快排(快速排序)的递归与非递归实现(文末附完整代码)

2024-06-09 21:44

本文主要是介绍快排(快速排序)的递归与非递归实现(文末附完整代码),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

快排有几种不同的写法,下面一一来介绍并实现。其中又分为递归和非递归的写法,但大体思路相同,只是代码实现略有不同。(注:文章中的完整代码中,Swap()函数均省略未写,记得自己补充)

递归写法

递归的写法类似于二叉树的前序遍历,先数组本身排序,再递归左右两个区间,直至将无序数组变为有序。

hoare版本

霍尔版本是快排的提出者,也就是最开始的写法。

其基于分治的思想,在数组中选中一个值作为基准(keyi),利用这个值(a[keyi]),进行排序,将待排序元素分为两份,比a[keyi]小的值在其左侧,比a[keyi]大的值在其右侧。此时a[keyi]这个值就排好序了,然后用递归的方法对左右两侧进行重复操作,直至无序数组变为有序。

一次排序过程如下:

其中,还有一些小问题需要注意:

代码实现为:

// 快速排序hoare版本
int PartSort(int* a, int left, int right)
{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;return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right){return;}int keyi = PartSort(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

挖坑法

挖坑法的思想是选中一个坑位(其值记为tmp,坑位的起始位置为begin),然后从右边找比tmp小的值,填入其中(此时要begin++),然后从左边找比tmp大的值填入新的坑位(此时坑位在end处,填入后要end--)。

最后begin和end相遇时,将tmp的值填入。

代码实现为:

// 挖坑法
int PartSort(int* a, int left, int right)
{int tmp = a[left];int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= tmp){end--;}a[begin] = a[end];if (begin >= end){break;}begin++;while (begin < end && a[begin] <= tmp){begin++;}a[end] = a[begin];if (begin >= end){break;}end--;}a[begin] = tmp;return begin;
}void QuickSort(int* a, int left, int right)
{if (left >= right){return;}int keyi = PartSort(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

写的这个版本看起来有些长,原因是我在写时,没有再用一个变量来记录坑位的位置,我们可以再添加一个变量来记录坑位的位置。

// 挖坑法
int PartSort(int* a, int left, int right)
{int tmp = a[left];int begin = left, end = right;int key = begin;while (begin < end){while (begin < end && a[end] >= tmp){end--;}a[key] = a[end];key = end;while (begin < end && a[begin] <= tmp){begin++;}a[key] = a[begin];key = begin;}a[key] = tmp;return key;
}void QuickSort(int* a, int left, int right)
{if (left >= right){return;}int keyi = PartSort(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

一趟排序过程如下:

双指针

双指针法的中心思想是利用 prevcur 两个指针来操作。

 具体代码实现如下:

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int keyi = left;int prev = left, cur = left + 1;while (cur <= right){//这里如果a[keyi] > a[cur],就会判断++prev != cur,//prev就会加一,只有prev和cur所在位置不同时才会发生交换。if (a[keyi] > a[cur] && ++prev != cur){Swap(&a[prev], &a[cur]);}cur++;}//最后交换prev位置和keyi位置的值Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right){return;}int keyi = PartSort3(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

非递归

有时候,递归深度太深会导致栈溢出,所以我们有时要用非递归来实现快排,非递归实现快排,我们就需要借助栈来实现。其思想就是模拟递归的过程,并用循环来替代,循环每走一次,就相当于递归了一次。所以要用栈来记录每次要排序的区间(也就是每次递归的 leftright )。栈的实现详解(点这里)。

// 快速排序hoare版本
int PartSort(int* a, int left, int right)
{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;return keyi;
}#include "Stacktest.h"// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{stack st;StackInit(&st);//先入右,再入左StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);//排序int keyi = PartSort(a, begin, end);if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi + 1);}if (begin < keyi - 1){StackPush(&st, keyi - 1);StackPush(&st, begin);}}StackDestory(&st);
}

具体过程如下:

优化

快排中 keyi 的选取是十分最重要的,快排的时间复杂度为O(N*logN),但其最坏情况下为O(N^2),如果基准值是数组中最大或最小的数值,则快速排序的递归深度会非常深,排序效率会很低。若是一个有序数组使用快速排序,则递归深度为n,单趟排序也为n,此时时间复杂度为O(N^2),为了避免最坏情况的发生,我们通常是在数组中随意选择一个数作为基准。这里有几种方法:随机数法、取中间位置和三数取中法。

随机数法

随机选一个,有概率选到最大值或最小值。

#include<stdlib.h>
#include<time.h>int GetNumber(int* a, int left, int right)
{return rand() % (right - left + 1) + left;
}// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int n = GetNumber(a, left, right);Swap(&a[left], &a[n]);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;return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right){return;}int keyi = PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}int main()
{srand((unsigned int)time(NULL));int arr[] = { 6,5,7,9,2,0,3,1,8,4,10 };int len = sizeof(arr) / sizeof(int);QuickSort(arr, 0, len - 1);//打印数组Print(arr, len);return 0;
}

取中间位置的数

取中间元素位置,也有可能选到最大值或最小值。

​
​
#include<stdlib.h>
#include<time.h>int GetNumber(int* a, int left, int right)
{return (right + left) / 2;
}// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int n = GetNumber(a, left, right);Swap(&a[left], &a[n]);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;return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right){return;}int keyi = PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}int main()
{srand((unsigned int)time(NULL));int arr[] = { 6,5,7,9,2,0,3,1,8,4,10 };int len = sizeof(arr) / sizeof(int);QuickSort(arr, 0, len - 1);//打印数组Print(arr, len);return 0;
}

三数取中法

三数取中法是指比较最左边、最右边和中间元素的大小选出折中值。不会选到最大值或最小值。

​
​
​
#include<stdlib.h>
#include<time.h>int GetNumber(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] < a[right]){return right;}else{return left;}}else //a[mid] <= a[left]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int n = GetNumber(a, left, right);Swap(&a[left], &a[n]);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;return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right){return;}int keyi = PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

小区间优化

递归不断的拆分左右区间,越往深递归,所耗费的时间就越多,当递归至区间中元素个数为个位数字时,使用快排反而降低了效率,这是我们可以考虑使用插入排序来进行小区间优化。

void QuickSort(int* a, int left, int right)
{if (left >= right){return;}//小区间优化if ((right - left + 1) < 10){InsertSort(a + left, left, right);}else{int keyi = PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>void Swap(int* p1, int* p2)
{int* tmp = *p1;*p1 = *p2;*p2 = tmp;
}void Print(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}//插入排序
void InsertSort(int* a, int n)
{for (int i = 1; i < n - 1; i++){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;}
}// 快速排序递归实现int GetNumber(int* a, int left, int right)
{//return (right - left) / 2;//return rand() % (right - left + 1) + left;int mid = (right + left) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] < a[right]){return right;}else{return left;}}else //a[mid] <= a[left]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int n = GetNumber(a, left, right);Swap(&a[left], &a[n]);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;return keyi;
}// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int tmp = a[left];int begin = left, end = right;int key = begin;while (begin < end){while (begin < end && a[end] >= tmp){end--;}/*a[begin] = a[end];if (begin >= end){break;}begin++;*/a[key] = a[end];key = end;while (begin < end && a[begin] <= tmp){begin++;}/*a[end] = a[begin];if (begin >= end){break;}end--;*/a[key] = a[begin];key = begin;}a[key] = tmp;return key;
}// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int keyi = left;int prev = left, cur = left + 1;while (cur <= right){//这里如果a[keyi] > a[cur],就会判断++prev != cur,//prev就会加一,只有prev和cur所在位置不同时才会发生交换。if (a[keyi] > a[cur] && ++prev != cur){Swap(&a[prev], &a[cur]);}cur++;}//最后交换prev位置和keyi位置的值Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right){return;}//小区间优化if ((right - left + 1) < 10){InsertSort(a + left, left, right);}else{int keyi = PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}#include "Stacktest.h"// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{stack st;StackInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int keyi = PartSort1(a, begin, end);if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi + 1);}if (begin < keyi - 1){StackPush(&st, keyi - 1);StackPush(&st, begin);}}StackDestory(&st);
}int main()
{srand((unsigned int)time(NULL));int arr[] = { 6,5,7,9,2,0,3,1,8,4,10 };int len = sizeof(arr) / sizeof(int);QuickSort(arr, 0, len - 1);Print(arr, len);return 0;
}

这篇关于快排(快速排序)的递归与非递归实现(文末附完整代码)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1046382

相关文章

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

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

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

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

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

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c