个人主页: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.总结
非递归与递归快速排序的对比
- 非递归版本避免了递归调用的额外开销,使用栈来存储分割点,节省了空间。
- 在处理大规模数据时,递归深度可能导致栈溢出,而非递归版本则能够更好地应对这种情况。