【数据结构与算法】快速排序（中）快速排序的优化
【摘要】 快速排序是计算机科学中最著名的排序算法之一，与归并排序、堆排序等算法齐名。它以其简洁的算法逻辑和高效的性能表现，成为了排序算法中的佼佼者。本文将深入探讨快速排序算法的原理、实现方式以及优化策略，帮助读者更好地理解这一经典算法，并在实际应用中灵活运用。
目录
一、快速排序的优化
🍃三数取中
上述快速排序实现代码在最坏情况下（如数组已经有序或逆序）会退化到O(n^2)。为了改善最坏情况的表现，可以采取三数取中法来优化。
快速排序三数取中法（也称为三数中值分割法）是快速排序算法的一种优化策略，它旨在通过更合理地选择分区点来减少算法在极端情况下的性能退化。
思想：
三数取中优化的主要目的是减少在数组已经部分有序或几乎有序时，由于分区点（pivot）选择不当而导致的性能退化。在极端情况下，如果分区点总是选择到数组的最小值或最大值，那么每次分区都将导致一个空子数组和一个几乎不变的子数组，从而使得算法的时间复杂度退化为O(n^2)。
实现：
通过比较数组左端点（left）、中间点（mid）和右端点（right）的值，选择这三个数中的中间值作为分区点。将中间值交换为数组的左端点（left），原代码的逻辑依然不变
🍃小区间优化
目的：
小区间优化是为了处理快速排序在处理小规模数组时可能不如其他排序算法（如插入排序）高效的问题。当数组规模较小时，快速排序的递归调用和分区操作可能会带来较大的开销，比如区间只剩几个元素时仍然需要递归调用，建立栈帧，而使用插入排序在这些情况下通常能提供更好的性能。
实现：
在QuickSort1函数中，通过检查区间长度（right - left + 1），如果它小于某个阈值（比如10），则停止递归，转而调用插入函数对该小区间进行插入排序。这是一种常见的混合排序策略，旨在结合不同排序算法的优势。
🍃加入三数取中和小区间优化后的版本
Hoare版本
void Swap(int* a, int* b)//交换函数
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void InsertSort1(int* a, int n)//插入排序升序
{
for (int i = 1; i <= n-1 ; i++)//控制要插入的元素个数
{
int key = a[i];
int end = i - 1;
while (end >= 0 && a[end] > key)//移动元素
{
a[end + 1] = a[end];
end--;
}
a[end+1] = key;//满足大小关系后插入到指定位置
}
}
int GetMid(int* a,int left,int right)//三数取中函数
{
int mid = (left + right) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])//说明a[left] > a[mid] > a[right]
return mid;
//走到这里说明a[mid]是最小值
else if (a[left] > a[right])
return right;
else
return left;
}
else //走到这里说明a[left] < a[mid]
{
if (a[left] > a[right])//说明a[mid] > a[left] > a[right]
return left;
//走到这里说明a[left]是最小值
else if (a[mid] > a[right])
return right;
else
return mid;
}
}
void QuickSort1(int* a, int left, int right)//优化
{
if (left >= right)//只有一个元素或不存在，停止递归
return;
if ((right - left+1) < 10)//如果区间小于10，停止递归，改用直接插入排序
InsertSort1(a+left, right-left+1);//参数分别是区间起始地址，和区间元素个数
else
{
int midi = GetMid(a, left, right);//三个数取中间值的下标
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left, end = right;
while (begin < end)//begin与end未相遇时，继续循环
{
while (begin < end && a[end] >= a[keyi])//end先移动，找到小于keyi位置的值停止
end--;
while (begin < end && a[begin] <= a[keyi])//begin再移动，找到大于keyi位置的值停止
begin++;
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);//出循环后，begin与end相遇，交换此位置与keyi位置的值
keyi = begin;//更新keyi的位置
//[left][keyi-1]keyi[keyi+1][right] 左右区间划分
QuickSort1(a, left, keyi - 1);//左区间递归
QuickSort1(a, keyi + 1, right);//右区间递归
}
}
挖坑法
void Swap(int* a, int* b)//交换函数
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void InsertSort1(int* a, int n)//插入排序升序
{
for (int i = 1; i <= n-1 ; i++)//控制要插入的元素个数
{
int key = a[i];
int end = i - 1;
while (end >= 0 && a[end] > key)//移动元素
{
a[end + 1] = a[end];
end--;
}
a[end+1] = key;//满足大小关系后插入到指定位置
}
}
int GetMid(int* a,int left,int right)//三数取中函数
{
int mid = (left + right) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])//说明a[left] > a[mid] > a[right]
return mid;
//走到这里说明a[mid]是最小值
else if (a[left] > a[right])
return right;
else
return left;
}
else //走到这里说明a[left] < a[mid]
{
if (a[left] > a[right])//说明a[mid] > a[left] > a[right]
return left;
//走到这里说明a[left]是最小值
else if (a[mid] > a[right])
return right;
else
return mid;
}
}
void QuickSort2(int* a, int left, int right)
{
if (left >= right)//只有一个元素或不存在，停止递归
return;
if ((right - left + 1) < 10)//如果区间小于10，停止递归，改用直接插入排序
InsertSort1(a + left, right - left + 1);//参数分别是区间起始地址，和区间元素个数
else
{
int midi = GetMid(a, left, right);//三个数取中间值的下标
Swap(&a[left], &a[midi]);
int tmp = a[left];//先将基准值存下来
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
while (begin < end && a[end] <= tmp)//右找大，找到停下来，填到左边的坑
end--;
if (begin < end)
a[begin] = a[end];
while (begin < end && a[begin] >= tmp)//左找小，找到停下来，填到右边的坑
begin++;
if (begin < end)
a[end] = a[begin];
}
a[begin] = tmp;//相遇之后，将保存的值填到相遇位置
keyi = begin;
Quicksort2(a, left, keyi - 1);
Quicksort2(a, keyi + 1, right);
}
}
前后指针法
void Swap(int* a, int* b)//交换函数
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void InsertSort1(int* a, int n)//插入排序升序
{
for (int i = 1; i <= n-1 ; i++)//控制要插入的元素个数
{
int key = a[i];
int end = i - 1;
while (end >= 0 && a[end] > key)//移动元素
{
a[end + 1] = a[end];
end--;
}
a[end+1] = key;//满足大小关系后插入到指定位置
}
}
int GetMid(int* a,int left,int right)//三数取中函数
{
int mid = (left + right) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])//说明a[left] > a[mid] > a[right]
return mid;
//走到这里说明a[mid]是最小值
else if (a[left] > a[right])
return right;
else
return left;
}
else //走到这里说明a[left] < a[mid]
{
if (a[left] > a[right])//说明a[mid] > a[left] > a[right]
return left;
//走到这里说明a[left]是最小值
else if (a[mid] > a[right])
return right;
else
return mid;
}
}
void QuickSort3(int* a, int left, int right)
{
if (left >= right)//只有一个元素或不存在，停止递归
return;
if ((right - left + 1) < 10)//如果区间小于10，停止递归，改用直接插入排序
InsertSort1(a + left, right - left + 1);//参数分别是区间起始地址，和区间元素个数
else
{
int midi = GetMid(a, left, right);//三个数取中间值的下标
Swap(&a[left], &a[midi]);
int keyi = left;
int prev = left;//前指针
int cur = left + 1;//后指针
while (cur <= right)//cur越界结束循环
{
//cur一直向后走，遇到小的值就停下，让prev向前走一步并交换
if (a[cur] < a[keyi] && prev++ != cur)//prev++ != cur是为了避免无用的原地交换
Swap(&a[prev], &a[cur]);
cur++;
}
Swap(&a[keyi], &a[prev]);//出循环，将prev停留位置与keyi位置进行交换
keyi = prev;
Quicksort3(a, left, keyi - 1);
Quicksort3(a, keyi + 1, right);
}
}
【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）