快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

注意：每次都是右哨兵先出发，且左哨兵大于右哨兵时结束

代码：

在此代码中，函数quickSort()中左哨兵是i,left,右哨兵是j,right

#include <stdio.h>

void quickSort(int *a,int left,int right)
{
    int i,j,t,temp;
    if(left > right)//左哨兵大于右哨兵结束
        return;
    temp = a[left]; //存储基准数
    
    i = left;
    j = right;
    while(i != j)
    {
        //先右哨兵出发
        while(a[j] >= temp && i < j)
            j--;
        //在左哨兵出发
        while(a[i] <= temp && i < j)
            i++;
        
        //找到后交换两个数在数组中的位置
        if(i < j)//首先需要判断哨兵i和哨兵j没有相遇
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        
    }
    
    //最后将基准树归位
    a[left] = a[i];
    a[i] = temp;
    
    //递归处理
    //i-1.i+1是因为i现在是基准点，需要排除
    quickSort(a,left,i - 1);
    quickSort(a,i + 1,right);
}

int main(void)
{
    int i;
    int a[10] = {5,8,2,6,0,1,4,7,3,9};
    printf("Front:");
    for(i = 0;i < 10;i ++)
        printf("%d ",a[i]);
    quickSort(a,0,9);
    printf("\nBack: ");
    for(i = 0;i < 10;i ++)
        printf("%d ",a[i]);
    getchar();
}

运行结果：

Front:5 8 2 6 0 1 4 7 3 9
Back: 0 1 2 3 4 5 6 7 8 9

时间复杂度：

最差时间复杂度和冒泡排序是一样： O(N²)，
平均时间复杂度为 ：(NlogN)。

总结:

快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的，每次排序的时候设置一个基准点，将小于基准点的数全部放到基准点的左边，将大于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大的多，因此总的比较和交换次数就少，速度自然就提高了。