一、引言

练好基本功，面试中经常考察的排序算法有快速排序、归并排序、插入排序、冒泡排序、堆排序和计数排序等。学习排序算法时需要关注以下几点：

  1. 时间复杂度
  2. 空间复杂度
  3. 排序算法的稳定性
  4. 算法适用的场景

二、快速排序

快排基本思路是找一个基准元素 pivot，把数组分成 2 部分（这 2 部分都不包括pivot），再分别递归快排这 2 个子数组。平均时间复杂度 O(NlogN),空间复杂度O(logN)。

相同大小的元素在比较过程中会改变相对顺序（比如最右边的先交换到左边），所以快排是不稳定排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 /**
 * 快速排序，先找到 pivot 元素在数组中排序后的最终位置；再对 pivot 左边区间和右边区间的子数组继续进行快速排序
 * @param arr
 * @param start
 * @param end
 */
public void quicksort(int[] arr, int start, int end) {
    if(start >= end) return;
    int left = start, right = end;
    int pivot = arr[left];
    while(left < right) {
        while(left < right && arr[right] >= pivot) {
            --right;
        }

        if(left < right) {
            arr[left] = arr[right];
        }
        while(left < right && arr[left] <= pivot) {
            ++left;
        }

        if(left < right) {
            arr[right] = arr[left];
        }
    }
    arr[left] = pivot;

    quicksort(arr, start, left -1);
    quicksort(arr, left + 1, end);
}

三、归并排序

归并排序先把数组拆分为 2 个子数组并对子数组排序，对 2 个排号序的子数组进行归并。对子数组排序是一个递归调用过程，只是问题空间变小了，也就是能收敛。

相对快速排序，归并排序优点是算法是稳定的，也就是相同元素相对位置不会变，缺点是需要 O(N)的空间复杂度。

归并排序和快速排序都有分而治之的设计思想，把一个大的问题空间拆分成小的问题空间。如果按拆分类似 2 叉树的角度来看，快速排序是前序遍历（先找 pivot 节点位置），归并排序是后序（归并操作在最后）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 归并排序 2：内存只分配一次
 * @param arr：原数组
 * @param temp：临时数组，和原数组大小一致
 * @param left：待排序数组左边界。需要指定的原因是递归调用需要修改待排序子数组边界
 * @param right：待排序数组右边界
 */
public void mergeSort2(int[] arr, int[] temp, int left, int right) {
    if(left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort2(arr, temp, left, mid);
    mergeSort2(arr, temp, mid + 1, right);

    merge2(arr, temp, left, mid, right);
}

/**
 * 合并数组，对应归并数组 2。temp 数组 k 位置也可以从 0 开始，只要保证来回复制时位置一致即可（程序没有并发）
 * @param arr：原始数组
 * @param temp：临时数组
 * @param start：左子数组开始位置
 * @param mid：二分的中间位置，并归入左子数组右边界
 * @param end：右子数组结束位置
 */
private void merge2(int[] arr, int[] temp, int start, int mid, int end) {
    int i = start, j = mid + 1, k = start;
    while(i <= mid && j <= end) {
        if(arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while(i <= mid) temp[k++] = arr[i++];
    while(j <= end) temp[k++] = arr[j++];

    // 原始数组从临时数组中还原
    System.arraycopy(temp, start, arr, start, end - start + 1);
}

四、希尔排序

希尔排序是对插入排序的优化，解决插入排序只能在小范围内逐步排序问题。找一个增量序列，数组按增量分组后做插入排序。这样即使数组中两个数隔的比较远，也可能提前排好序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 /**
 * 希尔排序，插入排序的优化。找一个增量序列，数组按增量分组后做插入排序。
 * @param arr
 */
public void shellSort(int[] arr) {
    // 步长为 k，这个增量序列不是最优的，合适的增量序列是希尔排序的关键
    int gap = arr.length / 2;
    while(gap > 0) {
        // 步长为 gap，则分为 gap 组。每组做插入排序
        for(int k = 0; k < gap; k++) {
            // 找到每组的数
            for(int i = gap + k; i < arr.length; i += gap) {
                // 插入排序
                int temp = arr[i];
                int pre = i - gap;
                while(pre >= 0 && arr[pre] > temp) {
                    arr[pre + gap] = arr[pre];
                    pre -= gap;
                }
                arr[pre + gap] = temp;
            }

        }

        gap /= 2;
    }
}

五、堆排序

采用最大堆来排序，涉及到堆调整（根元素也就是第一个元素最大，父元素值大于子元素值）。建堆时从下到上（从第一个非叶子节点）开始，排序时把最大元素交换到“已排序区”的开始位置，同时从上到下调整，使得“未排序区”满足堆特性。

注意堆指的是完全二叉树（不一定是满二叉树），通过一个数组来表示。这使得父子节点满足一些有趣的特征比如父节点索引为 i 时（索引从 0开始），左子节点为：2 * i + 1, 右子节点为：2 * (i + 1)，最后一个非叶子节点为 （n - 1）/ 2，n 是数组大小。

堆排序时数组分为 2 部分，左边为“未排序区”，右边为“已排序区”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
     * 向下调整堆。
     * 建堆时从最后一个非叶子节点开始直到叶节点
     * 排序时从根节点到未排好序的最后一个节点
     *
     * @param arr
     * @param s：开始节点位置
     * @param t：结束节点位置
     */
    public static void heapAdjust(int[] arr, int s, int t) {

        for (int j = s; j < t; ) {
            int left = 2 * j + 1;
            int right = left + 1;
            int max = left; //左右子节点中小的节点,默认为左子节点
            if (left > t) {
                break; //exit now
            } else if (right <= t && arr[right] > arr[left]) {
                max = right;
            }

            if (arr[j] < arr[max]) {
                swap(arr, j, max);
                j = max;
            } else {
                break; //exit now
            }
        }
    }

    /**
     * 最大堆堆排序
     *
     * @param arr
     */
    public static void sort(int[] arr) {

        //从最后一个非叶节点起调整堆，使得左右子节点值都比该分支节点值小
        for (int i = (arr.length - 1) / 2; i >= 0; --i) {
            heapAdjust(arr, i, arr.length - 1);
        }

        //把堆顶元素与最后一个节点交换，然后重新调整堆，循环arr.length-1次即可得到升序排列
        for (int j = arr.length - 1; j >= 1; --j) {
            swap(arr, 0, j);

            heapAdjust(arr, 0, j - 1);
        }
    }

六、Java 中 Arrays.sort使用的排序算法

多个排序算法的结合，按数据量从大到小依次用到了归并排序、快速排序和插入排序。

七. 算法复杂度

时间复杂度主要是平均时间复杂度。

算法 平均时间复杂度 空间复杂度 算法稳定性
插入排序 O(N^2) O(1) 稳定
冒泡排序 O(N^2) O(1) 不稳定
快速排序 O(NlogN) O(logN) 不稳定
归并排序 O(NlogN) O(N) 稳定
堆排序 O(NlogN) O(1) 不稳定
希尔排序 O(NlogN) O(1) 不稳定
计数排序 O(N+K) O(K) 稳定

具体算法时间或者空间复杂度以及稳定性可以参考维基百科。

六、总结

本文介绍了几种常见的算法面试中遇到的排序算法，实现算法的方式很多，网上找一大把，读者主要从算法思想来了解算法的优势和劣势。一般基于比较和交换的排序算法平均时间复杂度到 O(Nlog(N))已经不错了，插入、选择和冒泡等排序算法平均时间复杂度为O(N^2)。还有一种更牛的基于计数的时间复杂度为O(N+K)，K为数的范围，当然这种需要待排序的数在一定范围内。

本文中使用的代码请参考github