【排序算法】实现快速排序值（霍尔法三指针法挖坑法优化随即选key中位数法小区间法非递归版本）

2024-03-24 00:20
文章标签 算法 实现 指针 优化 快速 排序 版本 递归 key 区间 中位数 霍尔 挖坑 随即 法非 法三 法小

本文主要是介绍【排序算法】实现快速排序值（霍尔法三指针法挖坑法优化随即选key中位数法小区间法非递归版本），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

请添加图片描述

文章目录

  • 📝快速排序
    • 🌠霍尔法
    • 🌉三指针法
    • 🌠挖坑法
      • ✏️优化快速排序
  • 🌠随机选key
    • 🌉三位数取中
  • 🌠小区间选择走插入，可以减少90%左右的递归
  • 🌉 快速排序改非递归版本
  • 🚩总结

📝快速排序

快速排序是一种分治算法。它通过一趟排序将数据分割成独立的两部分,然后再分别对这两部分数据进行快速排序。

本文将用3种方法实现：

🌠霍尔法

霍尔法是一种快速排序中常用的单趟排序方法，由霍尔先发现。

它通过选定一个基准数key（通常是第一个元素），然后利用双指针left和right的方式进行排序，right指针先找比key基准值小的数，left然后找比key基准值大的数，找到后将两个数交换位置，同时实现大数右移和小数左移，当left与right相遇就排序完成，然后将下标key的值与left交换，返回基准数key的下标，完成了单趟排序。这一过程使得基准数左侧的元素都比基准数小，右侧的元素都比基准数大。

如图动图展示：
请添加图片描述
以下是单趟排序的详解图解过程：

  • begin和end记录区间的范围，left记录做下标，从左向右遍历，right记录右下标，从右向左遍历，以第一个数key作为基基准值
    在这里插入图片描述
  • 先让right出发，找比key值小的值，找到就停下来
    在这里插入图片描述
  • 然后left再出发，找比key大的值，若是找到则停下来，与right的值进行交换
    在这里插入图片描述
  • 接着right继续找key小的值，找到后才让left找比key大的值，直到left相遇right，此时left会指向同一个数
    在这里插入图片描述
    在这里插入图片描述
  • 将left与right指向的数与key进行交换，单趟排序就完成了，最后将基准值的下标返回
    在这里插入图片描述
    为啥相遇位置比key要小->右边先走保证的
  1. L遇R: R先走,R在比key小的位置停下来了，L没有找到比key大的，就会跟R相遇相遇位置R停下的位置，是比key小的位置
  2. R遇L:第一轮以后的，先交换了，L位置的值小于key,R位置的值大于key ，R启动找小，没有找到，跟L相遇了，相遇位置L停下位置，这个位置比key小
  • 第一轮R遇L，那么就是R没有找到小的，直接就一路左移，遇到L，也就是key的位置

代码实现

void Swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}//Hoare经典随机快排
void QuickSort1(int* a, int left, int right)
{// 如果左指针大于等于右指针,表示数组为空或只有一个元素,直接返回if (left >= right)return;// 区间只有一个值或者不存在就是最小子问题int begin = left, end = right;// begin和end记录原始整个区间// keyi为基准值下标,初始化为左指针int keyi = left;// 循环从left到rightwhile (left < right){// right先走，找小，这里和下面的left<right一方面也是为了防止,right一路走出区间，走到left-1越界while (left<right && a[right] >= a[keyi]){--right;}// 左指针移动,找比基准值大的元素   while (left<right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}// 交换左右指针所指元素Swap(&a[left], &a[keyi]);// 更新基准值下标keyi = left;// 递归排序左右两部分//[begin , keyi-1]keyi[keyi+1 , end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}

🌉三指针法

定义一个数组，第一个元素还是key基准值，定义前指针prev指向第一个数，后指针cur指向第二个数，让cur走，然后遍历数组，cur找到大于等于key基准值的数，cur++让cur向前走一步。当cur指针小于key基准值时，后指针加一走一步（++prev），然后交换prev和cur所指的值进行交换，因为这样cur一直都是小于key的值，让他继续向前不断找大的，而prev一直在找小的。依次类推，到cur遍历完数组，完成单趟排序。
如此动图理解：
请添加图片描述
简单总结：
在这里插入图片描述
以下是单趟排序的详解图解过程：

  1. 一开始，让prev指向第一个数，cur指向prev的下一位，此时cur位置的数比key基准值小，所以prev加一后，与cur位置的数交换，由于此时prev+1 == cur，自己跟自己交换，交换没变，完了让cur++走下一个位置。
    在这里插入图片描述
    紧接着：
    在这里插入图片描述

  2. cur继续前进，此时来到了7的位置，大于key的值6，cur++继续向前走，来到9位置，9还是大于6，OK ! 我cur再cur++，来到3的位置，也是看到cur与prev拉开了距离，所以他又叫前后指针，这就体现出来，往下看–》
    在这里插入图片描述
    在这里插入图片描述

  3. 此时此刻，我cur的值小于key基准值，先让prev走一步，然后与cur的值交换交换
    在这里插入图片描述
    在这里插入图片描述

  4. 同样的步骤，重复上述遍历，直到遍历完数组

在这里插入图片描述在这里插入图片描述

  1. cur遍历完数组后，将交换prev的值key的基准值进行交换，交换完，将key的下标更新为prev下标的，然后返回key下标，完成单趟。
    在这里插入图片描述
    代码如下：
void QuickSort2(int* a, int left, int right)
{// 如果左指针大于等于右指针,表示数组为空或只有一个元素,直接返回if (left >= right)return;// keyi为基准值下标,初始化为左指针int keyi = left;// prev记录每次交换后的下标int prev = left;// cur为遍历指针int cur = left+1;// 循环从左指针+1的位置开始到右指针结束while (cur <= right){// 如果cur位置元素小于基准值,并且prev不等于cur// 就将prev和cur位置元素交换// 并将prev后移一位if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;//不管是cur小于还是大于，是否交换,cur都后移一位      cur都++}// 将基准值和prev位置元素交换Swap(&a[keyi], &a[prev]);// 更新基准值下标为prevkeyi = prev;// 递归调用左右两部分// [left, keyi-1]keyi[keyi+1, right]QuickSort2(a, left, keyi - 1);QuickSort2(a, keyi + 1, right);
}

🌠挖坑法

挖坑法也是快速排序的一种单趟排序方法。它也是利用双指针，但与霍尔法不同的是，挖坑法在每次找到比基准数小的元素时，会将其值填入基准数所在的位置，然后将基准数所在的位置作为“坑”，接着从右边开始找比基准数大的元素填入这个“坑”，如此往复，直到双指针相遇。最后，将基准数填入最后一个“坑”的位置。
请添加图片描述
挖坑法思路：
您提到的挖坑法是一种快速排序的实现方式。

  1. 选择基准值(key),将其值保存到另一个变量pivot中作为"坑"
  2. 从左往右扫描,找到小于基准值的元素,将其值填入"坑"中,然后"坑"向右移动一个位置
  3. 从右往左扫描,找到大于或等于基准值的元素,将其值填入移动后的"坑"中
  4. 重复步骤2和3,直到左右两个指针相遇
  5. 将基准值填入最后一个"坑"位置
  6. 对基准值左右两边递归分治，【begin,key-1】key 【key+1，end】重复上述过程,实现递归排序

与双指针法相比,挖坑法在处理基准值时使用了额外的"坑"变量,简化了元素交换的操作,但思想都是利用基准值将数组分割成两部分。

代码如下：

//挖坑法
void Dig_QuickSort(int* a, int begin, int end)
{if (begin >= end)return;//一趟的实现int key = a[begin];int pivot = begin;int left = begin;int right = end;while (left < right){while (left < right && a[right] >= key){right--;}a[pivot] = a[right];pivot = right;while (left < right && a[left] <= key){left++;}a[pivot] = a[left];pivot = left;}//补坑位a[pivot] = key;//递归分治//[begin, piti - 1] piti [piti + 1, end]Dig_QuickSort(a, begin, pivot - 1);Dig_QuickSort(a, pivot + 1, end);
}

当你讨厌挖左边的坑，可以试试右边的坑😉：
代码如下：

// 交换元素
void swap(int* a, int* b) 
{int t = *a;*a = *b;*b = t;
}// 分区操作函数
int partition(int arr[], int low, int high) 
{// 取最后一个元素作为基准值int pivot = arr[high];// 初始化左右索引  int i = (low - 1);// 从左到右遍历数组for (int j = low; j <= high - 1; j++) {// 如果当前元素小于或等于基准值if (arr[j] <= pivot) {// 左索引向右移动一位i++;// 将当前元素与左索引位置元素交换  swap(&arr[i], &arr[j]);}}// 将基准值和左索引位置元素交换swap(&arr[i + 1], &arr[high]);// 返回基准值的最终位置return (i + 1);
}// 快速排序主函数
void quickSort(int arr[], int low, int high) 
{// 如果低位索引小于高位索引,表示需要继续排序if (low < high) {// 调用分区函数,得到基准值的位置int pi = partition(arr, low, high);// 对基准值左边子数组递归调用快速排序quickSort(arr, low, pi - 1);// 对基准值右边子数组递归调用快速排序   quickSort(arr, pi + 1, high);}
}// 测试
int main() 
{// 测试数据int arr1[] = { 5,3,6,2,10,1,4 };int n1 = sizeof(arr1) / sizeof(arr1[0]);quickSort(arr1, 0, n1 - 1);// 输出排序结果for (int i = 0; i < n1; i++){printf("%d ", arr1[i]);}printf("\n");int arr2[] = { 5,3,6,2,10,1,4,29,44,1,3,4,5,6 };int n2 = sizeof(arr2) / sizeof(arr2[0]);quickSort(arr2, 0, n2 - 1);// 输出排序结果for (int i = 0; i < n2; i++){printf("%d ", arr2[i]);}printf("\n");// 测试数据int arr3[] = { 10,1,4,5,3,6,2,1 };int n3 = sizeof(arr3) / sizeof(arr3[0]);quickSort(arr3, 0, n3 - 1);// 输出排序结果for (int i = 0; i < n3; i++){printf("%d ", arr3[i]);}printf("\n");return 0;
}

运行启动：
在这里插入图片描述

✏️优化快速排序

🌠随机选key

为什么要使用随机数选取key?
避免最坏情况,即每次选择子数组第一个或最后一个元素作为key,这样会导致时间复杂度退化为O(n^2)。
随机化可以减少排序不均匀数据对算法性能的影响。
相比固定选择第一个或最后一个元素,随机选择key可以在概率上提高算法的平均性能。

这里是优化快速排序使用随机数选取key的方法:

  1. 在划分子数组前,随机生成一个[left,right]区间中的随机数randi，
  2. 将随机randi处的元素与区间起始元素left交换
  3. 使用这个随机索引取出子数组中的元素作为keyi。

随机选key逻辑代码：

//快排，随机选key
void QuickSort3(int* a, int left, int right) 
{//区间只有一个值或者不存在就是最小子问题if (left >= right)return;int begin = left, end = right;//选[left,right]区间中的随机数做keyint randi = rand() % (right - left + 1);  //rand() % N生成0到N-1的随机数randi += left;  //将随机索引处的元素与区间起始元素交换Swap(&a[left], &a[randi]);//用交换后的元素作为基准值keyiint keyi = left;while (left < right) {//从右向左找小于key的元素while (left < right && a[right] >= a[keyi]) {--right;}//从左向右找大于key的元素      while (left < right && a[left] <= a[keyi]) {++left; }//交换元素Swap(&a[left], &a[right]);}//将基准值与交叉点元素交换Swap(&a[left], &a[keyi]);keyi = left;//递归处理子区间QuickSort3(a, begin, keyi - 1);QuickSort3(a, keyi + 1, end);
}

🌉三位数取中

有无序数列数组的首和尾后，我们只需要在首，中，尾这三个数据中，选择一个排在中间的数据作为基准值(keyi)，进行快速排序，减少极端情况,进一步提高快速排序的平均性能。
代码实现：

// 三数取中  left  mid  right
// 大小居中的值，也就是不是最大也不是最小的
int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}

取中的返回函数接收：

		int begin = left, end = right;// 三数取中int midi = GetMidi(a, left, right);//printf("%d\n", midi);Swap(&a[left], &a[midi]);

整体函数实现：

//三数取中  left  mid  right
//大小居中的值，也就是不是最大，也不是最小的
int GetMid(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if(a[left] > a[right]){return left;}else{return  right;}}else//a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}void QuickSort4(int* a, int left, int right)
{if (left >= right)return;int begin = left, end = right;//三数取中int midi = GetMid(a, left, right);//printf("%d\n",midi);Swap(&a[left], &a[midi]);int keyi = left;while (left < right){while (left < right && a[right] >= a[keyi]){--right;}while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;QuickSort4(a, begin, keyi - 1);QuickSort4(a, keyi + 1, end);}

🌠小区间选择走插入，可以减少90%左右的递归

对于小区间,使用插入排序而不是递归进行快速排序。
在快速排序递归中,检查子问题的区间长度是否小于某个阈值(如10-20)，如果区间长度小于阈值,则使用插入排序进行排序，否则使用快速排序递归进行划分。
而这个(如10-20)刚好可以在递归二叉树中体现出来。
如图：
在这里插入图片描述
当然从向下建堆优于向上建堆，也可以体现出来：
在这里插入图片描述

优点在于:对于小区间,插入排序效率高于快速排序的递归开销大部分数组元素位于小区间中，采用插入排序可以省去90%左右的递归调用，但整体数组规模大时,主要工作还是由快速排序完成

与三数取中进行合用

void QuickSort5(int* a, int left, int right)
{if (left >= right)return;// 小区间选择走插入，可以减少90%左右的递归if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);}else{int begin = left, end = right;//三数取中int midi = GetMid(a, left, right);//printf("%d\n",midi);Swap(&a[left], &a[midi]);int keyi = left;while (left < right){while (left < right && a[right] >= a[keyi]){--right;}while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;QuickSort4(a, begin, keyi - 1);QuickSort4(a, keyi + 1, end);}
}

🌉 快速排序改非递归版本

逻辑原理：
非递归版本的快速排序利用了栈来模拟递归的过程。它的基本思想是：将待排序数组的起始和结束位置压入栈中，然后不断出栈，进行单趟排序，直到栈为空为止。在单趟排序中，选取基准数，将小于基准数的元素移到基准数左边，大于基准数的元素移到基准数右边，并返回基准数的位置。然后根据基准数的位置，将分区的起始和结束位置入栈，继续下一轮排序，直到所有子数组有序。
在这里插入图片描述

代码实现步骤:

  1. 初始化一个栈用于保存待排序子数组的起始和结束位置。
  2. 将整个数组的起始和结束位置压入栈中。
  3. 循环执行以下步骤，直到栈为空：
    出栈，获取当前待排序子数组的起始和结束位置。
    进行单趟排序，选取基准数，并将小于基准数的元素移到左边，大于基准数的元素移到右边。
    根据基准数的位置，将分区的起始和结束位置入栈。
  4. 排序结束。

代码实现

#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 = begin;int prev = begin;int cur = begin + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;//[begin,keyi-1]keyi[keyi+1,end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (keyi - 1 > begin){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}

以下是栈的实现：
Stack.c

#include"Stack.h"void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}// 栈顶
// 11:55
void STPush(ST* ps, STDataType x)
{assert(ps);// 满了， 扩容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

栈的头文件实现：

#pragma once#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* ps);
void STDestroy(ST* ps);// 栈顶
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);

🚩总结

快速排序的特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定

快排可以很快，你的点赞也可以很快，哈哈哈，感谢💓 💗 💕 💞，喜欢的话可以点个关注，也可以给博主点一个小小的赞😘呀
请添加图片描述

这篇关于【排序算法】实现快速排序值（霍尔法三指针法挖坑法优化随即选key中位数法小区间法非递归版本）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/839983。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2