快速排序

007 快速排序

一、算法介绍

快速排序是由冒泡排序改进而得的。作为目前内排序算法中最快的排序算法，快速排序通常明显比时间效率同为 O(nlogn) 的其他算法更快。其基本思想是：在待排序的n个元素中任取一个（通常取第一个）作为基准(pivot)，把该元素放到适当的位置，数据序列被此元素划分为两部分。比该元素小的放在前一部分，大的放在后一部分，这样基准元素就被放在了适当的位置，即归位。然后分别再对划分出的两部分进行同样的操作，直到划分的部分只有一个元素或为空。这一过程中大树一直在往后移，小数一直往前移，所以最终序列一定是有序的。显然，快速排序也用到了分治的策略。因此，快速排序又称分区交换排序。

二、算法分析

在分区时，我们可以理解成把在首位置的元素拿出来，然后从后往前找把乱序（比基准小）的数拿出来填进去，再从前往后找把比基准大的数填到刚刚被拿来填空的数留下的空里，一直循环，直到两头碰在一起了，这时就把基准填进去。这样一趟排序就完成了。

如图所示

设有一数组a[10]，取a[0]，38作为基准，将其取出保存到tmp中

空用黄色标出

1	2	3	4	5	6	7	8	9
38	24	57	91	16	4	42	20	88	64

从后往前找，把遇到的第一个小于38的数 即a[7]=20取出填进去

1	2	3	4	5	6	7	8	9
20	24	57	91	16	4	42	88	64

从前往后找，把遇到的第一个大于38的数 即a[2]=57取出填入

1	2	3	4	5	6	7	8	9
20	24	91	16	4	42	57	88	64

接着从后往前找，把小于38的数 即a[5]=4取出填入

1	2	3	4	5	6	7	8	9
20	24	4	91	16	42	57	88	64

接着从前往后找，把大于38的数 即a[3]=91取出填入

1	2	3	4	5	6	7	8	9
20	24	4	16	91	42	57	88	64

接着从后往前找，把小于38的数 即a[4]=16取出填入

1	2	3	4	5	6	7	8	9
20	24	4	16	91	42	57	88	64

这时，再从前往后找，发现和后面的碰头了，这时就可以把存放在tmp中的a[0]填进去了

1	2	3	4	5	6	7	8	9
20	24	4	16	38	91	42	57	88	64

这时我们可以发现38两边的数是满足要求的，第一趟排序就完成了，然后需要对两部分进行相同的操作，直到分出的部分的元素个数为1或0

三、算法代码

void QuickSort(int a[], int s, int e) //当前部分头尾位置的索引
{
    int i=s, j=e;
    int tmp=a[s]; //取出基准
    if(s<e) //元素个数大于1
    {
        while(i<j)
        {
            while(i<j && a[j]>tmp) //从后向前找小于基准的数
                j--;
            //无须if(i<j),如果因i=j结束循环，a[i] = a[j]也无影响
            a[i] = a[j];
            while(i<j && a[i]<tmp) //从前向后找大于基准的数
                i++;
            a[j] = a[i];
        }
        a[i] = tmp; //i=j，前后碰头了，就把基准填在碰头的地方
        
        //划分结束，对基准的前后部分再进行相同的操作
        QuickSort(a, s, i-1);
        QuickSort(a, i+1, e);
    }
}
           

运行结果