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

た入场券 2022-05-31 14:16 242阅读 0赞

# 快速排序算法介绍 #

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

# 图解快速排序算法 #

![20180227123624764][]

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

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

//快速排序 升序 递归形式
    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 == j
    		arr[i] = temp;//将基准数放到它的正确位置，现在它左边的数都比它小，他右边的数都比它大。
    		QuickSort_Up_Recursion(arr, start, i - 1);//将它左边的序列 进行快排
    		QuickSort_Up_Recursion(arr, i + 1, end);//将它右边的序列 进行快排
    	}
    }

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

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

//将基准数 放到它该有的位置
    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 == j
    		arr[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);
    			}
    		}
    	}
    }

# 完整代码 #

其他排序算法代码请看，**[希尔排序][Link 2]，[堆排序][Link 3]，[归并排序][Link 4]**

#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 == j
    		arr[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 == j
    		arr[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;
    }

# 代码运行检测 #

## 正确性校验 ##

![20180227172159359][]

## 和希尔排序、堆排序、归并排序 比较 ##

用同样**随机数字数组**测试**100万个数字元素，还是快排最快。**

![20180227130305158][]

[20180227123624764]: /images/20220531/d5855bd93ca64d768db4f6266b518a50.png
[Link 1]: http://blog.csdn.net/qq_29542611/article/details/79372198
[Link 2]: http://blog.csdn.net/qq_29542611/article/details/79352820
[Link 3]: http://blog.csdn.net/qq_29542611/article/details/79356378
[Link 4]: http://blog.csdn.net/qq_29542611/article/details/79366050
[20180227172159359]: /images/20220531/0207e794e05e4bc795b20e12435dde09.png
[20180227130305158]: /images/20220531/7420d510d0db4d67852164df8791e4e1.png