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

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);
}

一趟排序过程如下：

双指针

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

 具体代码实现如下：

// 快速排序前后指针法
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);
}

非递归

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

// 快速排序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。

相关文章

Python实例题之pygame开发打飞机游戏实例代码

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,：本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部
阅读更多...
Python实现精准提取 PDF中的文本,表格与图片

Python实现精准提取 PDF中的文本,表格与图片

《Python实现精准提取PDF中的文本,表格与图片》在实际的系统开发中,处理PDF文件不仅限于读取整页文本,还有提取文档中的表格数据,图片或特定区域的内容,下面我们来看看如何使用Python实... 目录安装 python 库提取 PDF 文本内容：获取整页文本与指定区域内容获取页面上的所有文本内容获取
阅读更多...
基于Python实现一个Windows Tree命令工具

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一：创建批处理文件并添加到PATH1
阅读更多...
Java使用HttpClient实现图片下载与本地保存功能

Java使用HttpClient实现图片下载与本地保存功能

《Java使用HttpClient实现图片下载与本地保存功能》在当今数字化时代,网络资源的获取与处理已成为软件开发中的常见需求,其中,图片作为网络上最常见的资源之一,其下载与保存功能在许多应用场景中都... 目录引言一、Apache HttpClient简介二、技术栈与环境准备三、实现图片下载与保存功能1.
阅读更多...
canal实现mysql数据同步的详细过程

canal实现mysql数据同步的详细过程

《canal实现mysql数据同步的详细过程》：本文主要介绍canal实现mysql数据同步的详细过程,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的... 目录1、canal下载2、mysql同步用户创建和授权3、canal admin安装和启动4、canal
阅读更多...
Nexus安装和启动的实现教程

Nexus安装和启动的实现教程

《Nexus安装和启动的实现教程》：本文主要介绍Nexus安装和启动的实现教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、Nexus下载二、Nexus安装和启动三、关闭Nexus总结一、Nexus下载官方下载链接：DownloadWindows系统根
阅读更多...
SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程

SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程

《SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程》LiteFlow是一款专注于逻辑驱动流程编排的轻量级框架,它以组件化方式快速构建和执行业务流程,有效解耦复杂业务逻辑,下面给大... 目录一、基础概念1.1 组件（Component）1.2 规则（Rule）1.3 上下文（Conte
阅读更多...
Java中Map.Entry()含义及方法使用代码

Java中Map.Entry()含义及方法使用代码

《Java中Map.Entry()含义及方法使用代码》：本文主要介绍Java中Map.Entry()含义及方法使用的相关资料,Map.Entry是Java中Map的静态内部接口,用于表示键值对,其... 目录前言 Map.Entry作用核心方法常见使用场景1. 遍历 Map 的所有键值对2. 直接修改 Ma
阅读更多...
MySQL 横向衍生表(Lateral Derived Tables)的实现

MySQL 横向衍生表(Lateral Derived Tables)的实现

《MySQL横向衍生表(LateralDerivedTables)的实现》横向衍生表适用于在需要通过子查询获取中间结果集的场景,相对于普通衍生表,横向衍生表可以引用在其之前出现过的表名,本文就来... 目录一、横向衍生表用法示例1.1 用法示例1.2 使用建议前面我们介绍过mysql中的衍生表（From子句
阅读更多...
Mybatis的分页实现方式

Mybatis的分页实现方式

《Mybatis的分页实现方式》MyBatis的分页实现方式主要有以下几种,每种方式适用于不同的场景,且在性能、灵活性和代码侵入性上有所差异,对Mybatis的分页实现方式感兴趣的朋友一起看看吧... 目录​1. 原生 SQL 分页（物理分页）​​2. RowBounds 分页（逻辑分页）​​3. Page
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2