快速排序的深入优化——三路划分，内省排序（C语言）
1. 快排性能的关键点分析
决定快排性能的关键点是每次单趟排序后，key对数组的分割，如果每次选key基本⼆分居中，那么快 排的递归树就是颗均匀的满⼆叉树，性能最佳。但是实践中虽然不可能每次都是⼆分居中，但是性能 也还是可控的。但是如果出现每次选到最⼩值/最⼤值，划分为0个和N-1的⼦问题时，时间复杂度为 O(N^2)，数组序列有序时就会出现这样的问题，我们前⾯已经⽤三数取中或者随机选key解决了这个问题，也就是说我们解决了绝⼤多数的问题，但是现在还是有⼀些场景没解决(数组中有⼤量重复数据 时)，例如下面：
多个key值相等，或者全是相同的数。
int a[] = { 6,1,7,6,6,6,4,9 };
int a[] = { 3,2,3,3,3,3,2,3 };
int a[] = { 3,3,3,3,3,3,3,3 };2.三路划分算法
这里使用三路划分可以提升当数组中，有大量相同的值时，排序的时间效率，三路划分的核⼼思想有点类似hoare的左右指针和lomuto的前后指针的结合（这里的hoare的左右指针和lomuto的前后指针在小编前面“各种排序方法”文章中有所讲解）。核⼼思想是把数组中的数据分为三段⽐key⼩的值；跟key相等的值；⽐key⼤的值，所以叫做三路划分算法。
实现的思想：
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结束
排序成这样以后，再递归left之前的数组，和right之后的数组就可以了。
注意：这种排序方法，主要是当数组中有大量相同的数据时，时间效率较高，但如果数组中没有大量相同的数据，这种算法的时间效率甚至还不如，lomuto和hoare版的快速排序。
三路划分针对有⼤量重复数据时，效率很好，其他场景就⼀般，但是三路划分思路还是很有价 值的，有些快排思想变形体，要⽤划分去选数，他能保证跟key相等的数都排到中间去，三路划分的价值就体现出来了。
void _QuicksortPro(int* arr, int left, int right)//三路划分：有大量相同数据
{
if (left >= right)
return;
int begin = left;
int end = right;
int randi = left + (rand()%(right - left + 1));
Swap(&arr[left], &arr[randi]);
int key = arr[left];
int cur = left + 1;
while (cur <= right)
{
if (arr[cur] < key)
{
Swap(&arr[left++], &arr[cur++]);
}
else if (arr[cur > key])
{
Swap(&arr[cur], &arr[right--]);
}
else
{
cur++;
}
}
_QuicksortPro(arr, begin, left - 1);
_QuicksortPro(arr, right + 1, end);
}
void Quicksort(int* arr, int left, int right)
{
srand(time(0));
_QuicksortPro(arr, left, right);
}3.introsort的快排排序（内省排序）
introsort是由DavidMusser在1997年设计的排序算法，C++sgi STL sort中就是⽤的introspective sort(内省排序)思想实现的。内省排序可以认为不受数据分布的影响，⽆论什么原因划分不均匀， 导致递归深度太深，他就是转换堆排了，堆排不受数据分布影响。
首先确定递归深度达到多少时,深度一般为logn的两倍（数据个数取二的对数：2*logn），就停止这种排序转换成堆排序（堆排序，在小编之前“堆的应用”文章中已有详细讲解）；
其次当数组长度小于十六时，就直接使用插入排序，简单递归次数；
代码如下：
//直接插入排序
void InsertSort(int* arr, int size)
{
for (int i = 0; i < size-1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + 1] = arr[end];
}
else {
break;
}
end--;
}
arr[end + 1] = tmp;
}
}
//堆排序
void AdjustDwon(int* a, int n, int root)
{
int parent = root;
int child = 2 * parent + 1;
while (child < n)
{
if (child + 1 < n && a[child] < a[child + 1])
{
child += 1;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
int parent = (n - 1 - 1) / 2;
while (parent >= 0)
{
AdjustDwon(a, n, parent);
parent--;
}
int size = n - 1;
while (size > 0)
{
Swap(&a[0], &a[size]);
AdjustDwon(a, size, 0);
size--;
}
}
void IntroSort(int* arr, int left, int right, int depth, int defaultDepth)
{
if (left >= right)
{
return;
}
if (right - left + 1 < 16)
{
InsertSort(arr + left, right - left + 1);
return;
}
if (depth > defaultDepth)
{
HeapSort(arr+ left, right - left + 1);
return;
}
depth++;
int begin = left;
int end = right;
int randi = left + (rand() % (right - left + 1));
Swap(&arr[randi], &arr[left]);
int keyi = left;
int prev = left, cur = left + 1;
while (cur <=right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi=prev;
IntroSort(arr, begin, keyi - 1, depth, defaultDepth);
IntroSort(arr, keyi+1, end, depth, defaultDepth);
}
void QuickSort（int *arr,int left,int right）
{
int depth = 0;
int logn = 0;
int size=right-left+1;
for (int i = 1; i < size; i*=2)
{
logn++;
}
IntroSort(arr, left, right, depth,logn*2);
}
原文地址：https://blog.csdn.net/2401_83456040/article/details/143534963
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！