目录

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=tem)
        {
            End--;
        }
        t[Begin]=t[End];
        while(Begin 

3.算法复杂度分析

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

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

4.算法效率测试 

 

 测试代码

#include
#include
#include
#define   N 2000000
#define MAX 1000 
int t[N];
int Ysort(int arr[],int n)//检测排序完成 
{
	int i=0;
	while(iarr[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=tem)
        {
            End--;
        }
        t[Begin]=t[End];
        while(Begin 
5.算法改进与优化 
1.可以利用顺序栈消除递归
 
2.在元素较少时，改为插入排序
 
3.基准值改为随机选取