【數據結構與算法】數據結構初階：排序內容加餐（一）—

🔥個人主頁：艾莉絲努力練劍

?專欄傳送門：《C語言》、《數據結構與算法》、C語言刷題12天IO強訓、LeetCode代碼強化刷題

🍉學習方向：C/C++方向

??人生格言：為天地立心，為生民立命，為往圣繼絕學，為萬世開太平

這個用來測試代碼的對比排序性能的代碼博主還是放在下面，大家可以對比一下各種排序算法的運行時間，從而對不同排序方法的時間復雜度有更加直觀地認識：

代碼演示：

//測試排序的性能對比  
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];}//begin和end的時間差就是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);
}

前言：本篇文章，我們繼續來介紹排序相關的知識點，在初階的數據結構與算法階段，我們把知識點分成三部分，復雜度作為第一部分，順序表和鏈表、棧和隊列、二叉樹為第二部分，排序為第二部分，我們之前已經介紹完了第一部分：算法復雜度和第二部分：順序表和鏈表、棧和隊列、二叉樹。本文我們繼續開始學習第三部分中的排序的內容啦。?

正文

一、三路劃分

1、三路劃分的概念

2、思想

3、代碼實現

（1）寫法1

（2）寫法2?

（3）寫法3

二、自省排序（內觀排序）

1、找基準值出現問題

2、代碼實現?

3、完整代碼

結尾

正文

一、三路劃分

1、三路劃分的概念

使用三路劃分可以提升當數組中，有大量相同的值時，排序的時間效率，三路劃分的核心思想有點類似hoare版本的left、right左右指針和lomuto雙指針法的前后指針的結合（這里的hoare版本的左右指針和lomuto雙指針的前后指針博主在之前的文章中已經介紹過了）。

核心思想：就是把數組中的數據分為三段：比key小的值、跟key相等的值以及比key大的值，因此叫做三路劃分算法。

2、思想

三路劃分實現的思想：

1. key默認取left位置的值；

2. left指向區間最左邊，right指向區間最后邊，cur指向left+1位置；

3. cur遇到比key小的值后跟left位置交換，換到左邊，left++，cur++；

4. cur遇到比key大的值后跟right位置交換，換到右邊，right--；

5. cur遇到跟key相等的值之后，cur++；

6. 直到 cur > right 結束——

3、代碼實現

代碼演示：

（1）寫法1

//三路劃分
KeyWayIndex PartSort3Way(int* arr, int left, int right)
{int key = arr[left];//left和right指向就是跟key相等的區間//[begin,left-1]  [left,right]  [right+1,end]int cur = left + 1;while (cur <= right){//1、cur遇到比key小，小的換到左邊，同時把key換到中間位置//2、cur遇到比key大，大的換到右邊if (arr[cur] < key){Swap(&arr[cur], &arr[left]);++left;++cur;}else if (arr[cur] > key){Swap(&arr[cur], &arr[right]);//cur不能動--right;}else{++cur;}}KeyWayIndex kwi;kwi.leftkeyi = left;kwi.rightkeyi = right;return kwi;
}

不理解這個寫法也沒關系，博主自己測試的時候用的是這個寫法——

（2）寫法2?

int _QuickSort3Way(int* arr, int left, int right)
{return;
}//三路劃分實現
void QuickSort3Way(int* arr, int left, int right)
{if (left >= right){return;}//隨機數取法srand((unsigned int)time(NULL));int randi = left + rand() % (right - left + 1);Swap(&arr[left], &arr[randi]);//三數取中int midi = _QuickSort3Way(arr, left, right);//三路劃分int key = arr[left];int cur = left + 1;int begin = left;int end = right;while (cur <= right){//1、cur遇到比key小，小的換到左邊，同時把key換到中間位置//2、cur遇到比key大，大的換到右邊if (arr[cur] < key){Swap(&arr[cur], &arr[left]);++left;++cur;}else if (arr[cur] > key){Swap(&arr[cur], &arr[right]);//cur不能動--right;}else{++cur;}}//三路劃分 [begin,left-1]  [left,right]  [right+1,end]QuickSort3Way(arr, begin, left - 1);QuickSort3Way(arr, right + 1, end);
}

運行一下，確實能跑出來——?

（3）寫法3

此外，還可以采用這種寫法——

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void QuickSort(int* arr, int left, int right)
{if (left >= right)return;int begin = left;int end = right;//隨機選keyint randi = left + (rand() % (right - left + 1));Swap(&arr[left], &arr[randi]);//三路劃分//left和right指向就是跟key相等的區間// [begin, left-1] [left, right] right+1, end]int key = arr[left];int cur = left + 1;while (cur <= right){//1、cur遇到比key小，小的換到左邊，同時把key換到中間位置//2、cur遇到比key大，大的換到右邊if (arr[cur] < key){Swap(&arr[cur], &arr[left]);++left;++cur;}else if (arr[cur] > key){Swap(&arr[cur], &arr[right]);--right;}else{++cur;}}// [begin, left-1] [left, right] right+1, end]QuickSort(arr, begin, left - 1);QuickSort(arr, right + 1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {srand(time(0));QuickSort(nums, 0, numsSize - 1);*returnSize = numsSize;return nums;
}

時間復雜度：O(n*logn) 。

二、自省排序（內觀排序）

自省排序(Introsort)是一種混合排序算法，它結合了快速排序(Quicksort)、堆排序(Heapsort)和插入排序(Insertion sort)的優點。其核心思想是利用快速排序的高效性，同時在遞歸深度超過一定限制時切換到堆排序以避免最壞情況的發生，從而保證整體性能。

introsort的快排排序OJ代碼

——C++庫提出來的

1、找基準值出現問題

這里的introsort是introspective(自省的) sort采用了縮寫，他的名字其實表達了他的實現思路，他的思路就是進行自我偵測和反省，快速排序遞歸深度太深（sgi stl使用的是深度為2倍排序元素數量的對數值）就說明在這種數據序列下，選key出現了問題，性能在快速退化，那么就不要再進行快排分割遞歸了，改換為堆排序進行排序。

2、代碼實現?

代碼演示：

//自省排序(內觀排序)
void IntroSort(int* arr, int left, int right, int depth, int defaultDepth)
{if (left >= right)return;//數組大小小于16的小數組，換為插入排序，簡單遞歸次數if (right - left + 1 < 16){InsertSort(arr + left, right - left + 1);return;}//當深度超過2*logn，則改用堆排序if (depth > defaultDepth){HeapSort(arr + left, right - left + 1);return;}depth++;int begin = left;int end = right;//隨機選keyint randi = left + (rand() % (right - left));Swap(&arr[left], &arr[right]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}++cur;}Swap(&arr[prev], &arr[keyi]);keyi = prev;//[begin,keyi-1]  keyi  [keyi+1,end]IntroSort(arr, begin, keyi - 1, depth, defaultDepth);
}

時間復雜度：O(n*logn) 。

3、完整代碼

代碼演示：

#define  _CRT_SECURE_NO_WARNINGS  1/*** Note: The returned array must be malloced, assume caller calls free().*/
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//選出左右孩子中大的那?個if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//建堆--向下調整建堆-- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// 自己先實現—— O(N * logN)int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1;int tmp = a[i];// 將tmp插入到[0, end]區間中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}
void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{if (left >= right)return;//數組長度小于16的小數組，換為插入排序，簡單遞歸次數if (right - left + 1 < 16){InsertSort(a + left, right - left + 1);return;}//當深度超過2 * logN時改用堆排序if (depth > defaultDepth){HeapSort(a + left, right - left + 1);return;}depth++;int begin = left;int end = right;//隨機選keyint randi = left + (rand() % (right - left + 1));Swap(&a[left], &a[randi]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;// [begin, keyi-1] keyi [keyi+1, end]IntroSort(a, begin, keyi - 1, depth, defaultDepth);IntroSort(a, keyi + 1, end, depth, defaultDepth);
}
void QuickSort(int* a, int left, int right)
{int depth = 0;int logn = 0;int N = right - left + 1;for (int i = 1; i < N; i *= 2){logn++;}//introspective sort -- 自省排序IntroSort(a, left, right, depth, logn * 2);
}
int* sortArray(int* nums, int numsSize, int* returnSize) 
{srand(time(0));QuickSort(nums, 0, numsSize - 1);*returnSize = numsSize;return nums;
}

結尾

往期回顧：

【數據結構與算法】數據結構初階：詳解排序（四）——非比較排序：計數排序（鴿巢原理）——對哈希直接定址法的變形應用，排序算法復雜度及穩定性分析

本期內容需要回顧的C語言知識如下面的截圖中所示（指針博主寫了6篇，列出來有水字數嫌疑了，就只放指針第六篇的網址，博主在指針（六）把指針部分的前五篇的網址都放在【往期回顧】了，點擊【傳送門】就可以看了）。

大家如果對前面部分的知識點印象不深，可以去上一篇文章的結尾部分看看，博主把需要回顧的知識點相關的博客的鏈接都放在上一篇文章了，上一篇文章的鏈接博主放在下面了：

【數據結構與算法】數據結構初階：詳解順序表和鏈表（三）——單鏈表（上）