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