快速排序-Quick Sort

基础版本--后续有机会出详细优化版本

★

• 快速排序由于排序效率在同为 的几种排序方法中效率较高，因此经常被采用。
• 再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。
• 总的说来，要直接默写出快速排序还是有一定难度的，因此本人就自己的理解对快速排序作了下白话解释，希望对大家理解有帮助，达到快速排序，快速搞定。

”

★

- 算法思想：

• 快速排序是冒泡排序的改进算法。它也是通过不断比较和移动交换来实现排序的，只不过它的实现增大了记录的比较和移动的距离， 将关键字较大的元素直接放到枢轴元素(随机或者特定位置的元素)后面，关键字较小的元素直接放到枢轴元素前面，从而减小了比较次数和交换次数。
• (1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 "基准"（pivot） 注: 此处选择中间位置元素为 pivot 元素
• (2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准元素左边的元素都比基准元素小，在基准元素右边的元素都比基准元素大。
• (3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

”

实例演示

★

- 后续操作类似，不再演示

”

---

代码如下:

// int a[] 待排序数组
// int left 数组左边界
// int right 数组右边界
//快速排序
void quick_sort(int a[], int left, int right) {
    //数组为空或者只有一个数
    if (left >= right)
        return;

    //分界点,枢轴元素(中间位置元素)
    int pivot = a[left + right >> 1];

    //两侧指针(数组两边界之外, i j 同时往中间移动)
    int i = left - 1, j = right + 1;

    //不断循环
    while (i < j) {
        //左右指针向中间移动
        do {
            i++;
        } while (a[i] < pivot);  //遇到第一个大于等于 pivot的值
        do {
            j--;
        } while (a[j] > pivot);  //遇到第一个小于等于 pivot的值

        //没有相遇
        if (i < j)
            //交换a[i], a[j]
            swap(a[i], a[j]);  // swap 函数在冒泡排序函数中已出现过
    }
    //递归处理左右两端
    quick_sort(a, left, j);
    quick_sort(a, j + 1, right);
}

1.3    算法总结

• 在最优情况下，Partition(划分)每次都划分得很均匀，如果排序 个关键字，其递归树的深度就为 （ 表示不大于 的最大整数），即仅需递归 次，需要时间为 的话，第一次 Partiation 应该是需要对整个数组扫描一遍，做 n 次比较。然后，获得的枢轴将数组一分为二，那么各自还需要 的时间 （注意:是最好情况，所以平分两半）。
• 于是不断地划分下去，我们就有了下面的不等式推断:

• 在最优的情况下 ，快速排序的时间复杂度为

• 在最坏的情况下 , 待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列， 注意: 另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行 次递归调用，且第 次划分需要经过 次关键字的比较才能找到第 个记录，也就是枢轴的位置,因此比较次数为:

• 在最坏情况下 快速排序时间复杂度为 。

• 平均的情况 ，设枢轴的关键字应该在第 的位置 ，那么：

• 平均情况下, 快速排序时间复杂度为 。

• 空间复杂度分析: 主要是递归造成的栈空间的使用，最好情况，递归树的深度为 ，其空间复杂度也就为 ，最坏情况，需要进行 次递归调用，其空间复杂度为 ，平均情况，空间复杂度也为 。

• 稳定性分析: 由于关键字的比较和交换是跳跃进行的,快速排序是不稳定的。