[C描述演算法入門]常見排序小結

語言: CN / TW / HK

theme: channing-cyan highlight: a11y-dark


持續創作,加速成長!這是我參與「掘金日新計劃 · 10 月更文挑戰」的第12天,點選檢視活動詳情

前言

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

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

常見排序小結

排序的概念

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

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

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

微信截圖_20210119163314

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

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

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

img

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

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

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

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

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

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

比較排序和非比較排序

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

常見的排序演算法

image-20220812120415698

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

// 測試排序的效能對比  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)

排序演算法總結

綜合而言快排效能最優、使用最多,堆排適合TopK問題,歸併適合外排序。

image-20220907220213733

image-20220907220222520

穩定性分析

實際上這些排序都可以做到不穩定,但如果能通過一些控制來保持穩定就說它是穩定的。

氣泡排序

你想啊,氣泡排序每次兩兩比較,比如說我要排升序,當前一個比後一個大時就要兩兩交換,那要是相等呢?相等時不會交換,繼續把後面的數兩兩比較,所以說它是穩定的。

img

其實吧,每趟排序都把最大或最小的數一點一點“頂”到已排序序列中,就像泡泡浮上水面一樣,遇到兩個值相等的情況不會發生交換,所以的確是穩定的。

直接選擇排序

有些資料認為該排序是穩定的,實際上是不穩定的。

img

無論是原版還是改進版,都能找到使排序不穩定的情況,也就是該排序不能保證穩定。

image-20220916225858135

直接插入排序

該排序是穩定的,我們實現的邏輯是未排序序列第一個元素和已排序序列從後向前比較,如果未排序序列第一個元素更小,就讓已排序序列的元素向後移動“騰出位置”,相等和更大的情況就是直接放在已排序序列元素的後面,所以並不會破壞相等元素的相對位置。

img

希爾排序

同一組內由於進行直接插入排序所以相同資料相對位置可以不變,但預排序時相同的資料可能被分到不同組,這樣就不能保證穩定性。

比如:

image-20220912224648926

堆排序

直接上一個極端場景:

image-20220912200954173

其實建堆的時候都可能已經破壞穩定性了,在建完堆後無論資料如何都會按部就班用交換堆頂堆尾、向下調整方法來排序,就比如遇到上圖情況,你說穩定不穩定?那肯定不穩定。

快速排序

你覺得穩定嗎?不穩定,就比如下面這個例子:

image-20220912230004133

歸併排序

能控制一下做到穩定,就是在歸併判斷的時候,多加上一個等於:if (arr[begin1] <= arr[begin2]) tmp[j++] = arr[begin1++]; ,在第一個序列的元素等於第二個序列元素時歸併第一個序列的元素,這樣就不會破壞穩定性,所以是穩定的。

排序需要掌握的知識點和程度

  1. 幾大排序的原理和實現
  2. 時間複雜度和空間複雜度(不要背,要靠理解)
  3. 穩定性
  4. 排序之間特性的對比

以上就是本文全部內容,感謝觀看,你的支援就是對我最大的鼓勵~

src=http___c-ssl.duitang.com_uploads_item_201708_07_20170807082850_kGsQF.thumb.400_0.gif&refer=http___c-ssl.duitang.gif