七种常见的排序算法

发表于

前言

本篇文章主要是复习总结算法四讲解的7种基本排序方法，包括：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序。注：统一按照升序进行排序。

通用接口及方法

interface Sortable {

    /**
     * 将数组进行排序，内部会修改数组元素顺序
     * @param array 待排序数组
     */
    <T extends Comparable<T>> void sort(T[] array);
}

public class SortUtils {

    /**
     * 交换数组中两个位置的元素
     * @param array 待交换的数组
     * @param first 第一个位置
     * @param second 第二个位置
     */
    public static <T> void exch(T[] array, int first, int second) {
        T temp = array[first];
        array[first] = array[second];
        array[second] = temp;
    }

    /**
     * 判断第一个位置的元素是否小于第二个位置元素
     * @param array 待测试数组
     * @param first 第一个位置
     * @param second 第二个位置
     * @return 是否小于
     */
    public static <T extends Comparable<T>> boolean less(T[] array, int first, int second) {
        return array[first].compareTo(array[second]) < 0;
    }
    
    /**
     * 判断第一个位置的元素是否小于第二个位置元素
     * @param array 待测试数组
     * @param first 第一个位置
     * @param second 第二个位置
     * @param comparator 比较器
     * @return 是否小于
     */
    public static <T> boolean less(T[] array, int first, int second, Comparator<T> comparator) {
        return comparator.compare(array[first], array[second]) < 0;
    }
    
    /**
     * 创建一个T[]
     * @param size 待创建的数组大小
     * @return 创建后的数组
     */
    @SuppressWarnings("unchecked cast")
    public static <T extends Comparable<T>> T[] createArray(int size) {
        return (T[]) new Comparable[size];
    }

    /**
     * 测试数组是否有序，所有元素都相同也会被认为有序
     * @param array 待测试数组
     * @return 是否有序
     */
    public static <T extends Comparable<T>> boolean test(T[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (less(array, i+1, i)) {
                return false;
            }
        }
        return true;
    }
}

各种排序方式

冒泡排序

代码实现

public class Bubble implements Sortable {

    @Override
    public <T extends Comparable<T>> void sort(T[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (less(array, j+1, j)) {
                    exch(array, j+1, j);
                }
            }
        }
    }
}

代码说明

外层循环表示一共需要冒出 N-1 个元素，内层循环将元素两两进行比较如果前面的元素大于后面的元素，就进行交换，一次循环后索引为 N-i-1 的元素就是剩余元素的最大值。

选择排序

代码实现

public class Selection implements Sortable {

    @Override
    public <T extends Comparable<T>> void sort(T[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (less(array, j, minIndex)) {
                    minIndex = j;
                }
            }
            exch(array, i, minIndex);
        }
    }
}

代码说明

外层循环表示一共需要选择 N-1 个元素，内层循环找出所有剩余元素中最小值所在的索引，然后将其与i进行交换，一次循环后索引为i的元素就是剩余元素的最小值。

与冒泡排序的比较：

这两种排序方式其实比较类似，主要有两点差异：

  1. 冒泡排序数组尾端是有序的（最大的在最后），而选择排序数组前端是有序的（最小的在最前）。

  2. 冒泡排序是通过不停的交换元素来选择出数组中的最大值，而选择排序是通过记录最小元素索引来选择的，这一点冒泡排序性能就稍差了。

插入排序

代码实现

public class Insertion implements Sortable {

    @Override
    public <T extends Comparable<T>> void sort(T[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (less(array, j, j - 1)) {
                    exch(array, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }
}

代码说明

外层循环表示每次要插入的元素，索引 [0, i-1] 表示已经有序的元素，i 从1开始，因为索引为0的一个元素可以认为已经有序，内层循环将待插入元素与前面有序的最大值进行比较，如果比原先最大值要小，那么交换，继续比较。这里有一个性能优化点，每次不交换元素而是拷贝 j-1 索引的元素到 j 索引，最后在插入点替换待插入元素即可，可以省去很多交换时间。

优化代码实现

public class InsertionOptimized implements Sortable {

    @Override
    public <T extends Comparable<T>> void sort(T[] array) {
        for (int i = 1; i < array.length; i++) {
            T target = array[i];
            int j;
            for (j = i; j > 0; j--) {
                if (target.compareTo(array[j-1]) < 0) {
                    array[j] = array[j-1];
                } else {
                    break;
                }
            }
            array[j] = target;
        }
    }
}

希尔排序

代码实现

public class Shell implements Sortable {

    @Override
    public <T extends Comparable<T>> void sort(T[] array) {
        int gap = 1;
        while (gap < array.length / 3) {
            gap = 3 * gap + 1;
        }
        while (gap >= 1) {
            for (int i = gap; i < array.length; i++) {
                for (int j = i; j >= gap; j--) {
                    if (less(array, j, j-gap)) {
                        exch(array, j, j-gap);
                    } else {
                        break;
                    }
                }
            }
            gap /= 3;
        }
    }
}

代码说明

首先是 gap（间隔）的选择，这个就按书上好了，没必要研究，接着就是典型的插入排序了，不过原先的插入排序间隔为1，现在为gap，插入排序后缩小 gap，再次进行进行插入排序，直到 gap 为1排序完毕。

归并排序

代码实现

public class Merge implements Sortable {

    @Override
    public <T extends Comparable<T>> void sort(T[] array) {
        T[] auxArray = createArray(array.length);
        sort(array, auxArray, 0, array.length - 1);
    }

    private <T extends Comparable<T>> void sort(T[] array, T[] auxArray, int low, int high) {
        if (low == high) {
            return;
        }
        int middle = (low + high) / 2;
        sort(array, auxArray, low, middle);
        sort(array, auxArray, middle + 1, high);
        merge(array, auxArray, low, high);
    }

    private <T extends Comparable<T>> void merge(T[] array, T[] auxArray, int low, int high) {
        System.arraycopy(array, low, auxArray, low, high - low + 1);
        int middle = (low + high) / 2;
        int left = low;
        int right = middle + 1;
        for (int i = low; i <= high; i++) {
            if (left > middle) {
                array[i] = auxArray[right++];
            } else if (right > high) {
                array[i] = auxArray[left++];
            } else if (less(auxArray, left, right)) {
                array[i] = auxArray[left++];
            } else {
                array[i] = auxArray[right++];
            }
        }
    }
}

代码说明

首先创建了一个辅助数组，接着递归将数组进行拆分，直到只有一个元素，然后将两个有序子数组进行合并（首次合并两个子数组里面其实各就一个元素），合并过程由于目标数组既要读取元素又要写入元素，因此合并前先把 low-high 中的元素拷贝入辅助数组，这使得后续目标数组只需要写入就行，最后根据左右指针判断选择左数组还是右数组。

代码分析

假设一共有8个元素，分别位于索引为 [0, 7] ，执行过程如下：

  1. 首先会将该数组拆分成 [0, 3] 、[4, 7] 两个子数组。
  2. 接着将 [0, 3] 数组再次拆分成 [0, 1] 、[2, 3] 两个子数组。
  3. 然后再将 [0, 1] 数组拆分成 [0] 、[1] 两个子数组。
  4. 由于两个子数组都只有一个元素，可以认为有序，将 [0]、[1] 两个子数组进行合并，合并后 [0, 1] 子数组有序。
  5. 接着再将 [2, 3] 数组拆分成 [2]、 [3]两个子数组。
  6. 由于两个子数组都只有一个元素，可以认为有序，将 [2]、[3] 两个子数组进行合并，合并后 [2, 3] 子数组有序。
  7. 两个子数组 [0, 1]、[2, 3] 都已经有序，将两个子数组进行合并，合并后 [0, 3] 子数组有序。
  8. 接着再将 [4, 7] 数组再次拆分成 [4, 5] 、[6, 7] 两个子数组。
  9. 然后再将 [4, 5] 数组拆分成 [4]、[5] 两个子数组。
  10. 由于两个子数组都只有一个元素，可以认为有序，将 [4]、[5] 两个子数组进行合并，合并后 [4, 5] 子数组有序。
  11. 接着再将 [6, 7] 数组拆分成 [6]、[7] 两个子数组。
  12. 由于两个子数组都只有一个元素，可以认为有序，将 [6]、[7] 两个子数组进行合并，合并后 [6, 7] 子数组有序。
  13. 两个子数组 [4, 5]、[6, 7] 都已经有序，将其进行合并，合并后 [4, 7] 子数组有序。
  14. 两个子数组 [0, 3]、[4, 7] 都已经有序，将其进行合并，合并后 [0, 7] 子数组有序。

快速排序

代码实现

public class Quick implements Sortable {

    @Override
    public <T extends Comparable<T>> void sort(T[] array) {
        sort(array, 0, array.length - 1);
    }

    private <T extends Comparable<T>> void sort(T[] array, int low, int high) {
        if (low >= high) {
            return;
        }
        int pivotIndex = partition(array, low, high);
        sort(array, low, pivotIndex);
        sort(array, pivotIndex + 1, high);
    }

    private <T extends Comparable<T>> int partition(T[] array, int low, int high) {
        int left = low;
        int right = high + 1;
        while (true) {
            while (less(array, ++left, low)) {
                if (left == high) {
                    break;
                }
            }
            while (less(array, low, --right)) {
                if (right == low) {
                    break;
                }
            }
            if (left >= right) {
                break;
            } else {
                exch(array, left, right);
            }
        }
        exch(array, low, right);
        return right;
    }
}

代码说明

首先取数组首个元素为中心点，将其放置于数组的某个索引使得该索引前的元素都小于等于它，该索引后的元素都大于等于它，这通过 left、right 指针实现，left 指针首先遍历 [low+1, high] 索引位置的元素，当发现一个元素大于等于中心点时停止，right指针接着遍历 [high, low] 索引位置的元素，当发现一个元素小于等于中心点时停止。这时如果发现 left、right还没相遇（left < right）那么交换下两者的元素，继续遍历。如果发现两者相遇（left >= right）注意这里大于等于都需要考虑（大于的情况为：left 在遍历过程中遇到一个大于中心点的值，那么 right 会停留在该值左边的索引。等于的情况为：left 在遍历过程中遇到一个等于中心点的值，那么 right 也会停留在改值索引处。）那么将 low、right 索引元素互换即可。这里再解释下为什么 right 不能到 low+1 就停止，原因是如果 low+1 索引位置的元素还是大于中心点，那么 right 必须到low，与中心点交换后才能保证结果正确。当放置中心点完毕后将数组划分为 [0, pivotIndex]、[pivotIndex+1, high] 两个子数组递归进行前面的操作，每次执行sort方法都会将一个元素放置到有序数组的合适位置。

代码分析

假设一共有8个元素：4，1，7，6，0，3，2，5，分别位于索引为 [0, 7]，执行过程如下：

  1. 选取第一个索引（0）为基准点，left 指针停在索引2位置，right 指针停在索引6位置，由于 left<right，交换索引2、6元素，数组改为：4，1，2，6，0，3，7，5。
  2. 继续遍历，left 指针停在了索引3位置，right 指针停在了索引5位置，由于 left<right，交换索引3、5元素，数组改为：4，1，2，3，0，6，7，5。
  3. 继续遍历，left 指针停在了索引5位置，right 指针停在了索引4位置，由于 left>right，交换第一个索引（0）与索引4元素，元素4的索引就被确定了，索引为4，数组改为：0，1，2，3，4，6，7，5。
  4. 执行子数组索引 [0, 3] 排序。
  5. 选取第一个索引（0）为基准点，left 指针停在索引1位置，right 指针停在索引0位置，由于 left>right，交换第一个索引（0）与索引0元素，元素0的索引就被确定了，索引为0，数组改为：0，1，2，3，4，6，7，5。这一轮相当于没有交换元素因为索引0元素正好是最小的。
  6. 执行子数组 [0, 0] 排序，由于只有一个元素直接返回。
  7. 执行子数组 [1, 3] 排序。
  8. 选取第一个索引（1）为基准点，left 指针停在了索引2位置，right 指针停在索引1位置，由于 left>right，交换索引（1）与索引1元素，元素1的索引就被确定了，索引为1，数组改为：0，1，2，3，4，6，7，5。这一轮相当于没有交换元素因为索引1元素正好是最小的。
  9. 执行子数组 [2, 3] 排序。
  10. 选取第一个索引（2）为基准点，left 指针停在了索引3位置，right 指针停在索引2位置，由于 left>right，交换索引（2）与索引2元素，元素2的索引就被确定了，索引为2，数组改为：0，1，2，3，4，6，7，5。这一轮相当于没有交换元素因为索引2元素正好是最小的。
  11. 执行子数组 [2, 2] 排序，由于只有一个元素直接返回。
  12. 执行子数组 [3, 3] 排序，由于只有一个元素直接返回。因此元素3的索引就被确定了，索引为3，数组改为：0，1，2，3，4，6，7，5
  13. 执行子数组 [5, 7] 排序。
  14. 选取第一个索引（5）为基准点，left 指针停在索引6位置，right 指针停在索引7位置，由于 left<right，交换索引6、7元素，数组改为：0，1，2，3，4，6，5，7
  15. 继续遍历，left 指针停在索引7位置，right 指针停在索引6位置，由于 left>right，交换索引（5）与索引6元素，元素6的索引就被确定了，索引为6，数组改为：0，1，2，3，4，5，6，7。
  16. 执行子数组 [5, 5] 排序，由于只有一个元素直接返回。因此元素5的索引就被确定了，索引为5，数组改为：0，1，2，3，4，5，6，7。
  17. 执行子数组 [7, 7] 排序，由于只有一个元素直接返回。因此元素7的索引就被确定了，索引为7，数组改为：0，1，2，3，4，5，6，7。

问题与优化方式

上面代码为二路快排，注意需要打乱元素顺序，原因是如果不打乱顺序可能会导致元素分割不均匀影响执行效率。试想对于一个本来就基本有序的数组，每次选取第一个元素当做基准点，那么几乎每次分割都会将数组分成 [low]、[low + 1, high] 两半，这样快排就退化成了 O(n^2) 的算法了。

还有另一个问题，二路快排对于重复元素多的数组执行效率并不高，因为其会导致若干不需要的比较，试想对于数组：5，5，3，6 ，使用二路快排首次排序数组会变成：3，5，5，6，于是会继续执行 [0, 0]、[2, 3] 两个子数组排序，其实对于索引2是不需要再次排序的因为其与基准值一样，要解决这个问题需要使用三路快排。

优化代码

public <T extends Comparable<T>> void sort(T[] array, int low, int high) {
    if (low >= high) {
        return;
    }
    int lt = low;
    int gt = high;
    int index = low + 1;
    while (index <= gt) {
        if (less(array, index, lt)) {
            exch(array, index++, lt++);
        } else if (less(array, low, index)) {
            exch(array, index, gt--);
        } else {
            index++;
        }
    }
    sort(array, low, lt - 1);
    sort(array, gt + 1, high);
}

代码说明

这段代码并不难，记住目标是将数组划分为 low ~ lt - 1、lt ~ gt、gt + 1 ~ high 三部分分别对应小于基准值，等于基准值，大于基准值。注意：由于 gt + 1开始都是大于基准值的，因此 index 只需遍历到 gt 即可，此外当遇到比基准值大的元素，与 gt 索引处的元素进行交换，不需要自增 index，由于交换过来的元素还不确定其大小。

堆排序

代码实现

public class Heap implements Sortable {
    @Override
    public <T extends Comparable<T>> void sort(T[] array) {
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            sink(array, i, array.length - 1);
        }
        int i = array.length - 1;
        while (i > 0) {
            exch(array, 0, i);
            sink(array, 0, --i);
        }
    }

    private <T extends Comparable<T>> void sink(T[] array, int index, int lastIndex) {
        while (2 * index + 1 <= lastIndex) {
            int j = 2 * index + 1;
            if (j < lastIndex && less(array, j, j + 1)) {
                j++;
            }
            if (less(array, index, j)) {
                exch(array, index, j);
            }
            index = j;
        }
    }
}

代码说明

首先构造堆，采用从最后一个非叶子节点依次下沉的方式，这样比从一个节点依次上浮效率要高，注意：最后一个非叶子节点索引为 N / 2 - 1。构造堆完毕后，将索引0（0 ~ i的最大值）与 i 进行交换，就跟冒泡排序一样将剩余元素最大值放到了数组末端，接着再执行索引0元素的下沉以维持堆定义，最后 i–（表示索引 [i+1, array.length - 1] 已经排好序，不再将其当做堆的一部分），依次循环。

复杂度比较

排序方法 平均时间复杂度 最好情况时间复杂度 最坏情况时间复杂度 空间复杂度 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(n^(1.3~2)) O(n) O(n^2) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定

注意点：

  1. 排序的稳定序指的是数组中的重复元素，排序前后相对位置是否会发生变化。比如：2，3，1（第一个），1（第二个）如果排序后一定为1（第一个），1（第二个），2，3那么表示该算法稳定，否则不稳定。

  2. 关于稳定性的一个典型应用场景，当需要将一个对象数组按照字段A、B进行排序，其中字段B的优先级高，一种方法是使用字段B先对数组进行排序，然后再对每个子数组按照字段A进行排序，这种做法当然可以但是相对比较麻烦，另一种方法是使用字段 A 先对数组进行排序，然后再对数组按照字段 B 进行排序，这时候需要注意如果排序算法是不稳定的那么将会出错。代码如下：

    public static void main(String[] args) {
        Country[] countries = new Country[6];
        countries[0] = new Country("China", "08:00");
        countries[1] = new Country("England", "07:00");
        countries[2] = new Country("America", "09:00");
        countries[3] = new Country("America", "06:00");
        countries[4] = new Country("China", "03:00");
        countries[5] = new Country("England", "09:20");
        Bubble sortable = new Bubble();
      	// Selection sortable = new Selection();
        sortable.sort(countries, new CountryTimeComparator());
        sortable.sort(countries, new CountryNameComparator());
        System.out.println(Arrays.toString(countries));
    }
    // Bubble outputs: [Country{name='America', time='06:00'}, Country{name='America', time='09:00'}, Country{name='China', time='03:00'}, Country{name='China', time='08:00'}, Country{name='England', time='07:00'}, Country{name='England', time='09:20'}
    // Selection outputs: [Country{name='America', time='06:00'}, Country{name='America', time='09:00'}, Country{name='China', time='08:00'}, Country{name='China', time='03:00'}, Country{name='England', time='07:00'}, Country{name='England', time='09:20'}]

    这段代码对Countries数组进行了两次排序，首先使用time字段排序，接着使用name字段排序，注意这里使用了冒泡排序其是稳定的，因此结果正确，而采用选择排序因为其实不稳定的，结果很有可能是错误的。

  3. 上面写的冒泡排序就算是 最好情况时间复杂度也是 O(n^2)，不过可以进行改进，使得最好情况时间复杂度为 O(n)。代码如下：

    public <T extends Comparable<T>> void sort(T[] array) {
          for (int i = 0; i < array.length - 1; i++) {
              boolean didSwap = false;
              for (int j = 0; j < array.length - i - 1; j++) {
                  if (!less(array, j, j+1)) {
                      exch(array, j, j+1);
                      didSwap = true;
                  }
              }
              if (!didSwap) {
                  return;
              }
          }
    }

    通过添加标记 didSwap，如果冒泡过程一次都没进行交换，那么说明数组已经有序了，就可以直接结束。当数组本来就是有序时时间复杂度就变成了 O(n)。

  4. 希尔排序的最好情况时间复杂度为 O(n)，原因与插入排序一致，当数组本来就是有序的时候不需要插入。

  5. 二路快速排序的最佳时间复杂度与平均时间复杂度一致都是 O(nlogn)，三路快排的最佳时间复杂度为 O(n) （当所有元素都相同时，不需要再分子数组），平均时间复杂度为 O(nlogn)。快排的最坏情况时间复杂度为 O(n^2)（每次只能分成一个子数组时），由于需要进行递归因此其需要额外空间，一般空间复杂度为 O(logn)，最坏空间复杂度为 O(n)。

0%