失眠网 > 排序算法：快速排序算法实现及分析（递归形式和非递归形式）

排序算法：快速排序算法实现及分析（递归形式和非递归形式）

时间：2023-10-12 22:24:49

快速排序算法介绍

从名字上就可以看出快速排序算法很嚣张，直接以快速命名。确实快速排序的确很快速，被列为20世纪十大算法之一。程序员难道不应该掌握么。快速排序（Quick Sort）的基本思想是：通过一趟排序将待排序记录分割成独立的2部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这2部分分记录继续进行排序，以达到整个序列有序的目的。没有理解？没关系，下面看图解。快速排序可以用递归的形式，当然任何递归形式的代码都可以改用栈或者队列这种数据结构进行改造，下面也有非递归形式的快速排序代码当然要比递归形式代码要复杂一点。

图解快速排序算法

快速排序算法递归代码实现

代码不是很多，还是那个逻辑将比基准数小的往前移，比基准数大的往后，将基准数放到正确的位置。然后进行递归分治。递归形式的代码比较容易理解。

//快速排序升序递归形式void QuickSort_Up_Recursion(int *arr, int start, int end){int i = start;int j = end;int temp = arr[i];//基准数if (i < j){while (i < j){//从后往前找比基准数小的下标while (i < j&& arr[j] >= temp){j--;}//将比基准数小的往前移if (i < j){arr[i] = arr[j];i++;}//从前往后找比基准数大的下标while (i < j&& arr[i] < temp){i++;}//将比基准数大的往后移if (i < j){arr[j] = arr[i];j--;}}//while循环完毕i == jarr[i] = temp;//将基准数放到它的正确位置，现在它左边的数都比它小，他右边的数都比它大。QuickSort_Up_Recursion(arr, start, i - 1);//将它左边的序列进行快排QuickSort_Up_Recursion(arr, i + 1, end);//将它右边的序列进行快排}}

快速排序算法非递归代码实现

因为递归需要函数的弹栈压栈对栈内存开销比较大，请记住任何形式的递归，只要是递归都可以通过队列或者栈数据结构去完成，我们自己封装的队列或者栈内存开辟实在堆当中所以不会对栈空间进行太大的开销。下面采用队列数据结构对快速排序的递归代码进行改造。队列采用的是自己底层封装的代码，不明白请看顺序队列。

//将基准数放到它该有的位置void QuickSort_Up_BaseNum(int *arr, int start, int end, int* mid){int i = start;int j = end;int temp = arr[i];//基准数if (i < j){while (i < j){//从后往前找比基准数小的下标while (i < j&& arr[j] >= temp){j--;}//将比基准数小的往前移if (i < j){arr[i] = arr[j];i++;}//从前往后找比基准数大的下标while (i < j&& arr[i] < temp){i++;}//将比基准数大的往后移if (i < j){arr[j] = arr[i];j--;}}//while循环完毕i == jarr[i] = temp;//将基准数放到它的正确位置，现在它左边的数都比它小，他右边的数都比它大。*mid = i;//printf("基准数：%d\n", temp);//PrintArr(arr, 10);}}//快速排序非递归形式升序//用队列或者栈都是可以的因为先分治左边或者先分治右边没有先后顺序的要求void QuickSort_Up_Nonrecursion(int* arr, int start, int end){SeqQueue queue = Init_SeqQueue();int* start1 = malloc(sizeof(int));int* end2 = malloc(sizeof(int));*start1 = start;*end2 = end;Push_SeqQueue(queue, start1);Push_SeqQueue(queue, end2);int mid;//临时变量while (!IsEmpty_SeqQueue(queue)){start1 = Pop_SeqQueue(queue);end2 = Pop_SeqQueue(queue);if (*start1 < *end2){//printf("(%d,%d) ", *start1, *end2);QuickSort_Up_BaseNum(arr, *start1, *end2, &mid);int* end1 = malloc(sizeof(int));int* start2 = malloc(sizeof(int));*end1 = mid - 1;*start2 = mid + 1;if (*start2 < *end2){Push_SeqQueue(queue, start2);Push_SeqQueue(queue, end2);}if (*start1 < *end1){Push_SeqQueue(queue, start1);Push_SeqQueue(queue, end1);}}}}

完整代码

其他排序算法代码请看，希尔排序，堆排序，归并排序

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h>#include <time.h>#include <sys/timeb.h>//#include "AllSort.h"#include "SeqQueue.h"#define MAXSIZE 1000000//打印数组元素void PrintArr(int* arr, int length){for (int i = 0; i < length; i++){printf("%d ", arr[i]);}printf("\n");return;}//获取系统时间long GetSysTime(){struct timeb time;ftime(&time);return time.time * 1000 + time.millitm;;}//快速排序升序递归形式void QuickSort_Up_Recursion(int *arr, int start, int end){int i = start;int j = end;int temp = arr[i];//基准数if (i < j){while (i < j){//从后往前找比基准数小的下标while (i < j&& arr[j] >= temp){j--;}//将比基准数小的往前移if (i < j){arr[i] = arr[j];i++;}//从前往后找比基准数大的下标while (i < j&& arr[i] < temp){i++;}//将比基准数大的往后移if (i < j){arr[j] = arr[i];j--;}}//while循环完毕i == jarr[i] = temp;//将基准数放到它的正确位置，现在它左边的数都比它小，他右边的数都比它大。QuickSort_Up_Recursion(arr, start, i - 1);//将它左边的序列进行快排QuickSort_Up_Recursion(arr, i + 1, end);//将它右边的序列进行快排}}//将基准数放到它该有的位置void QuickSort_Up_BaseNum(int *arr, int start, int end, int* mid){int i = start;int j = end;int temp = arr[i];//基准数if (i < j){while (i < j){//从后往前找比基准数小的下标while (i < j&& arr[j] >= temp){j--;}//将比基准数小的往前移if (i < j){arr[i] = arr[j];i++;}//从前往后找比基准数大的下标while (i < j&& arr[i] < temp){i++;}//将比基准数大的往后移if (i < j){arr[j] = arr[i];j--;}}//while循环完毕i == jarr[i] = temp;//将基准数放到它的正确位置，现在它左边的数都比它小，他右边的数都比它大。*mid = i;//printf("基准数：%d\n", temp);//PrintArr(arr, 10);}}//快速排序非递归形式升序//用队列或者栈都是可以的因为先分治左边或者先分治右边没有先后顺序的要求void QuickSort_Up_Nonrecursion(int* arr, int start, int end){SeqQueue queue = Init_SeqQueue();int* start1 = malloc(sizeof(int));int* end2 = malloc(sizeof(int));*start1 = start;*end2 = end;Push_SeqQueue(queue, start1);Push_SeqQueue(queue, end2);int mid;//临时变量while (!IsEmpty_SeqQueue(queue)){start1 = Pop_SeqQueue(queue);end2 = Pop_SeqQueue(queue);if (*start1 < *end2){//printf("(%d,%d) ", *start1, *end2);QuickSort_Up_BaseNum(arr, *start1, *end2, &mid);int* end1 = malloc(sizeof(int));int* start2 = malloc(sizeof(int));*end1 = mid - 1;*start2 = mid + 1;if (*start2 < *end2){Push_SeqQueue(queue, start2);Push_SeqQueue(queue, end2);}if (*start1 < *end1){Push_SeqQueue(queue, start1);Push_SeqQueue(queue, end1);}}}}int main(int argc, char *argv[]){srand((size_t)time(NULL));//设置随机种子int arr0[10] = { 6,8,2,3,9,7,4,1,5,10 };int arr1[10] = { 4,1,10,3,9,7,5,6,8,2 };int len0 = sizeof(arr0) / sizeof(arr0[0]);int len1 = sizeof(arr1) / sizeof(arr1[0]);int *arr2 = (int*)malloc(sizeof(int)*MAXSIZE);//希尔排序int *arr3 = (int*)malloc(sizeof(int)*MAXSIZE);//堆排序int *arr4 = (int*)malloc(sizeof(int)*MAXSIZE);//归并排序int *temp = (int*)malloc(sizeof(int)*MAXSIZE);//归并排序辅助空间int *arr5 = (int*)malloc(sizeof(int)*MAXSIZE);//快速排序for (int i = 0; i < MAXSIZE; i++){arr2[i] = rand() % MAXSIZE;arr3[i] = rand() % MAXSIZE;arr4[i] = rand() % MAXSIZE;arr5[i] = rand() % MAXSIZE;}printf("排序前arr0：\n");PrintArr(arr0,len0);printf("排序前arr1：\n");PrintArr(arr1, len1);printf("arr0快速排序升序[递归形式]：\n");QuickSort_Up_Recursion(arr0, 0, len0 - 1);PrintArr(arr0, len0);printf("arr1快速排序升序[非递归形式]：\n");QuickSort_Up_Nonrecursion(arr1, 0, len1 - 1);PrintArr(arr1, len1);/*long start1 = GetSysTime();ShellSort_Up(arr2,MAXSIZE);long end1 = GetSysTime();printf("%d个数据希尔排序耗费时间%d毫秒\n",MAXSIZE,end1-start1);long start2 = GetSysTime();HeapSort_Up(arr3,MAXSIZE);long end2 = GetSysTime();printf("%d个数据堆排序耗费时间%d毫秒\n",MAXSIZE,end2-start2);long start3 = GetSysTime();MergeSort_Up(arr4, 0, MAXSIZE - 1, temp);long end3 = GetSysTime();printf("%d个数据归并排序耗费时间%d毫秒\n",MAXSIZE,end3-start3);long start4 = GetSysTime();QuickSort_Up(arr5, 0, MAXSIZE - 1);long end4 = GetSysTime();printf("%d个数据快速排序耗费时间%d毫秒\n",MAXSIZE,end4-start4);*/return 0;}