1、冒泡排序算法：

冒泡排序算法是最簡單也是最基本的排序算法之一，算法的原理為如下：

原理：將數據當中的每一個元素與之后的元素進行對比，如果當前元素比序列后的元素的值小，則交換兩者的順序，依次類推，直到最后一個數據完成排序即可！

時間復雜度：O(n²)

?API實現如下(兩層for循環嵌套實現)：

1 int BubbleSort(int *In, int N) 2 { 3 int temp; 4 for (int i = 0; i < N; i++) { 5 for (int j = i + 1; j < N; j++) { 6 if (In[i] > In[j]) { 7 temp = In[i]; 8 In[i] = In[j]; 9 In[j] = temp; 10 } 11 } 12 } 13 return 1; 14 }

2、插入排序算法：

插入排序算法是最基本的排序算法之一，少量數據的排序，其效率較高，算法的原理為如下：

原理：從第一個數值開始排序，在每一個P循環之后，0-P之間的所有元素都是已經完成排序了，P之后的第一個數據作為插值，和前面的順序序列對比并插入正確的位置！

時間復雜度：O(n²)，對于基本排列好序列的數據，插入排序算法的時間復雜度為O(n)。

?API實現如下：

1 int InsertSort(int *In, int N) 2 { 3 int P, i, temp; 4 for (P = 1; P < N; P++) { 5 temp = In[P]; 6 for (i = P; i > 0 && temp < In[i - 1]; i--) { 7 In[i] = In[i - 1]; 8 } 9 In[i] = temp; 10 } 11 return 1; 12 }

3、希爾排序算法：

希爾排序算法的平均時間復雜度較低，算法的原理如下：

原理：算法在運行的過程中，每次將前面的數據與其間隔stride步長位置的數據進行對比，完成當前stride的全部對比之后，將stride縮小為原來的一半，以此類推，最后stride為1，這個時候對比的就是相鄰的元素，對比完成，序列同時完成了排序。

時間復雜度：O(n*log(n))

API_0實現如下(常規的希爾序列初始增量：N/2. N為數據的長度)：

1 int ShellSort(int *In, int N) 2 { 3 int i, j, stride,Temp; 4 /* 這里需要注意的是，stride最終的結果為0：當stride=1時，stride/=2得到的stride=floor(0.5)=0,所以循環退出 */ 5 for (stride = N / 2; stride > 0; stride /= 2) { 6 for (i = stride; i < N; i++) { 7 Temp = In[i]; 8 for (j = i; j >= stride && Temp < In[j - stride] ; j -= stride) { 9 In[j] = In[j - stride]; 10 } 11 In[j] = Temp; 12 } 13 } 14 return 1; 15 }

API_1實現如下(希爾Hibbard增量序列：Hibbard：{1, 3, ..., 2^k-1})

注：這是一種沖破二次時間屏障的算法

1 int ShellSort_Hibbard(int *In, int N) // 時間復雜度最壞的情況為o(N^3/2) 2 { 3 int i, j, stride, Temp; 4 int k = log2(N / 2 + 1); 5 // printf("The k is:%d\n", k); 6 /* 這里需要注意的是，stride最終的結果為0：當stride=1時，stride/=2得到的stride=floor(0.5)=0,所以循環退出 */ 7 for (stride = (2<<k) - 1; stride > 0 && k >= 1; stride = (1<<k) - 1) { // 注意這里的左移運算的優先級低于減法的優先級，所以要打上括號 8 // printf("The stride is:%d\n", stride); 9 for (i = stride; i < N; i++) { 10 Temp = In[i]; 11 for (j = i; j >= stride && Temp < In[j - stride]; j -= stride) { 12 In[j] = In[j - stride]; 13 } 14 In[j] = Temp; 15 } 16 k -= 1; 17 } 18 return 1; 19 }

4、選擇快速排序算法：

快速排序算法的平均時間復雜度低，比較適合大量數據的排序算法，算法的原理如下：

原理：快速排序算法的情況和歸并排序算法比較相似！詳細原理參考這里：https://www.jianshu.com/p/7631d95fdb0b

時間復雜度：O(n*log(n))

API實現如下：

#define Cutoff 3 void Swap(int *A, int *B) {int Temp;Temp = *A;*A = *B;*B = Temp; } int Median3(int A[], int left, int right) // 尋找樞紐值 {int center = (left + right) / 2;int Temp;if (A[left] > A[center])Swap(&A[left], &A[center]);if (A[left] > A[right])Swap(&A[left], &A[right]);if (A[center] > A[right])Swap(&A[center], &A[right]);Swap(&A[center], &A[right - 1]); // 將樞紐值保存在數組的邊緣return A[right - 1]; // return pivot-返回樞紐值 } void QSort(int A[], int left, int right) {int i, j;int pivo;if (left + Cutoff <= right) { // 小數組的處理交給插值排序的方法，速度比較快一些pivo = Median3(A, left, right); // 樞紐值求解i = left; j = right - 1;for (;;){while (A[++i] < pivo) { } // 分割策略while (A[--j] > pivo) { } // 分割策略if (i < j)Swap(&A[i], &A[j]);elsebreak;}Swap(&A[i], &A[right - 1]); // Swap函數屬于外部調用，為了提高算法的效率可以直接顯式寫出代碼，不用callSwap函數 QSort(A, left, i-1); // 分割之后的遞歸調用QSort(A, i+1, right); // 分割之后的遞歸調用 }else {InsertSort(A + left, right - left + 1); // 插值排序算法 }} void QuickSort(int A[], int N) {QSort(A, 0, N-1); }

5、堆排序算法：

堆排序算法的平均時間復雜度較低，算法的原理如下：

原理：堆排序算法主要使用了堆數據結構的特點，創建二叉堆，并進行堆排序，即可完成數據的排序。

時間復雜度：O(n*log(n))

API實現如下：

1 #define LeftChild(i) (2*(i)+1) 2 void PerDown(int A[], int i, int N) // 降過濾法完成二叉堆的生成 3 { 4 int Child; 5 int Tmp; 6 for (Tmp = A[i]; LeftChild(i) < N; i = Child) { 7 Child = LeftChild(i); 8 if (Child != N - 1 && A[Child + 1] > A[Child]) 9 Child++; 10 if (Tmp < A[Child]) 11 A[i] = A[Child]; 12 else 13 break; 14 } 15 A[i] = Tmp; 16 } 17 void Swap(int *A, int *B) 18 { 19 int Temp; 20 Temp = *A; 21 *A = *B; 22 *B = Temp; 23 } 24 void HeapSort(int A[], int N) 25 { 26 int i; 27 for (i = N / 2; i >= 0; i--) { 28 PerDown(A, i, N); // 創建二叉堆 29 } 30 for (i = N - 1; i > 0; i--) 31 { 32 Swap(&A[0], &A[i]); // Delet the Max Element 33 PerDown(A, 0, i); 34 } 35 }

6、桶排序算法：

堆排序算法的平均時間復雜度較低，算法的原理如下：

原理：桶排序算法主要使用了類似于散列表的特點，將待排序的數據的數據內容統計起來，按照index桶的位置來確保數據的順序問題，從而完成了桶排序的任務！

時間復雜度：O(n)

API實現如下：

1 void BucketSort(int A[], int N, int MAX) // 對于排序小整數的情況，buckect桶排序算法非常的適合 2 { 3 int *Bucket = (int *)malloc(sizeof(int)*MAX); 4 int index; 5 for (int i = 0; i < MAX; i++) { 6 *(Bucket + i) = 0; 7 } 8 for (int i = 0; i < N; i++) { 9 index = A[i]; 10 Bucket[index] += 1; 11 } 12 index = 0; 13 for (int i = 0; i < MAX; i++) { 14 while (Bucket[i] != 0) { 15 A[index] = i; 16 index += 1; 17 Bucket[i] -= 1; 18 } 19 } 20 }

未完待續~

轉載于:https://www.cnblogs.com/uestc-mm/p/10739085.html

總結

以上是生活随笔為你收集整理的排序算法-综述的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。