🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《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篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。

大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）