❶ 排序演算法(go實現)
時間:
平均O(n 2 ) 最差O(n 2 ) 最好O(n)
空間:
O(1)
它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然後,再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。
n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體演算法描述如下:
時間:
平均O(n 2 ) 最差O(n 2 ) 最好O(n 2 )
空間:
O(1)
它的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。
一般來說,插入排序都採用in-place在數組上實現。具體演算法描述如下:
時間:
平均O(n 2 ) 最差O(n 2 ) 最好O(n)
空間:
O(1)
快速排序的基本思想: 二分遞歸 ,通過一趟排序將待排記錄分隔成獨立的兩部分,其中一部分記錄的關鍵字均比另一部分的關鍵字小,則可分別對這兩部分記錄繼續進行排序,以達到整個序列有序。
快速排序使用分治法來把一個串(list)分為兩個子串(sub-lists)。具體演算法描述如下:
我們可以通過雙指針在O(n)的時間復雜度內獲取合適的 j
我們設立兩個指針 i 和 j,同時設置一個標志值 arr[low],一般來說,標志值取數組第一個元素
上述演算法結束之後,j 所在的位置即為我們尋找的 j
4.3 時間空間復雜度
時間:
平均O(nlog 2 n) 最差O(n 2 ) 最好O(nlog 2 n)
空間:
O(1)
演算法思想參考自: https://www.cnblogs.com/onepixel/articles/7674659.html