基础排序算法【快速排序+优化版本+非递归版本】

news/2024/12/22 23:15:17/

基础排序算法【快速排序+优化版本+非递归版本】💯💯💯

  • ⏰【快速排序】
    • ◽1.hoare法
    • ◽2.挖坑法
    • ◽3.前后指针法
    • ◽4.特性总结
  • ⏰【优化版本】
    • ◽1.随机选key
    • ◽2.三路取中
    • ◽3.小区间优化
  • ⏰【非递归版本】
  • ⏰【测试效率】
    • 排序OJ(可使用各种排序跑这个OJ)

在这里插入图片描述 请添加图片描述

⏰【快速排序】

快速排序是Hoare提出的一种二叉树结构的交换排序方法
> 基本思想：

任取待排序元素序列中的某个元素作为基准值key，按照该基准值将待排序列分成两个子序列，左子序列都比key小，右基准值都比key大。然后左右子序列重复上面的操作，直到所有元素都排列到相应的位置上为止。

而为什么说它是一种二叉树结构的交换排序方法呢？
是因为它的排序框架和二叉树的前序遍历规则十分相似。

进行一趟排序的效果是什么？

将小于key的值都放到key的左边，大于key的值都放到key的右边。

key将序列分成两个左右子序列，再对左右子序列重复上面的操作，就可以实现排序。而这一操作可以由递归实现。对左右子序列递归，直到没有子序列为止。

【快排基本框架】
void QuickSort(int *a, int left, int right)
{if (left>=right)return;// 按照基准值key对a数组的 [left, right)区间中的元素进行划分int keyi = partion(a, left, right);// 划分成功后以key为边界形成了左右两部分 [left, keyi-1] 和 [keyi+1, right)// 递归排[left, keyi-1]左子序列QuickSort(a, left, keyi-1);// 递归排[keyi+1+1, right)右子序列QuickSort(keyi, keyi + 1, right);
}

我们发现它与二叉树的前序遍历规则非常像，前序遍历是先访问根节点，然后再到左子树，右子树。
而这里类似，先将key排序好，然后再到左子序列，右子序列中去。所以我们在写递归框架时，可以想象二叉树前序遍历规则即可快速写出来。

◽1.hoare法

> 如何找key？

key的选值没有规定必须选哪一个，通常序列的最左边或者最右边作为key。

> 单趟排序：
单趟排序的效果也就是让key到正确的位置上去，key左边都比它小，右边都比它大。那如何做到这样呢？

  • 1.左边作key，右边先走。

  • 2.右边找比key小的值，左边找比key大的值。

  • 3.当两边都找到了就交换。

  • 4.当左边和右边相遇，将key和相遇点交换
    在这里插入图片描述

在这里插入图片描述

void Quicksort1(int*a,int left,int right)//需要区间范围{       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]);}//最后将key值与left和right相遇位置交换Swap(&a[keyi], &a[left]);
}

> 细节1

在找小找大的过程中，要注意lleft和right的范围，虽然在外面已经控制left小于right，但找小和找大的过程不受该限制，所以还需要判断一下。

> 细节2

在找小和找大的过程中，当遇到与key大小一样的值，该怎么办，当遇到与key一样的值时，想一下，这样的值在key的左边和右边都不影响结果，所以直接跳过即可，所以在找小找大时遇到相等的也跳过去。

> 问题1：为什么左边作key右边先走

> 问题2：为什么最后相遇点比key小

单趟排序写好了接下来就是写总趟了。
其实单趟写完后，剩下的就简单多了，单趟将key放入正确的位置，并且将序列分割成两个区间，在左区间中再选取个key，放入正确位置后，又分割成两个区间，在去左子序列中分割，直到最后子序列无法分割，递归就往回返。当左区间有序后再去分割右区间，右区间选key后再分割，跟左区间操作一致。
在这里插入图片描述

void Quicksort1(int*a,int left,int right)//需要区间范围
{//递归结束条件--子序列无法再分割if (left >= right)return;int keyi = left;int begin = left;//递归需要用到左右区间，需要改动区间的值，这里我们保存左右区间的值。int end = right;while (left < right){//右找小while (left<right && a[right]>=a[keyi])right--;//左找大while (left < right && a[left] <= a[keyi])left++;//交换右边的小和左边的大Swap(&a[left], &a[right]);}//最后将key值与left和right相遇位置交换Swap(&a[keyi], &a[left]);keyi = left;//要将最后keyi的位置更新下//begin   keyi-1 key keyi+1   endQuicksort1(a, begin, keyi - 1);//递归左区间Quicksort1(a, keyi + 1, end);//递归右区间
}

◽2.挖坑法

> 单趟排序：
挖坑法，本质上也是选出一个key，最后让key的左边都小于key，key的右边都大于key。

  • 1.先将key值保存下来，那key原先的位置上就形成一个坑

  • 2.右边找小，找到后将小的放入坑内，自己位置上形成坑

  • 3.左边找大，找到后将大的放入坑内，自己位置上形成坑

  • 4.最后左右相遇，将key的值放入坑内。

挖坑法其实和霍尔的方法目的是一样的，都是将小的甩到左边，大的甩到右边。只是方法不同。

在这里插入图片描述

在这里插入图片描述

    int key = a[left];int hole = begin;while (left < right){//右边找小while (left < right && a[right] >= key)--right;//找到之后将它甩到坑里，自己形成新的坑a[hole] = a[right];hole = right;while (left < right && a[left] <= key)++left;//找到之后将它甩到坑里，自己形成新的坑a[hole] = a[left];hole = left;}//最后left和right相遇，将key插入到坑里a[hole] = key;

单趟排序完后的结果也是让key的左边都比key小，key的右边都比key大。
而接下来的总趟跟霍尔的一样，都是递归左右子序列即可。

//2.挖坑法
void Quicksort2(int* a, int left, int right)
{if (left >= right)return;//将key的值保留int key = a[left];int begin = left;int end = right;int hole = begin;//三数取中，不是取数组中间的数，而是取三个数中中间的数--begin mid endint midi = Midi(a, begin, end);Swap(&key, &a[midi]);while (left < right){//右边找小while (left < right && a[right] >= key)--right;//找到之后将它甩到坑里，自己形成新的坑a[hole] = a[right];hole = right;while (left < right && a[left] <= key)++left;//找到之后将它甩到坑里，自己形成新的坑a[hole] = a[left];hole = left;}//最后left和right相遇，将key插入到坑里a[hole] = key;Quicksort2(a, begin, hole - 1);//递归左子序列Quicksort2(a, hole + 1, end);//递归右子序列}

◽3.前后指针法

第三种方法：前后指针法，顾名思义有两个指针cur和prev，该思路与霍尔和挖坑法截然不同。
它是将大的数据往右"推"，将大的数据翻滚到右边去，小的数据交换到左边去。

> 单趟排序：

  • 1.刚开始prev指向起始位置(最左边作key)，cur指向prev后面的位置

  • 2.cur用来找小，当cur往后找小时，找到之后，prev++，再将prev指向的元素和cur交换，cur再++。

  • 3.当cur遍历完序列后，将key直接和prev指向的数据交换即可。
    在这里插入图片描述

在这里插入图片描述

void Quicksort3(int* a, int left, int right)
{if (left >= right)return;int keyi = left;//最左边作keyint cur = left + 1;//cur指向prev的后面int prev = left;//prev指向序列起始位置//cur用来找小，当cur找到小时，prev++，prev的值与cur的值交换，cur继续往后走while (cur <= right)//当cur遍历完序列才可以结束{if (a[cur] <= a[keyi] && ++prev != cur)//如果cur找到比key小的数，那cur和prev直接的就是紧挨着，prev++后就会跟cur一样那指向的值也是一样，那就没有必要交换。当cur没到到比key小的数时，prev和cur之间就会出现距离。{Swap(&a[cur], &a[prev]);}++cur;//不管cur找没找到比key小的数，cur都要走的}Swap(&a[prev], &a[keyi]);//最后再将prev指向的数与key交换，这个数一定是比key要小的。keyi = prev;//交换完后需要更新key的位置。以便递归使用。
}

当一趟结束之后，将key排在合适的位置，就将序列分成两个子序列了，那再对两个子序列做相同的操作即可，用递归分治思想。

void Quicksort3(int* a, int left, int right)
{if (left >= right)return;int keyi = left;int cur = left + 1;int prev = left;//cur用来找小，当cur找到小时，prev++，prev的值与cur的值交换，cur继续往后走while (cur <= right){if (a[cur] <= a[keyi] && ++prev!= cur){Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;//更新key的位置Quicksort3(a, begin, keyi - 1);//递归左子序列Quicksort3(a, keyi + 1,end);//递归右子序列
}

> 注意：
prev与cur之间位置上有两种关系，要么prev紧跟着cur。
要么prev和cur之间隔着一段数据，该数据就是比prev大的数据。
当prev紧挨着cur的时，prev++就跳到cur的位置上去了，那prev的值和cur的值交换就没有意义了，因为它们代表的是同一个值。也就是如果一开始cur找小找到了，那么prev和cur就是紧挨着，当一旦找到一个比key大的数时，它们之间就会出现距离，不再紧挨着了。

◽4.特性总结

1.快速排序整体比其他排序都要好，所以才敢叫快排
2.时间复杂度O(N*logN)
在这里插入图片描述
3.空间复杂度：O(logN)
4.稳定性：不稳定。

⏰【优化版本】

想一想快排的时间复杂度是多少呢？如果我们从最坏情况讨论的话，当序列完全有序和完全逆序情况下，快速排序效率最低。
在这里插入图片描述
虽然从最后的情况下来看快速排序的时间复杂度为O(N^2)但是它是可以抢救的，它可以通过某种方法来提高效率，从而从O(N ^2)变成O(N*logN)。
在这里插入图片描述

◽1.随机选key

在这里插入图片描述

	//随机选keyint randi = rand() % (right - left) + begin;Swap(&a[keyi], &a[randi]);

在单趟排序中：

void Quicksort1(int*a,int left,int right)//需要区间范围
{//递归结束条件if (left >= right)return;int keyi = left;int begin = left;int end = right;//随机选keyint randi = rand() % (right - left) + begin;Swap(&a[keyi], &a[randi]);while (left < right){//右找小while (left<right && a[right]>=a[keyi])right--;//左找大while (left < right && a[left] <= a[keyi])left++;//交换右边的小和左边的大Swap(&a[left], &a[right]);}//最后将key值与left和right相遇位置交换Swap(&a[keyi], &a[left]);keyi = left;

随机选key的意义，本来最左边可能是最小值或者最大值，有可能会遇到有序情况和完全逆序情况，但是随机选key大大降低了这种可能，从而提高效率。

◽2.三路取中

三路哪三路呢？
左下标，右下标，和中间下标。
取中是什么意思？
我们要取的是三个下标中所代表的值是中间值的那个数。
找到之后，就将该中间值与最左边的key交换。那么key的值就不可能为最小值或者最大值。
这样就完全确定key不是最小值了，不像随机选key还有一丢丢的可能。
所以三路取中更科学更有可用性。

怎么取出三个数中的中中间值呢？就比较即可。

int Midi(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[great]{return mid;//mid的是中间值下标}else//a[left]>a[mid]且a[right]>a[mid] 左右两个值都大于中间的，那左右两个值再比较得中间{if (a[left] > a[right]){return right;//right是两个数中小的，也就是三个数中中间数}else{return left;//否则left就是中间数的下标}}}else//a[left]<a[mid]{if (a[mid] < a[right]){return mid;}else//a[left]<a[mid]且a[right]<a[mid]{if (a[left] > a[right]){return left;}else{return right;}}}
}

最后返回的都是三个数中中间值。

利用三路取中单趟排序：

void Quicksort1(int*a,int left,int right)//需要区间范围
{//递归结束条件if (left >= right)return;int keyi = left;//三数取中，不是取数组中间的数，而是取三个数中中间的数--begin mid endint midi=Midi(a, left, right);Swap(&a[keyi], &a[midi]);//将中间值与key交换，key就永远不可能为最小值或最大值了。while (left < right){//右找小while (left<right && a[right]>=a[keyi])right--;//左找大while (left < right && a[left] <= a[keyi])left++;//交换右边的小和左边的大Swap(&a[left], &a[right]);}//最后将key值与left和right相遇位置交换Swap(&a[keyi], &a[left]);keyi = left;

◽3.小区间优化

我们想一颗满二叉树它最后一层节点的个数是多少？
如果这颗数的深度为h，那么最后一层的节点数就是2^(h-1)而这么多节点，这么多节点需要大量的栈帧，而且最后几层的节点数是总课数节点的一半还多。而且最后一层要递归很多次才可以到达，这样的递归的缺点就显现出来了。所以有些人就在想当递归到一定程度就不再递归，用另一种方式进行排序。
也就是当区间不断的缩小，缩小到一定范围，用直接插入排序的效果要比递归好，这样也可以做到优化效果。

因为对于数据量小的，虽然区间多，但插入排序嘎嘎快，对于快速排序这些区间需要递归很多次才可以完成所以使用这样的小区间优化来提高效率。

//3.前后指针方法
void Quicksort3(int* a, int left, int right)
{if (left >= right)return;//三数取中，不是取数组中间的数，而是取三个数中中间的数--begin mid endint midi = Midi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int cur = left + 1;int prev = left;//cur用来找小，当cur找到小时，prev++，prev的值与cur的值交换，cur继续往后走while (cur <= right){if (a[cur] <= a[keyi] && a[++prev] != a[cur]){Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;//小区间优化--当区间小时，直接使用插入排序if(right-left+1>10)//当区间大于10时，仍然进行递归{Quicksort3(a, left, keyi - 1);Quicksort3(a, keyi + 1,right);}else{InsertSort(a+left,right-left+1);//注意这里是将a+left传过去，因为不一定就是左区间，还可能是右区间}
}

⏰【非递归版本】

递归真正的问题是什么？

  • 1.效率不行，但现阶段效率方面都差不多

  • 2.深度太深，系统跑不过去会造成栈溢出。

因为递归是要消耗空间的，递归一次就需要建立一个栈帧，最后栈区域的内存不够了，就会造成栈溢出。
所以我们需要掌握这样的能力：将递归改成非递归。
递归改成非递归有两种思路：

  • 1.直接改成循环—如斐波那契数列

  • 2.使用(栈)辅助来改循环。

这里我们将会用栈来辅助将递归改成循环。
> 基本思路：
我们要思考排序递归函数里到底存放的是什么，每次递归什么发生了改变？对！
其实本质就是区间
每次递归函数区间都会被分割，缩小。所以我们在栈里存放的也就是区间通过栈里的区间对序列进行分割，不再使用递归分治的方法分割区间。

  • 1.首先将最初的序列左右区间入栈，要想使用左区间需要先将右区间入栈，然后左区间再入栈（栈的特点）。

  • 2.然后就开始使用栈来辅助修改循环。当栈不为空栈时，就将栈里区间出栈，一次出两个值，也就是左右区间。当左右区间出栈后，我们就可以根据左右区间对序列进行单趟排序选出key，key就将序列分成两个子序列，而这两个子序列又代表着两个区间，再将它们入栈，注意要先将右子序列区间入栈再将左序列区间入栈，然后再出栈重复上面的操作。

  • 3.当出栈的区间拿来分割子序列时，子序列无法再分割了没有区间，就不用入栈。

void QuickSortNoN(int* a, int left, int right)
{Stack st;StackInit(&st);//初始化栈//首先将序列的左右区间入栈StackPush(&st, right);StackPush(&st, left);//开始使用栈辅助修改循环while (!StackEmpty(&st)){//当栈不为空时，将区间出栈--出两个元素int begin = StackTop(&st);int end = StackTop(&st);//将区间出来后，就利用改区间对序列进行单趟排序int midi = Midi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int cur = left + 1;int prev = left;//cur用来找小，当cur找到小时，prev++，prev的值与cur的值交换，cur继续往后走while (cur <= right){if (a[cur] <= a[keyi] && a[++prev] != a[cur]){Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;//[left   keyi-1]  [keyi+1  right] //单趟排序完后选出key ，而key又将序列分成两个子序列，相当于两个区间，将这两个区间入栈，注意先将右区间入栈，再入左区间//还有要注意的是，当子序列无法再分割时，无法产生区间时就不入栈if (left < keyi - 1){StackPush(&st, right);STackPush(&st, keyi + 1);}if (keyi + 1 < right){StackPush(&st, keyi - 1);StackPush(&st, left);}}//当栈里没有区间时序列就已经排序好了。
}

⏰【测试效率】

接下来就是测试快排的效率如何了。
我们可以拿希尔排序进行比较，也可以拿快排自己的三种方法进行比较。

void QuickTest1()
{srand(time(0));const int N = 1000000;int* a2 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a2[i] = rand();}int begin1 = clock();Quicksort1(a2, 0, N - 1);int end1 = clock();printf("霍尔-Quicksort:%d\n", end1 - begin1);free(a2);
}
void QuickTest2()
{srand(time(0));const int N = 1000000;int* a2 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a2[i] = rand();}int begin1 = clock();Quicksort2(a2, 0, N - 1);int end1 = clock();printf("挖坑法-Quicksort:%d\n", end1 - begin1);free(a2);
}
void QuickTest3()
{srand(time(0));const int N = 1000000;int* a2 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a2[i] = rand();}int begin1 = clock();Quicksort3(a2, 0, N - 1);int end1 = clock();printf("前后指针-Quicksort:%d\n", end1 - begin1);free(a2);
}
void ShellsortTest()
{srand(time(0));const int N = 1000000;int* a2 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a2[i] = rand();}int begin1 = clock();Shellsort(a2, N);int end1 = clock();printf("希尔Shellsort:%d\n", end1 - begin1);free(a2);
}
int main()
{QuickTest1();QuickTest2();QuickTest3();ShellsortTest();return 0;}

在这里插入图片描述

排序OJ(可使用各种排序跑这个OJ)


http://www.ppmy.cn/news/48414.html

相关文章

camunda如何监控流程执行

camunda如何监控流程执行

在 Camunda 中&#xff0c;可以使用 Camunda 提供的用户界面和 API 来监控流程的执行情况。以下是几种常用的监控流程执行的方式&#xff1a; 1、使用 Camunda Cockpit&#xff1a;Camunda Cockpit 是 Camunda 官方提供的流程监控和管理工具&#xff0c;可以在浏览器中访问 Co…
阅读更多...
Shiro安全框架简介

Shiro安全框架简介

一、权限管理 1.1 什么是权限管理 基本上只要涉及到用户参数的系统都要进行权限管理&#xff0c;使用权限管理实现了对用户访问系统的控制&#xff0c;不同的用户访问不同的资源。按照安全规则或者安全策略控制用户访问资源&#xff0c;而且只能访问被授权的资源 权限管理包括认…
阅读更多...
13.基于双层优化的电动汽车日前-实时两阶段市场竞标

13.基于双层优化的电动汽车日前-实时两阶段市场竞标

MATLAB代码&#xff1a;基于双层优化的电动汽车日前-实时两阶段市场竞标 关键词&#xff1a;日前-实时市场竞标 电动汽车 双层优化 编程语言&#xff1a;MATLAB平台 内容简介&#xff1a;代码主要做的是电动汽车充电站市场竞标策略&#xff0c;采用双层优化模型对电动汽车…
阅读更多...
内网穿透搭建

内网穿透搭建

搭建内网穿透服务器搭建 1.frp frp官网 https://gofrp.org/ 简介 frp 是一个专注于内网穿透的高性能的反向代理应用&#xff0c;支持 TCP、UDP、HTTP、HTTPS 等多种协议。可以将内网服务以安全、便捷的方式通过具有公网 IP 节点的中转暴露到公网。 条件 公网服务器&…
阅读更多...
Linux网桥简介、入门与配置

Linux网桥简介、入门与配置

开始之前先得介绍一下什么是网桥&#xff0c;这里我们假设大家已经知道了物理的交换机是工作在链路层的。交换机的主要任务是在链路层查找转发表&#xff08;mac地址与端口对应关系表&#xff09;&#xff0c;按照数据帧的目标mac地址&#xff0c;转发数据帧到相应的端口。那么…
阅读更多...
4.24、半关闭、端口复用

4.24、半关闭、端口复用

UNIX网络编程卷1&#xff1a;套接字联网API&#xff08;第3版&#xff09; 等文件(提取码&#xff1a;q99x) 4.24、半关闭、端口复用 1.半关闭2.端口复用 1.半关闭 当 TCP 链接中 A 向 B 发送 FIN 请求关闭&#xff0c;另一端 B 回应 ACK 之后&#xff08;A 端进入 FIN_WAIT_…
阅读更多...
Java最新面试题100道，包含答案示例（1-10题）

Java最新面试题100道，包含答案示例（1-10题）

1. Java 中什么是 JVM&#xff1f; JVM&#xff08;Java Virtual Machine&#xff09;即 Java 虚拟机&#xff0c;是一种能够在不同平台上运行 Java 程序的虚拟计算机。JVM 是 Java 的核心组成部分&#xff0c;它负责解释 Java 代码并将其转换成可执行的二进制字节码指令&…
阅读更多...
13.弹出层.下

13.弹出层.下

学习要点&#xff1a; 1. 基础参数 本节课我们来开始了解 Layui 的内置模块&#xff1a;弹出层的方法演示。 一&#xff0e;基础参数 1. 参数&#xff0c;我们主要通过 open 方法来演示&#xff0c;其它方法类似&#xff1b; layer . open ({ // 标题 title : 标…
阅读更多...
最新文章

Copyright @ 2022~2023