数据结构——快速排序（hoare版、挖坑法、前后指针版、循环实现）

2023-10-07 18:50
文章标签 实现 指针 快速 数据结构 排序 循环 挖坑 hoare

本文主要是介绍数据结构——快速排序（hoare版、挖坑法、前后指针版、循环实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、算法思想

1.hoare版

2.挖坑法

3.前后指针版

 二、算法缺陷与优化

1.算法缺陷

1.1基准值取值

1.2递归超限

2.优化方法

2.1三位取中法

2.2设置阈值

2.3循环实现

三、接口实现

1.快速排序

2.hoare版

3.挖坑法

4.前后指针版

5.非递归版

四、接口测试

1.测试用例

2.测试结果

2.1递归方式

 2.2非递归方式

五、性能分析

六、完整代码

1.QuickSort.c

2.Stack.h

一、算法思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想是：任意选取待排序序列中的一个元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后再对左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

注：后续实现均以取序列最右侧元素为基准值为例。

其中，将区间按照基准值划分为左右两部分的常见方式有三种：

1.hoare版

通过两个标志，分别从左往右找比基准值大的元素和从右向左找比基准值小的元素，然后交换两个元素，重复上述过程直到两个标志位相遇，最后再将基准值交换到相遇位置，然后再对左右子序列重复上述过程，直到整个序列完成排序。

图示：

2.挖坑法

挖坑法大体思路与hoare法思路相同，其基本思想是：将基准值保存到标记位中，这样最右侧位置就形成了一个坑位，然后左侧标注位往右遍历找比基准值大的元素，找到后将该元素填入右侧坑位中，该位置就又形成了一个新的坑位，然后从右侧往左遍历找比基准值小的元素，将该元素填入到坑位中，重复上述过程直到左右标志位相遇，最后将基准值放入最后的坑位中，最对左右子序列重复上述过程直到整个序列排序完成。

图示基准值取的为最左侧元素：

3.前后指针版

初始设置cur、prev两个标志指针，cur标志序列第一个元素，prev标志cur前一个位置，cur位置的元素若大于基准值，cur向前前进，若小于基准值，则先对prev进行加一，然后交换cur和prev标记位置的元素，这样就能保证cur与prev之间的元素都大于基准值，prev之前的元素都小于基准值，重复上述过程，直到cur超过序列最右侧位置，最后进行一次判断，若prev标记位置不是序列最后一个位置，则将基准值交换到prev交换位置，即完成左右子序列划分，再对左右子序列重复上述过程，直到整个序列完成排序。

图示：

 二、算法缺陷与优化

1.算法缺陷

1.1基准值取值

若所取基准值为序列中的最大或最小值，那么每趟划分后，基准值的一侧将会出现没有元素的情况，就相当于每趟只完成了一个元素的排序，那么快速排序的时间复杂度此时将达到O(n^{2})，效率较低。

1.2递归超限

算法递归深度会随着元素的增多而加深，若序列元素元素量非常巨大，可能会造成递归超限。

2.优化方法

2.1三位取中法

我们可以通过选取序列中开始、中间、末尾三个位置中元素大小居中的元素作为基准值，此方法可以大大降低基准值取到序列内最大或最小元素的概率。

注：为了不改变代码的逻辑实现，若取得的基准值的位置不是基准值默认位置，可先提前将基准值交换到所取基准值的默认位置处。

2.2设置阈值

我们可以发现，随着划分次数的增加，子序列内的元素个数会不断减少，而且元素数量较少时，各类排序算法的效率差距其实是可以忽略不记的，而比较适合元素个数比较少的排序就是直接插入排序，所以我们可以在递归的过程中设计一个阈值，当子序列中元素个数不超过阈值时，递归不再进行，而是直接对当前子序列进行直接插入排序，然后返回。

当然，这种方法只能进行一定程度的缓解，并不能完全解决递归超限的问题。

所以，我们可以提前估算一下递归的深度N，再在递归深度上设置一个阈值count，若N小于count直接进行快速排序；若N大于count，先通过快速排序递归count次，然后再对每个分组中进行其他排序（比如：堆排序）。

这样即不会对算法效率造成太大影响，也避免了递归超限的问题。

2.3循环实现

使用循环的方式实现快速排序，我们会发现直接转循环并不容易实现，结合递归调用的特性，后调用的先结束退出，先调用的后结束，符合栈后进先出的特点，所有可以利用栈来循环实现快速排序。

每次对序列进行分割后，利用栈依次压入左右子序列的右边界和左边界，这样下一次循环就会依次拿到一个子序列的左右边界，然后再对此序列进行分割，循环进行上述操作，直到栈为空即完成序列排序。（可加上优化方法，为子序列元素个数加上阈值）

三、接口实现

1.快速排序

void QuickSort(int* array, int left, int right) {//快速排序if (right - left <= 16) {//阈值设置为16InsertSort(array + left, right - left);//达到阈值，进行直接插入排序}else {if (right - left <= 1) {//区间内少于等于1个元素，不需要再排return;}int div = PartSort2(array, left, right);//找一个基准值对区间元素进行划分，分割完成后返回基准值位置QuickSort(array, left, div);//对基准值左侧进行快排QuickSort(array, div + 1, right);//对基准值右侧进行快排}
}

2.hoare版

int PartSort1(int* array, int left, int right) {//快速排序hoare版int begin = left;int end = right - 1;int midPos = GetMiddleIndex(array, left, right);//获取元素大小相对靠中的元素下标if (midPos != end) {//将该元素交换到末尾，从而不影响后续代码的逻辑实现Swap(&array[midPos], &array[end]);}int key = array[end];//取最后一个元素为基准值while (begin < end) {//begin与end没有相遇while (begin < end && array[begin] <= key) {//1.从前往后找比基准值key大的元素begin++;}while (begin < end && array[end] >= key) {//2.从后往前找比基准值key小的元素end--;}if (begin != end) {//3.交换两个元素Swap(&array[begin], &array[end]);}}Swap(&array[begin], &array[right - 1]);//4.将基准值交换到区间中间位置return begin;//5.返回基准值下标
}

3.挖坑法

int PartSort2(int* array, int left, int right) {//快速排序挖坑法int begin = left;int end = right - 1;int midPos = GetMiddleIndex(array, left, right);//获取元素大小相对靠中的元素下标if (midPos != end) {//将该元素交换到末尾，从而不影响后续代码的逻辑实现Swap(&array[midPos], &array[end]);}int key = array[end];//1.取最后一个元素为基准值，并挖坑endwhile (begin < end) {//begin与end没有相遇while (begin < end && array[begin] <= key) {//2.从前往后找比基准值key大的元素begin++;}if (begin != end) {array[end--] = array[begin];//3.填end坑,挖begin坑,end前移一位}while (begin < end && array[end] >= key) {//4.从后往前找比基准值key小的元素end--;}if (begin != end) {array[begin++] = array[end];//5.填begin坑，挖end坑，begin后移一位}}array[end] = key;//6.基准值放入最后一个坑内return end;//7.返回基准值下标
}

4.前后指针版

int PartSort3(int* array, int left, int right) {//快速排序前后指针版int cur = left;//标记第一个元素int prev = cur - 1;//位于cur之后一个位置int midPos = GetMiddleIndex(array, left, right);//获取元素大小相对靠中的元素下标if (midPos != right - 1) {//将该元素交换到末尾，从而不影响后续代码的逻辑实现Swap(&array[midPos], &array[right - 1]);}int key = array[right - 1];//取最后一个元素为基准值while (cur < right) {if (array[cur] < key && ++prev != cur) {//始终保存cur与prev之间的元素都大于基准值keySwap(&array[cur], &array[prev]);}cur++;}if (++prev != right - 1) {//将基准值交换到prev的下一个位置Swap(&array[right - 1], &array[prev]);}return prev;
}

5.非递归版

void QuickSortNonR(int* array, int size) {//快速排序非递归版Stack s;StackInit(&s);int left = 0;int right = size;StackPush(&s, right);//依次压入右边界和左边界StackPush(&s, left);while (!StackEmpty(&s)) {//栈不为空，循环进行left = StackTop(&s);//获取栈顶，左边界StackPop(&s);//左边界出栈right = StackTop(&s);//获取栈顶，右边界StackPop(&s);//右边界出栈if (right - left <= 16) {//子序列达到阈值InsertSort(array + left, right - left);//进行直接插入排序}else {int div = PartSort2(array, left, right);//基准值左侧（left，div）；右侧（div+1，right）//先压右侧子序列边界（先压右边界，再压左边界）StackPush(&s, right);StackPush(&s, div + 1);//再压左侧子序列边界StackPush(&s, div);StackPush(&s, left);}}
}

四、接口测试

1.测试用例

void TestPartSort() {//快速排序测试函数int array[] = { 5,4,8,1,9,7,3,2,6,0 };int length = sizeof(array) / sizeof(array[0]);printf("排序前：");PrintArray(array, length);QuickSort(array, 0, length);//递归方式//QuickSortNonR(array, length);//非递归方式printf("\n排序后：");PrintArray(array, length);
}

2.测试结果

2.1递归方式

 2.2非递归方式

五、性能分析

1.时间复杂度：O(nlog^{n})

2.空间复杂度：O(log^{n})

3.稳定性：不稳定

六、完整代码

1.QuickSort.c

#include"Stack.h"void QuickSort(int* array, int left, int right);//快速排序
int  PartSort1(int* array, int left, int right);//快速排序hoare版
int  PartSort2(int* array, int left, int right);//快速排序挖坑法
int  PartSort3(int* array, int left, int right);//快速排序前后指针版int GetMiddleIndex(int* array, int left, int right);//三位取中法(选取元素大小相对靠中的为基准值)
void QuickSortNonR(int* array, int size);//快速排序非递归版void InsertSort(int* array, int size);//直接插入排序
void PrintArray(int* array, int size);//数组打印
void Swap(int* num1, int* num2);//整数交换void TestPartSort();//快速排序测试函数int main() {TestPartSort();return 0;
}void QuickSort(int* array, int left, int right) {//快速排序if (right - left <= 16) {//阈值设置为16InsertSort(array + left, right - left);//达到阈值，进行直接插入排序}else {if (right - left <= 1) {//区间内少于等于1个元素，不需要再排return;}int div = PartSort2(array, left, right);//找一个基准值对区间元素进行划分，分割完成后返回基准值位置QuickSort(array, left, div);//对基准值左侧进行快排QuickSort(array, div + 1, right);//对基准值右侧进行快排}
}int PartSort1(int* array, int left, int right) {//快速排序hoare版int begin = left;int end = right - 1;int midPos = GetMiddleIndex(array, left, right);//获取元素大小相对靠中的元素下标if (midPos != end) {//将该元素交换到末尾，从而不影响后续代码的逻辑实现Swap(&array[midPos], &array[end]);}int key = array[end];//取最后一个元素为基准值while (begin < end) {//begin与end没有相遇while (begin < end && array[begin] <= key) {//1.从前往后找比基准值key大的元素begin++;}while (begin < end && array[end] >= key) {//2.从后往前找比基准值key小的元素end--;}if (begin != end) {//3.交换两个元素Swap(&array[begin], &array[end]);}}Swap(&array[begin], &array[right - 1]);//4.将基准值交换到区间中间位置return begin;//5.返回基准值下标
}int PartSort2(int* array, int left, int right) {//快速排序挖坑法int begin = left;int end = right - 1;int midPos = GetMiddleIndex(array, left, right);//获取元素大小相对靠中的元素下标if (midPos != end) {//将该元素交换到末尾，从而不影响后续代码的逻辑实现Swap(&array[midPos], &array[end]);}int key = array[end];//1.取最后一个元素为基准值，并挖坑endwhile (begin < end) {//begin与end没有相遇while (begin < end && array[begin] <= key) {//2.从前往后找比基准值key大的元素begin++;}if (begin != end) {array[end--] = array[begin];//3.填end坑,挖begin坑,end前移一位}while (begin < end && array[end] >= key) {//4.从后往前找比基准值key小的元素end--;}if (begin != end) {array[begin++] = array[end];//5.填begin坑，挖end坑，begin后移一位}}array[end] = key;//6.基准值放入最后一个坑内return end;//7.返回基准值下标
}int PartSort3(int* array, int left, int right) {//快速排序前后指针版int cur = left;//标记第一个元素int prev = cur - 1;//位于cur之后一个位置int midPos = GetMiddleIndex(array, left, right);//获取元素大小相对靠中的元素下标if (midPos != right - 1) {//将该元素交换到末尾，从而不影响后续代码的逻辑实现Swap(&array[midPos], &array[right - 1]);}int key = array[right - 1];//取最后一个元素为基准值while (cur < right) {if (array[cur] < key && ++prev != cur) {//始终保存cur与prev之间的元素都大于基准值keySwap(&array[cur], &array[prev]);}cur++;}if (++prev != right - 1) {//将基准值交换到prev的下一个位置Swap(&array[right - 1], &array[prev]);}return prev;
}void QuickSortNonR(int* array, int size) {//快速排序非递归版Stack s;StackInit(&s);int left = 0;int right = size;StackPush(&s, right);//依次压入右边界和左边界StackPush(&s, left);while (!StackEmpty(&s)) {//栈不为空，循环进行left = StackTop(&s);//获取栈顶，左边界StackPop(&s);//左边界出栈right = StackTop(&s);//获取栈顶，右边界StackPop(&s);//右边界出栈if (right - left <= 16) {//子序列达到阈值InsertSort(array + left, right - left);//进行直接插入排序}else {int div = PartSort2(array, left, right);//基准值左侧（left，div）；右侧（div+1，right）//先压右侧子序列边界（先压右边界，再压左边界）StackPush(&s, right);StackPush(&s, div + 1);//再压左侧子序列边界StackPush(&s, div);StackPush(&s, left);}}
}int GetMiddleIndex(int* array, int left, int right) {//三位取中法(选取元素大小相对靠中的为基准值)int mid = (left + right) / 2;//返回基准值的下标if (array[left] < array[right - 1]) {if (array[mid] < array[left]) {return left;}else if (array[mid] > array[right - 1]) {return right - 1;}else {return mid;}}else {//array[left]>=array[right-1]if (array[mid] > array[left]) {return left;}else if (array[mid] < array[right - 1]) {return right - 1;}else {return mid;}}
}void InsertSort(int* array, int size) {//直接插入排序for (int i = 1; i < size; i++) {//从1开始循环，默认数组内第一个元素为有序序列int end = i - 1;//标记已排序序列最后位置下标int key = array[i];//依次拿取数组内元素while (end >= 0 && key < array[end]) {//key从前往后比较：小于当前元素，继续往前走array[end + 1] = array[end];//将当前元素往后移一个位置end--;}array[end + 1] = key;//key大于等于当前元素，插入到当前位置之后}
}void PrintArray(int* array, int size) {//数组打印for (int i = 0; i < size; i++) {printf("%d ", array[i]);}
}void Swap(int* num1, int* num2) {//整数交换int temp = *num1;*num1 = *num2;*num2 = temp;
}void TestPartSort() {//快速排序测试函数int array[] = { 5,4,8,1,9,7,3,2,6,0 };int length = sizeof(array) / sizeof(array[0]);printf("排序前：");PrintArray(array, length);//QuickSort(array, 0, length);//递归方式QuickSortNonR(array, length);//非递归方式printf("\n排序后：");PrintArray(array, length);
}

2.Stack.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<malloc.h>// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* array;int top;		// 栈顶int capacity;  // 容量 
}Stack;
/*void StackInit(Stack* ps, int capacity);// 初始化栈 
void StackPush(Stack* ps, STDataType data);// 入栈 
void StackPop(Stack* ps);// 出栈 
STDataType StackTop(Stack* ps);// 获取栈顶元素 
int StackSize(Stack* ps);// 获取栈中有效元素个数 
int StackEmpty(Stack* ps);// 检测栈是否为空，为空返回1，非空返回0 
void StackDestroy(Stack* ps);// 销毁栈 
void Stack_Test();//功能测试函数
*/// 初始化栈 
void StackInit(Stack* ps) {assert(ps);ps->array = (STDataType*)malloc(sizeof(STDataType) * 3);if (ps->array == NULL) {//申请失败assert(0);return;}ps->capacity = 3;ps->top = 0;
}void StackCheckCapacity(Stack* ps) {assert(ps);if (ps->top == ps->capacity) {//栈满int newCapacity = ps->capacity * 2;//每次扩容扩大两倍STDataType* temp = (STDataType*)malloc(sizeof(STDataType) * newCapacity);//开辟新空间if (temp == NULL) {assert(0);return;}memcpy(temp, ps->array, sizeof(STDataType) * ps->capacity);//将元数据拷贝到新空间中free(ps->array);//释放旧空间，使用新空间ps->array = temp;ps->capacity = newCapacity;}
}void StackPush(Stack* ps, STDataType data) {//入栈StackCheckCapacity(ps);//判断是否栈满，栈满则扩容ps->array[ps->top] = data;ps->top++;
}int StackEmpty(Stack* ps) {//栈判空assert(ps);return 0 == ps->top;//空返回1，非空返回0
}void StackPop(Stack* ps) {//出栈if (StackEmpty(ps)) {//判空return;}ps->top--;
}STDataType StackTop(Stack* ps) {//获取栈顶元素assert(ps);return ps->array[ps->top - 1];
}int StackSize(Stack* ps) {//获取栈中有效元素个数assert(ps);return ps->top;
}void StackDestroy(Stack* ps) {//栈销毁assert(ps);if (ps->array) {free(ps->array);ps->capacity = 0;ps->top = 1;}
}

这篇关于数据结构——快速排序（hoare版、挖坑法、前后指针版、循环实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
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
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

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

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

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

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

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

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

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

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

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

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

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

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

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
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2