【八大排序】冒泡、直接選擇、直接插入、希爾、堆、歸并、快速、計數排序

一、排序的介紹

我們的生活中有很多排序，比如像成績的高低，身高的高低，體重的胖瘦，價格的高低等，這些都是排序，今天我們這期博客要講的就是如何去排序，我們一共會講解8個排序算法，它們分別是：
在這里插入圖片描述
這八大排序就是我們常用的主流排序算法，其中大多數都是我們耳熟能詳的排序算法，下面我們會逐步實現這八大算法。

二、排序算法的實現

2.1 直接插入排序

在這里插入圖片描述
直接插入排序是?種簡單的插入排序法，基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到?個已經排好序的有序序列中，直到所有的記錄插入完為止，得到?個新的有序序列。
這個排序就是依次從前往后掃描建立前k個有序序列，之后每次讓序列之后的一個元素依次從有序序列的末尾開始與有序序列的元素進行比較，如果序列中的元素比序列之后的第一個元素大，就讓序列中的元素向后移動，直到找到小于有序序列之后第一個元素的位置就將它插入。上面動圖中標黃的就是排好的有序序列，標紅的是有序序列后面的第一個元素，移動的過程就是比較的過程。

//直接插入排序
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--;}else{break;}}arr[end + 1] = tmp;}
}

以上代碼中，變量end永遠指向有序序列的最后一個元素，我們用tmp存儲有序序列之后的第一個元素，然后我們讓有序序列中的元素和tmp比較，如果大我們就后移，如果小就跳出循環，此時end指向比tmp小的元素或者是下標為-1的元素，那么end+1就是tmp該在的位置。直接插入排序的時間復雜度是：O(n²)。

測試代碼：

int main()
{int arr[] = { 9,6,5,1,10,11,35,27 };printf("排序之前：");print(arr, 8);InsertSort(arr, 8);printf("排序之后：");print(arr, 8);return 0;
}

代碼中print是我封裝的一個打印函數。

結果：
在這里插入圖片描述

2.2 希爾排序

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

//希爾排序
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是2，就每隔一個數據進行比較然后排序，假設gap是1就和直接插入排序相同了，都是依次比較，這時候也是最后一次排序。也就是gap>1預排序，gap=1直接插入排序。關于希爾排序時間復雜度，它一直是一個難題，它的時間是所取“增量”序列的函數，這涉及一些數學上尚未解決的難題，希爾排序的時間復雜度大約是：n^1.3。

測試結果：
在這里插入圖片描述

2.3 直接選擇排序

在元素集合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 max = begin;int min = begin;for (int i = begin+1;i <= end;i++){if (arr[i] > arr[max]){max = i;}if (arr[i] < arr[min]){min = i;}}if (max == begin){max = min;}Swap(&arr[min], &arr[begin]);Swap(&arr[max], &arr[end]);begin++;end--;}
}

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}

直接選擇排序的代碼比較好理解，需要注意的是，假設我們要對6、5、4進行排升序時，max會指向下標為0的位置，min會指向下標為2的位置，begin指向下標為0，min指向下標為2，如果我們不對max進行if語句判斷max是否在begin指向下標位置的話，交換兩次之后，還會是6、5、4，序列沒有發生改變，就會出錯，所以代碼中出現了if語句特判。

直接選擇排序的時間復雜度為：O(n²)。

測試結果：
在這里插入圖片描述

2.4 堆排序

堆排序就是利用數據結構堆的思想進行的排序，我們在之前的博客中已經實現了堆排序，所以我們會直接將代碼拷貝過來，->堆排序博客

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[parent] < arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆排序
void HeapSort(int* arr, int n)
{//建大根堆for (int i = (n - 1 - 1) / 2;i >= 0;i--){AdjustDown(arr, i, n);}int end = n - 1;//排序while (end >= 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}

雖然代碼的風格和之前博客上的略有差異，但思想還是相同的，排升序：建大根堆，逐步交換排序；排降序：建小根堆，逐步交換排序。堆排序的時間復雜度為：O(nlogn)。

測試結果：
在這里插入圖片描述

2.5 冒泡排序

冒泡排序是我們最為熟知，也是最為經典的排序算法，它的代碼思路簡單且易懂，核心思路就是有n個數字就比較n-1次逐步比較出最大值或最小值并交換排序。

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

經典動圖：
在這里插入圖片描述

冒泡排序的時間復雜度為：O(n²)。

測試結果：
在這里插入圖片描述

2.6 快速排序

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

經典動圖：
在這里插入圖片描述
快速排序找基準值遞歸版本可以分成兩個版本，一個是hoare版本，一個是lomuto前后指針；非遞歸版本會借用數據結構棧進行實現。

快速排序主體框架：

//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基準值int keyi = _QuickSort(arr, left, right);//左序列[left,keyi-1] 右序列[keyi+1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}

找基準值的過程就是排序的過程。

遞歸版本：

hoare版本：

創建左右指針，確定基準值
right從右向左找出比基準值小的數據，left從左向右找出比基準值大的數據，左右指針數據交換，進入下次循環

//hoare版本
int _QuickSort(int* arr, int left, int right)
{int keyi = left;left++;while (left <= right){//right:從右往左走，找比基準值要小的while (left <= right && arr[right] > arr[keyi]){right--;}//left：從左往右走，找比基準值要大的while (left <= right && arr[left] < arr[keyi]){left++;}if (left <= right){Swap(&arr[left], &arr[right]);}}Swap(&arr[keyi], &arr[right]);return right;
}

測試結果：
在這里插入圖片描述
圖解：

lomuto前后指針：

創建前后指針，從左往右找比基準值小的進行交換，使得小的都排在基準值的左邊。

我們會創建兩個指針prev及cur，cur走在前面，prev在后面
cur找到比基準值要小的之后，++prev讓prev和cur指向的下標的值進行交換，cur++。
cur未找到比基準值要小的數據cur++。

//lomuto前后指針法
int _QuickSort1(int* arr, int left, int right)
{int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[keyi], &arr[prev]);return prev;
}

運行結果：
在這里插入圖片描述
圖解：

非遞歸版本：

非遞歸版本的快速排序將會使用到數據結構棧，我們在之前的博客中已經實現過了數據結構棧，所以我們會將代碼拷貝過來，在利用棧的同時，我們找基準值的方法依舊使用lomuto前后指針法，【數據結構】棧相關博客<–

//非遞歸版本快速排序
void QuickSortNoR(int* arr, int left, int right)
{//定義棧ST st;//初始化棧StackInit(&st);StackPush(&st, left);StackPush(&st, right);while (!StackEmpty(&st)){//取棧頂元素int end = StackTop(&st);//銷毀棧頂元素StackPop(&st);int begin = StackTop(&st);StackPop(&st);//[begin,end]找基準值int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[keyi], &arr[prev]);keyi = prev;//[begin,keyi-1]  [keyi+1,end]if (keyi + 1 < end){StackPush(&st, keyi + 1);StackPush(&st, end);}if (begin < keyi - 1){StackPush(&st, begin);StackPush(&st, keyi - 1);}}//銷毀棧StackDestroy(&st);
}

快速排序的時間復雜度為：O(nlogn)。

測試結果：
在這里插入圖片描述
圖解：

2.7 歸并排序

歸并排序MERGE-SORT是建立在歸并操作上的?種有效的排序算法，該算法是采用分治法Divideand Conquer的?個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

歸并排序核心步驟：
在這里插入圖片描述
從圖中就可以看出很強烈的遞歸思想，所以我們的歸并排序依舊使用遞歸寫的。

//歸并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right){return;}int mid = left + (right - left) / 2;//[left,mid] [mid+1,right]_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);//第一次運行到這里時，是將數組分解成了一個個單個元素的時候。//合并兩個有序序列int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = begin1;//[begin1,end1] [begin2,end2]while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//導入原數組for (int i = left;i <= right;i++){arr[i] = tmp[i];}
}
//歸并排序
void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

歸并排序的時間復雜度為：O(nlogn)。

測試結果：
在這里插入圖片描述
至此我們已經講解了七種排序算法，并且這七種排序算法都是比較算法，都是通過一個個比較來排序的，而我們的計數排序不是比較算法，那么在講解計數排序之前呢，我們先來了解一下這七種排序算法的性能如何吧！

2.8 比較排序算法的性能展示

測試代碼：

// 測試排序的性能對?
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);
}

首先生成了100000個隨機數據，然后保證每個排序算法排的數組中的元素相同，再根據clock函數記錄開始和結束時間，就可以知道每個排序算法耗費的時間了(單位：ms)。

測試結果：
在這里插入圖片描述
從結果可以看出，

我們的第一梯隊分別是：堆排序、希爾排序、快速排序、歸并排序；
我們的第二梯隊分別是：直接插入排序、直接選擇排序。但它們都是以秒為單位的。
我們的第三梯隊就是我們熟悉的冒泡排序了。

2.9 計數排序

經典動圖：
在這里插入圖片描述

//計數排序
void CountSort(int* arr, int n)
{//找最大最小值int max = arr[0];int min = arr[0];for (int i = 1;i < n;i++){if (max < arr[i]){max = arr[i];}if (arr[i] < min){min = arr[i];}}//用max-min+1確定數組大小int* count = (int*)malloc(sizeof(int) * (max - min + 1));if (count == NULL){perror("malloc fail!");return;}//初始化數組countmemset(count, 0, sizeof(int) * (max - min + 1));for (int i = 0;i < n;i++){count[arr[i] - min]++;}//將count數組還原到原數組中，使其有序int index = 0;for (int i = 0;i < max - min + 1;i++){while (count[i]--){arr[index++] = i + min;}}
}