【數據結構初階第十八節】八大排序系列(上篇)

看似不起眼的日復一日，總會在某一天讓你看到堅持的意義。??????云邊有個稻草人-CSDN博客

hello，好久不見！?

一. 排序的概念及運用

1.?概念

2.?運用?

3. 常見排序算法

二. 實現常見排序算法

1.?插入排序

（1）直接插入排序

【圖解】

【代碼】

【直接插入排序的特性總結】

【冒泡排序，堆排序，直接插入排序時間復雜度比較】

（2）希爾排序

【思路代碼圖解】?

【優化】

【希爾排序代碼】

【希爾排序時間復雜度】

2.選擇排序

（1）直接選擇排序

【代碼】

【直接選擇排序的特性總結】

（2）堆排序

3.交換排序

（1）冒泡排序

【代碼實現】

【冒泡排序特性總結】

（2）快速排序

【Hoare版本】

【細節問題】

【代碼】

【代碼圖解】

Relaxing Time ！

————————————《We Don't Talk Anymore》————————————

正文開始——

一. 排序的概念及運用

1.?概念

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

2.?運用?

院校排名

3. 常見排序算法

接下來我們來學習實現這些常見的排序算法。。。

二. 實現常見排序算法

int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8};

1.?插入排序

【基本思想】

直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。

實際中我們玩撲克牌時，就用了插入排序的思想。

（1）直接插入排序

【圖解】

當插入第 i (i>=1) 個元素時，前面的 array[0],array[1],…,array[i-1] 已經排好序，此時用?array[i] 的排序碼與 array[i-1],array[i-2],… 的排序碼順序進行比較，找到插入位置即將 array[i] 插入，原來位置上的元素順序后移。

這個動圖顯示了直接插入排序的步驟，里面原始的數據是10,9,8,7,6,5,4,3,2,1，是一個降序序列，現在我們用直接插入排序將其排列成升序序列，細節過程難以用文字描述，我們對照著代碼理解。

外層 for 循環來控制內層循環的次數。
for 循環的 i 的最大值為n-2，最后一次循環end指向倒數第二個元素，此時tmp里面存放的是整個序列里面最后一個數據，就是再將最后一個數據插入到前面有序序列里面合適的位置整體就ok了。
每一次進入新的for循環就是新的end，新的tmp，各自又分配到了新的數據，重復前面整體的步驟；進入到里面的 while 循環是在為 tmp 在前面的有序序列里面找合適的位置插入進去。
每次插入數據都是往end+1的地方插，end+1這個位置留用，誰大誰往這放。
tmp保存正在排序的數據，不斷比較然后賦值的過程中會將tmp原位置的值給覆蓋，所以我們保存一份在找到合適的位置后給它放進去。

【代碼】

//直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;//--是為了讓tmp與區間前面的元素進行挨個比較，最后找到合適的位置}else{break;}}//此時end可能等于-1，或者是因為end指向的元素 < tmp，此時我們還沒有進行最后的賦值，//這時我們都要把tmp里面的數據賦值給arr[end+1]arr[end + 1] = tmp;}
}

【直接插入排序的特性總結】

【冒泡排序，堆排序，直接插入排序時間復雜度比較】

冒泡排序代碼見下

時間復雜度為O(N^2)，空間復雜度為O(1)


void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//冒泡排序
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){//升序if (arr[j] > arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){break;}}
}

堆排序代碼見下

時間復雜度為O(N * logN)，空間復雜度為O(1)

//向下調整數據
void AdjustDown(int* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){//找出左右孩子中最小的->小堆 >//找出左右孩子中最大的->大堆 <if (child + 1 < n && arr[child] < arr[child + 1]){child++;}// < 建小堆// > 建大堆 if (arr[child] > arr[parent]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
void HeapSort(int* arr, int n)
{//向下調整算法建堆for (int i = (n - 2) / 2; i >= 0; i--){AdjustDown(arr, i, n);}//堆排序int end = n - 1;while (end > 0){//end指向的是最后一個數據Swap(&arr[0], &arr[end]);//有效的數據個數減了1AdjustDown(arr, 0, end);end--;}
}

直接插入排序代碼見下

時間復雜度最好的情況是O(N)，最差的情況為O(N^2)，最差的情況只有是有序的降序序列時才發生(如果我們要排升序的話)

//直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;//--是為了讓tmp與區間前面的元素進行挨個比較，最后找到合適的位置}else{break;}}//此時end可能等于-1，或者是因為end指向的元素 < tmp，此時我們還沒有進行最后的賦值，//這時我們都要把tmp里面的數據賦值給arr[end+1]arr[end + 1] = tmp;}
}

光說不行，我們可以借助測試代碼來驗證這幾種排序的性能到底如何——

TestOP函數思路——我們先開辟10W個數據類型大小的空間，然后隨機生成10W個數據并將數據依次插入到數組里面，這里面采用了賦值，保證各個數組里面的數據是一樣的，這樣在利用同樣數據的數組排序的時候就會公平統一，之后利用clock函數來計算各個排序運行的時間。下面是clock函數的簡單介紹，使用起來還是很簡單的，對于TestOP()里面的使用，就是求兩次clock函數之間的時間差就是排序所用的時間。

// 測試排序的性能對?
//下面我們還沒有實現的排序求時間我們就先注釋掉
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);*/int* a7 = (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];*/a7[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();int begin7 = clock();BubbleSort(a7, N);int end7 = 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);*/printf("BubbleSort:%d\n", end7 - begin7);free(a1);/*free(a2);free(a3);*/free(a4);/*free(a5);free(a6);*/free(a7);
}

下面我們來看一下運行結果

運行結果的單位是ms，對于相同的10W數據直接插入排序時間是3s多，而堆排序還要小得多，但是冒泡排序是接近40s，可見冒泡排序的效率之低（冒泡排序的作用僅僅只是教學意義，讓一開始菜鳥的我學習循環嵌套啥的）。堆排序效率確實很高，直接插入排序也還不錯，下面我們可以再對直接插入排序進行優化，就變成了希爾排序。

（2）希爾排序

希爾排序法又稱 縮小增量法 。希爾排序法的基本思想是：先選定?個整數（通常是gap = n/3+1），把待排序文件所有記錄分成各組，所有的距離相等的記錄分在同?組內，并對每?組內的記錄進行排序，然后gap=gap/3+1得到下?個整數，再將數組分成各組，進?插入排序，當gap=1時，就相當于直接插入排序。它是在直接插?排序算法的基礎上進?改進而來的，綜合來說它的效率肯定是要?于直接插?排序算法的。下圖是大致的排序思路：

【思路代碼圖解】?

【優化】

注意gap的變化，gap = gap / 3 +1。

【希爾排序代碼】

//希爾排序
//時間復雜度為O(N^1.3)
void ShellSort(int* arr, int n)
{int gap = n;//最外層循環來控制每組元素的間隔while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

我們還是調用上面的測試代碼來看一下運行時間，結果顯示希爾排序相對于直接插入排序確實提高了不少，贊！

下去我們可以試著測試，對于同樣的降序序列，直接插入排序和希爾排序各自的運行效率怎么樣，可以先使用冒泡排序搞一個降序序列。

【希爾排序時間復雜度】

經過不斷地預排序，小的數據基本在左邊，大的數據基本在右邊，在以后gap==1時，數組已經接近有序，時間復雜度不可能達到n^2，應該是接近O（n）。總的下來希爾排序的時間復雜度接近O(n^1.3)。

為什么gap = gap / 3 + 1取3個為一組呢？假設有10個數據，我們看一下取3個為一組和2個為一組的區別：

gap / 3 + 1? ? ?4---->2---->1

gap / 2 + 1? ? ?6---->4---->3---->2---->1

顯而易見，當取三個為一組的話外層循環的次數比較少的就可以達到gap==1，兩種方法相比每組分到的數據個數相差不大，循環次數越多，時間復雜度就越高

通過上面的分析我們可以畫出下面的曲線圖

因此，希爾排序在最初和最后的排序的次數都為n，即前?階段排序次數是逐漸上升的狀態，當到達某?頂點時，排序次數逐漸下降?n，?該頂點的計算暫時?法給出具體的計算過程。

希爾排序時間復雜度不好計算，因為 gap 的取值很多，導致很難去計算，因此很多書中給出的希爾排序的時間復雜度都不固定。《數據結構(C語?版)》--- 嚴蔚敏書中給出的時間復雜度為：

2.選擇排序

【 基本思想 】

每?次從待排序的數據元素中選出最?（或最?）的?個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。

（1）直接選擇排序

?在元素集合 array[i]--array[n-1] 中選擇關鍵碼最?(?)的數據元素；
?若它不是這組元素中的最后?個(第?個)元素，則將它與這組元素中的最后?個（第?個）元素；
在剩余的 array[i]--array[n-2] （ array[i+1]--array[n-1] ）集合中，重復上述步驟，直到集合剩余 1 個元素。

【代碼】

//直接插入排序
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin, maxi = begin;//在后面區間內找maxi，minifor (int j = begin+1; j <= end; j++){if (arr[j] < arr[mini]){mini = j;}if (arr[j] > arr[maxi]){maxi = j;}}if (maxi == begin){maxi = mini;}Swap(&arr[begin], &arr[mini]);Swap(&arr[end], &arr[maxi]);begin++;end--;}
}

看一下運行結果是否正確，對了！

【直接選擇排序的特性總結】

直接選擇排序比較好理解，但是效率不好，實際中很少使用，那為啥還要學呢，為了你知道這是最差的排序方式（哈哈）
時間復雜度：O(N^2)
空間復雜度：O(1)

（2）堆排序

堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的?種排序算法，它是選擇排序的?種。它是通過堆來進行選擇數據。需要注意的是排升序要建?堆，排降序建?堆。在?叉樹章節我們已經實現過堆排序，這里不再贅述，我之前寫了一篇詳細的關于堆排序的博客，下面是博客鏈接：

【【數據結構初階第十五節】堆的應用（堆排序 + Top-K問題）-CSDN博客】

3.交換排序

（1）冒泡排序

前?在算法題中我們已經接觸過冒泡排序的思路了，冒泡排序是?種最基礎的交換排序。之所以叫做冒泡排序，因為每?個元素都可以像小氣泡?樣，根據自身大小?點?點向數組的?側移動。

【代碼實現】

//冒泡排序
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){if (arr[j] < arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){break;}}
}

【冒泡排序特性總結】

時間復雜度：O(N^2)

空間復雜度：O(1)

（2）快速排序

快速排序是Hoare于1962年提出的?種?叉樹結構的交換排序?法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩?序列，左?序列中所有元素均?于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。

快速排序實現主框架：

//快排
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//1.找基準值int key = _QuickSort(arr,left,right);//2.左子序列進行排序QuickSort(arr, left, key - 1);//3.右子序列進行排序QuickSort(arr, key + 1, right);
}

?將區間中的元素進?劃分的 _QuickSort ?法主要有以下?種實現?式：

【Hoare版本】

【細節問題】

【代碼】

//找基準值
int _QuickSort(int* arr, int left, int right)
{int key = left;left++;while (left <= right){//找比基準值大的while (left <= right && arr[left] < arr[key]){left++;}//找比基準值小的while (left <= right && arr[right] > arr[key]){right--;}if (left <= right){Swap(&arr[right--], &arr[left++]);}}//將right指向的數據和key指向的數據進行交換Swap(&arr[key], &arr[right]);return right;
}//快排
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//1.找基準值int key = _QuickSort(arr,left,right);//2.左子序列進行排序QuickSort(arr, left, key - 1);//3.右子序列進行排序QuickSort(arr, key + 1, right);
}

效果展示：

我們再根據代碼來一遍流程，看看代碼內部到底是怎么運行的

【代碼圖解】

問題1：為什么跳出循環后right位置的值?定不?于key？

當 left > right 時，即right?到left的左側，?left掃描過的數據均不?于key，因此right此時指向的數據?定不?于key

問題2：為什么left 和 right指定的數據和key值相等時也要交換？

相等的值參與交換確實有?些額外消耗。實際還有各種復雜的場景，假設數組中的數據?量重復時，?法進?有效的分割排序。