排序算法(4)之快速排序(2)
个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创排序算法(4)之快速排序(2)
收录于专栏【数据结构初阶】
本专栏旨在分享学习数据结构学习的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
前置说明
大家对快排还不是很了解的可以先去看--排序算法(4)之快速排序(1)-CSDN博客
1.快速排序的优化
上章节我们说到了快排有三个版本,分别是hoare版本,挖坑法和前后指针法,现在我就分别测试一下它们的性能.
测试代码
测试链接--912. 排序数组 - 力扣（LeetCode）
1.hoare版本
代码展示:
void Swap(int* n, int* m)
{
int p = *n;
*n = *m;
*m = p;
}
//hoare版本
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
//右边找小
while (begin < end && a[end] >= a[keyi])
{
end--;
}
//左边找大
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
keyi = begin;
//[left,keyi-1] keyi [keyi+1, right]
QuickSort1(a, left, keyi - 1);
QuickSort1(a, keyi + 1, right);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
(*returnSize) = numsSize;
int* array = (int*)malloc(sizeof(int)*(*returnSize));
for(int i = 0; i < numsSize; i++)
{
array[i] = nums[i];
}
QuickSort1(array, 0, numsSize-1);
return array;
}结果展示:
发现当数据有序时,会超出时间限制....
2.挖坑法
代码展示:
//挖坑法
void QuickSort2(int* a, int left, int right) {
if (left >= right)
return;
int key = a[left]; // 选择第一个元素作为基准值
int low = left, high = right;
while (low < high) {
// 从右向左找到第一个小于基准值key的元素
while (low < high && a[high] >= key)
high--;
if (low < high) {
a[low] = a[high]; // 使用 a[high] 的值填充 a[low] 的坑
low++;
}
// 从左向右找到第一个大于基准值key的元素
while (low < high && a[low] <= key)
low++;
if (low < high) {
a[high] = a[low]; // 使用 a[low] 的值填充 a[high] 的坑
high--;
}
}
a[low] = key; // 将基准值放入最终的坑中
int pivot = low; // 基准值的最终位置
QuickSort2(a, left, pivot - 1); // 对左子数组递归排序
QuickSort2(a, pivot + 1, right); // 对右子数组递归排序
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
(*returnSize) = numsSize;
int* array = (int*)malloc(sizeof(int)*(*returnSize));
for(int i = 0; i < numsSize; i++)
{
array[i] = nums[i];
}
QuickSort2(array, 0, numsSize-1);
return array;
}结果展示:
3.前后指针法
代码展示:
// 前后指针_快速排序
void QuickSort3(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
cur++;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
QuickSort3(a, left, keyi - 1);
QuickSort3(a, keyi + 1, right);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
(*returnSize) = numsSize;
int* array = (int*)malloc(sizeof(int)*(*returnSize));
for(int i = 0; i < numsSize; i++)
{
array[i] = nums[i];
}
QuickSort3(array, 0, numsSize-1);
return array;
}
结果显然,三个方法都没有通过,快排作为排序界的杠把子,难道就这么拉吗?都跟冒泡和选择排序一个挡位了,所以这里我们需要进一步优化快速排序.
1.1三数取中
以hoare版本为例,key都是取左端点.在有序序列中,原本分区的时间复杂度为O(logN)就会转换成O(N),这就会导致快速排序遇到有序或逆序时,时间复杂度就会变成O(N^2)
示例:
当key为中间值时,满足O(logN)的时间复杂度
当key为最小或最大值时 ,时间复杂度为O(N):
这里还有可能存在栈溢出的风险
所以快排里面有一个取中的方式,让key不会成为最大数或者时最小数,这里就介绍一下三数取中的方式:
这里的三数是指:left,right,midi((left+right)/2) ,我们需要在这三个数中找出中间值并赋值给key
代码展示:
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
// left midi right
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}1.2小区间优化
快速排序类似于二叉树递归的过程,越处于底层的数据会被重复调用多次,所以可以当划分的数列小于10时,可.直接调用其他排序,比如插入排序,直接排好,能减少很大一部分数据的递归调用,
代码展示:
// 小区间优化，不再递归分割排序，减少递归的次数
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);
}
void InsertSort(int* a, int n)
{
// [0, n-1]
for (int i = 0; i < n - 1; i++)
{
// [0, n-2]是最后一组
// [0,end]有序 end+1位置的值插入[0,end]，保持有序
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}优化后的快速排序
void InsertSort(int* a, int n)
{
// [0, n-1]
for (int i = 0; i < n - 1; i++)
{
// [0, n-2]是最后一组
// [0,end]有序 end+1位置的值插入[0,end]，保持有序
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void Swap(int* n, int* m)
{
int p = *n;
*n = *m;
*m = p;
}
//hoare版本
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
// left midi right
if (a[left] == a[midi] && a[left] == a[midi] && a[midi] == a[right])
return midi;
else if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
// 避免有序情况下，效率退化
//三数取中
//小区间优化
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
// 小区间优化，不再递归分割排序，减少递归的次数
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
// 右边找小
while (begin < end && a[end] >= a[keyi])
{
--end;
}
// 左边找大
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
keyi = begin;
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}
InsertSort 函数
- 实现了插入排序算法，将传入的数组
a按升序排序。- 在外部循环中，逐步将数组分为已排序部分和未排序部分。
- 内部循环通过比较当前元素和已排序部分的元素，找到合适位置插入当前元素，保证数组的有序性。
Swap 函数：
辅助函数，用于交换两个整数指针所指向的值。
GetMidi 函数：
- 用于选择三个元素中间值作为快速排序的枢轴（pivot）。
- 考虑了数组左端、中间和右端三个位置的元素，确保选择合适的枢轴来避免最坏情况下的效率问题。
QuickSort 函数：
- 实现了快速排序算法。
- 在大于等于10个元素时，采用快速排序策略，选择枢轴、分割数组、递归排序子数组。
- 小于10个元素时，采用插入排序优化，减少递归深度，提高效率。
2.快速排序的非递归实现
上面说到过,由于快速排序是递归实现的,在遇到有序或者无序的序列会有栈溢出的风险,所以快速排序的非递归实现是有必要的.
思路:
利用栈后进先出的特点,模拟快速排序的过程
代码展示:
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
int keyi = PartSort2(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}分析:
数据结构和函数调用：
ST是一个栈结构，具备以下操作：
STInit(&st)：初始化栈st。STPush(&st, val)：将val压入栈st。STTop(&st)：获取栈顶元素但不弹出。STPop(&st)：弹出栈顶元素。非递归快速排序实现：
- 主要逻辑通过栈来维护排序区间的边界。
- 初始时，将整个数组的左右边界分别压入栈中，表示整个数组需要排序。
- 进入循环，不断从栈中取出左右边界，执行分区操作（
PartSort2函数），得到分区点keyi。- 根据分区点
keyi，将数组分为[begin, keyi-1]、keyi、[keyi+1, end]三部分。- 如果左边界小于
keyi - 1，说明左侧还有未排序部分，将其左右边界压入栈中。- 如果右边界大于
keyi + 1，同理将其左右边界压入栈中。循环结束条件：
当栈为空时，说明所有区间已经排序完成，循环结束。
PartSort2函数：它的作用是进行数组的分区操作，将数组按照某个基准值分成左右两部分，并返回基准值最终的位置。(可以是hoare,挖坑法,前后指针法)
完整代码:
栈
Stack.h
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);
// 入栈 出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
// 取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);Stack.c
#include"Stack.h"
// 初始化和销毁
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
// top指向栈顶数据的下一个位置
pst->top = 0;
// top指向栈顶数据
//pst->top = -1;
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
// 入栈 出栈
void STPush(ST* pst, STDataType x)
{
assert(pst);
// 扩容
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
// 20:08继续
// 取栈顶数据
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top - 1];
}
// 判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
// 获取数据个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}Sort.c
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
// left midi right
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
// hoare
int PartSort1(int* a, int left, int right)
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
// 右边找小
while (begin < end && a[end] >= a[keyi])
{
--end;
}
// 左边找大
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
return begin;
}
// 前后指针
int PartSort2(int* a, int left, int right)
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
// 避免有序情况下，效率退化
// 1、随机选key
// 2、三数取中
//
//void QuickSort(int* a, int left, int right)
//{
//if (left >= right)
//return;
//
//int keyi = PartSort1(a, left, right);
//
// [left, keyi-1] keyi [keyi+1, right]
//QuickSort(a, left, keyi - 1);
//QuickSort(a, keyi + 1, right);
//}
#include"Stack.h"
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
int keyi = PartSort2(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}
3.总结
非递归与递归快速排序的对比
- 非递归版本避免了递归调用的额外开销，使用栈来存储分割点，节省了空间。
- 在处理大规模数据时，递归深度可能导致栈溢出，而非递归版本则能够更好地应对这种情况。
原文地址：https://blog.csdn.net/wer24_25/article/details/140518371
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！