【排序算法全解】之 - 快速排序(QuickSort)

目录

1.算法原理

2.代码实现

3.算法复杂度分析

4.算法效率测试 

5.算法改进与优化

1.算法原理

每趟排序，先选取一个基准值key，把值小于key的元素都交换到key左边，大于key的元素都交换到右边

然后再分别对key值左右两边的序列进行快速排序

当序列元素小于等于2个时完成排序（若这时选取基准值，那么基准值左右两边待排序序列元素个数为1）

例如对数组  [  3，5，4，1，6，2  ]  的快速排序过程如下

 而每趟排序过程可以用左右指针法或者用挖坑法，挖坑法比较于左右指针法，可以少用一个中间变量，并减少元素交换次数，速度更快

本篇介绍的是 “挖坑” 法

例如对数组  [  3，5，4，1，6，2  ]  的一趟排序如下

先把key值挖出来

从右往左找比key小的元素挖出来，填入坑，元素被挖后留下坑

从左往右找比key大的元素挖出来，填入坑，元素被挖后留下坑

可以看到，一趟排序过后，比key值小的元素都换到了key值左边，比key值大的元素都换到了key值右边。

2.代码实现

快速排序一般有三个参数

第一个参数是数组名，第二个参数是排序开始位置下标，第三个参数是排序结束位置下标

由于是递归调用函数，在每趟排序前就得判断返回条件，当传入的序列长度小于等于2时，该序列已经有序，那么就返回。

当一次排序完，选取基准值后，待排序序列只有一个元素时，即返回

这里我们用Begin表示开始位置下标，用End表示结束位置下标，即Begin>=End时返回

按上述算法所编写的代码如下

void QuickSort(int t[],int Begin,int End)
{
    if(Begin>=End) return;
    int Left=Begin,Right=End;
    int tem=t[Begin];
    while(Begin<End)
    {
        while(Begin<End&&t[End]>=tem)
        {
            End--;
        }
        t[Begin]=t[End];
        while(Begin<End&&t[Begin]<=tem)
        {
            Begin++;
        }
        t[End]=t[Begin];
    }
    t[Begin]=tem;
    QuickSort(t,Left,Begin-1);
    QuickSort(t,Begin+1,Right);
}

3.算法复杂度分析

由于是递归调用，时间复杂度为：O(nlogn)-最好，O(nlogn)-平均，O(n^2)-最差

空间复杂度，O(logn)-最好，O(n)-最差

4.算法效率测试 

 测试代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define   N 2000000
#define MAX 1000 
int t[N];
int Ysort(int arr[],int n)//检测排序完成 
{
	int i=0;
	while(i<n-1)
	{
		if(arr[i]>arr[i+1])
			return 78;
		i++;
	}
	return 89;
}
void prin(int t[],int begin,int end)
{
	while(begin<=end)
		printf(" %d ",t[begin++]);
	printf("\n");
}
void QuickSort(int t[],int Begin,int End)//快速排序 
{
    if(Begin>=End) return;
    int Left=Begin,Right=End;
    int tem=t[Begin];
    while(Begin<End)
    {
        while(Begin<End&&t[End]>=tem)
        {
            End--;
        }
        t[Begin]=t[End];
        while(Begin<End&&t[Begin]<=tem)
        {
            Begin++;
        }
        t[End]=t[Begin];
    }
    t[Begin]=tem;
    QuickSort(t,Left,Begin-1);
    QuickSort(t,Begin+1,Right);
}
int main()
{
    int i;
	int n=N;
	int max=MAX;
	printf("Size:%d\n",n);
	printf("Max :%d\n",max);
	for( i = 0; i < N; i++)
	{
		t[i] = rand()%MAX;
	}
	printf("%c  \n",Ysort(t,n));
	int begintime,endtime;
	begintime=clock();
	QuickSort(t,0,n-1);
	endtime = clock();
	printf("\n\nSort Running Time：%dms\n", endtime-begintime);
	printf("This is QuickSort.\n"); 
	printf("%c  \n",Ysort(t,n));
    return 0;
}

5.算法改进与优化

1.可以利用顺序栈消除递归

2.在元素较少时，改为插入排序

3.基准值改为随机选取