八种排序算法可以按照如图分类,本文主要介绍快速排序。

 交换排序算法之快速排序 算法

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

交换排序

所谓交换,就是序列中任意两个元素进行比较,根据比较结果来交换各自在序列中的位置,以此达到排序的目的。


快速排序

快速排序的思想很简单,就是先把待排序的数组拆成左右两个区间,左边都比中间的基准数小,右边都比基准数大。接着左右两边各自再做同样的操作,完成后再拆分再继续,一直到各区间只有一个数为止。

举个例子,现在我要排序 4、9、5、1、2、6 这个数组。一般取首位的 4 为基准数,第一次排序的结果是:

2、1、4、5、9、6

可能有人觉得奇怪,2 和 1 交换下位置也能满足条件,为什么 2 在首位?这其实由实际的代码实现来决定,并不影响之后的操作。

以 4 为分界点,对 2、1、4 和 5、9、6 各自排序,得到

1、2、4、5、9、6

不用管左边的 1、2、4 了,将 5、9、6 拆成 5 和 9、6,再排序,至此结果为

1、2、4、5、6、9

为什么把快排划到交换排序的范畴呢?因为元素的移动也是靠交换位置来实现的。


算法实现

大体思路已经有了,接下来就是具体实现。

相信大家已经看出来了,算法的实现需要用到递归(拆分区间之后再对每个区间作同样的操作)。所有关于算法实现的阐述仅以一次排序为例。

基准数一般取数组首位的数,而最终基准数是要放在中间位置的。我们使用一个临时变量 stard 来保存选取的基准值,其余元素根据比较结果决定是否交换位置。

我们分别得到数组的首元素和尾元素的下标,作为头指针和尾指针。先尾指针开始,如果对应的数比基准值大,尾指针向前移动,直到遇到比基准值小的为止。此时将尾指针和头指针对应的数值进行交换。轮到头指针,如果对应的数比基准值小,头指针向后移动,直到遇到比基准值大的为止。此时将尾指针和头指针对应的数值进行交换。再到尾指针,再到头指针,直到头尾指针重合为止。此时将 stard 的值赋给指针重合处下标,一趟排序完成。

用 Java 实现的快速排序如下

/**
 * 快速排序
 *
 * @param arr 待排序的整型数组
 * @param start 起始下标
 * @param end 末尾下标
 */
public static void quicksort(int[] arr, int start, int end) {

    if (start < end) {
        // 把数组中第 0 个数字作为基准数
        int stard = arr[start];
        //  记录需要排序的下标
        int low = start;
        int high = end;
        // 循环找到比基准数大的数和比基准数小的数
        while (low < high) {
            // 右边的数字比基准数大
            while (low < high && arr[high] >= stard) {
                high--;
            }
            // 使用右边的数替换左边的数
            arr[low] = arr[high];
            // 左边的数字比基准数小
            while (low < high && arr[low] <= stard) {
                low++;
            }
            // 使用左边的数替换右边的数
            arr[high] = arr[low];
        }
        // 把标准值赋给下标重合的位置
        arr[low] = stard;
        // 处理所有小的数字
        quicksort(arr, start, low);
        // 处理所有大的数字
        quicksort(arr, low + 1, end);
    }
}

我还在网上看到另一种实现方式,个人觉得第二种虽然更符合交换这一概念,但在交换次数和空间消耗上有一丢丢逊色。

/**
 * 快速排序
 *
 * @param arr 待排序的整型数组
 * @param start 起始下标
 * @param end 末尾下标
 */
public static void quicksort(int[] arr, int start, int end) {

    if (start < end) {
        // 把数组中第 0 个数字作为基准数
        int stard = arr[start];
        //  记录需要排序的下标
        int low = start;
        int high = end;
        // 循环找到比基准数大的数和比基准数小的数
        while (low < high) {
            // 右边的数字比基准数大
            while (low < high && arr[high] >= stard) {
                high--;
            }
            // 左边的数字比基准数小
            while (low < high && arr[low] <= stard) {
                low++;
            }
            // 相等继续循环
            if (low < high && arr[low] == arr[high]) {       
                low++;            
            } else {
               	// 左边的数和右边的数交换位置
                int temp = arr[low];                
                arr[low] = arr[high];                
                arr[high] = temp;            
            }  
        }
        // 处理所有小的数字
        quicksort(arr, start, low);
        // 处理所有大的数字
        quicksort(arr, low + 1, end);
    }
}

快速排序稳定性

快速排序是不稳定的算法,只要举出一个实例,即可说明它的不稳定性。所谓不稳定,即序列中如果存在多个相同的元素,经过排序后它们的顺序位置发生变化,就是不稳定的。

假设在数列中存在 a[i]=a[j],若在排序之前,a[i]在a[j]前面,并且排序之后,a[i] 仍然在 a[j] 前面,则这个排序算法是稳定的。


快速排序性能

快速排序的一次划分算法从两头交替搜索,直到 low 和 high 重合,因此其时间复杂度是 O(n)。这里要注意时间复杂度的定义,常数是忽略不计的,可能第二次划分只有原长度的一半,即 (1/2)*n,但还是认为是 O(n)。

整个快速排序算法的时间复杂度与划分的趟数有关。理想的情况是,每次划分所选择的中间数恰好将当前序列几乎等分。第一次划分变成两个数组,第二次划分变成四个数组,最后一定会变成 n 个数组,划分次数即是 log2n 次,便可得到长度为1的子表。这样,整个算法的最优时间复杂度为 O(nlog2n)。

最坏的情况是,每次所选的中间数是当前序列中的最大或最小元素,这使得每次划分所得的子表中一个为空表,另一子表的长度为原表的长度减一。这样,长度为 n 的数据表的快速排序需要经过 n 趟划分,使得整个排序算法的时间复杂度为 O(n2)。

快速排序的平均时间复杂度也是 O(nlogn)。

从空间性能上看,尽管快速排序需要的辅助空间也就是个常数级 O(1) ,但用到了递归,每一次划分都需要开辟一块辅助空间。

因此最优的情况下空间复杂度为 O(log2n) ,最差的情况下空间复杂度为 O( n ) 。


扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄