前言

常見的幾大排序都已經更新完畢了（堆排序早在二叉樹講堆的時候就講了），本文就來對這些排序演算法進行一下小結。

筆者水平有限，難免存在紕漏，歡迎指正交流。

常見排序小結

排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。

穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，排序結果可能會存在不唯一的情況，若經過排序，這些記錄的相對次序保持不變，即在原序列中，則稱這種排序演算法是穩定的，否則稱為不穩定的。

換句話說就是，排序之後，如果相等元素之間原有的相對順序不變，則稱所用的排序方法是穩定的，反之則稱之為不穩定的。

微信截圖_20210119163314

例如上圖，我們的陣列中有兩個相同的元素 4，我們分別用不同的排序演算法對其排序，演算法一排序之後，兩個相同元素的相對位置沒有發生改變，我們則稱之為穩定的排序演算法，演算法二排序之後相對位置發生改變，則為不穩定的排序演算法。

那排序演算法的穩定性又有什麼用呢？

在我們做題中大多隻是將陣列進行排序，只需考慮時間複雜度空間複雜度等指標，排序演算法是否穩定一般不進行考慮。但是在真正軟體開發中排序演算法的穩定性是一個特別重要的衡量指標。假設我們想要實現年終獎從少到多的排序，然後相同年終獎區間內的紅豆數也按照從少到多進行排序。排序演算法的穩定性在這裡就顯得至關重要。這是為什麼呢？見下圖

第一次排序之後，所有的職工按照紅豆數從少到多有序。

第二次排序中，我們使用穩定的排序演算法，所以經過第二次排序之後，年終獎相同的職工，仍然保持著紅豆的有序（相對位置不變），紅豆仍是從小到大排序。我們使用穩定的排序演算法，只需要兩次排序即可。

因為實際生活生產中要進行排序的話完全有可能不止排序一次，每一次排序的衡量標準也可能多種多樣，而穩定排序可以讓前一次排序的結果服務於後一次排序中數值相等的那些數，讓它們保留前一次排序得到的相對順序。

上述情況如果我們利用不穩定的排序演算法，要實現這一效果的話會比較複雜。

內部排序：資料元素全部放在記憶體中的排序。

外部排序：資料元素太多不能同時放在記憶體中，根據排序過程的要求不能在內外存之間移動資料的排序。

比較排序和非比較排序

我們根據元素是否依靠與其他元素的比較來決定元素間的相對次序，來區分比較排序演算法和非比較排序演算法。

常見的排序演算法

這裡有個用來測試各種排序效能的函式，可以在實現排序函式後呼叫該函式測試效能。

// 測試排序的效能對比 void TestOP() { srand(time(0)); const int N = 100000; int* a1 = (int*)malloc(sizeof(int)*N); int* a2 = (int*)malloc(sizeof(int)*N); int* a3 = (int*)malloc(sizeof(int)*N); int* a4 = (int*)malloc(sizeof(int)*N); int* a5 = (int*)malloc(sizeof(int)*N); int* a6 = (int*)malloc(sizeof(int)*N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; } int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort(a5, 0, N-1); int end5 = clock(); int begin6 = clock(); MergeSort(a6, N); int end6 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("QuickSort:%d\n", end5 - begin5); printf("MergeSort:%d\n", end6 - begin6); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); }

以及用來測試排序的OJ題：912. 排序陣列 - 力扣（LeetCode）