排序算法总结

各种排序算法的性能比较以及优化。

---

各排序算法性能表

算法	平均情况	最好情况	最坏情况	辅助空间	稳定性
快速排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(n^2)$	$O(log_2n)$	不稳定
归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(n)$	稳定
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(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^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
计数排序
基数排序
桶排序

补充内容

时间复杂度的表示方法：

设f和g是定义域为自然数集N上的函数，若存在正数c和$n_0$，使得对所有$n\geq n_0$有

$0\leq f(n) \leq cg(n)$记作：$f(n) = O(g(n))$ 表示g(n)是f(n)的渐近上界。

$0\leq cg(n) \leq f(n)$记作：$f(n) = \Omega(g(n))$ 表示g(n)是f(n)的渐近下界。

$0\leq f(n) < cg(n)$记作：$f(n) = o(g(n))$ 表示g(n)是f(n)的高阶。

$0\leq cg(n) < f(n)$记作：$f(n)=w(g(n))$ 表示g(n)是f(n)的低阶。

若$f(n)=O(g(n))$且$f(n)=\Omega(g(n))$记作：$f(n) = \Theta(g(n))$ 表示g(n)与f(n)同阶。

定理：在最坏情况下，任何比较排序算法都需要做$\Omega(n\log_2n)$次比较。(最坏情况下的比较次数 = 决策树的高度h，由Striling公式得 $h\geq \log_2(n!)=\Theta(n\log_2n)$ ，n!表示决策树中叶子节点的个数)

推论：堆排序和归并排序都是渐近最优的比较排序算法。

决策树

决策树是一颗完全二叉树，可以表示在给定输入规模下某一特定算法对所有元素的比较操作。

下图为三个元素作为输入序列的决策树，节点里的数值表示元素下表，叶节点表示通过比较后得到的输出序列。

对于n个元素一共有n!种排列，都会出现在决策树的叶子节点上。

定理1：N个互异数的数组的平均逆序数是N(N-1)/4。

这个定理意味着插入排序平均时间复杂度是$O(n^2)$，同时也提供了只交换相邻元素的任何算法的一个很强的下界$\Omega(n^2)$。

定理2：通过交换相邻元素进行排序的任何算法平均都需要$\Omega(n^2)$时间。

Java中的Comparable[]数组

在一些排序算法的源码中，我们可能会看到有些函数的传入常数是Comparable[] a;，这样写的意思是，这个参数可以是任何实现了Comparable接口的类，例如Integer[], Double[], String[]这些类，当然我们可以自己写一个实现Comparable接口的类作为传入参数。

这样写可以增强代码的复用性，当我们新写一个类，需要用这个方法排序的时候，只要在新类里实现Comparable里的comparaTo()方法，这个类的对象就可以作为该排序函数的传入参数。

用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使小规模问题中方法的调用过于频繁，所以改进对它们的处理方法就能改进整个算法。

---

快速排序 Quicksort

快速排序使用了分治法的思想，排序过程分为三步：

1. 分解：选定数组中最后一个元素作为划分元素，小于该元素的数放到数组前面，大于该元素的数放到数组后面。

2. 解决：通过递归调用对两个子数组进行排序。

3. 合并：不需要合并，原数组已经有序。

   

public class Quicksort {
    public void quicksort(int[] nums, int start, int end) {
        if (end <= start) return;
        int q = partition(nums, start, end);
        quicksort(nums, start, q-1);
        quicksort(nums, q+1, end);
    }
    public int partition(int[] nums, int start, int end) {
        int x = nums[end];
        int i = start-1;
        for (int j = start; j <= end-1; j++) {
            if (nums[j] <= x){
                i++;
                swap(nums, i, j);
            }
        }
        swap(nums, i+1, end);
        return i+1;
    }
    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

性能分析

快速排序通常是实际应用中最好的排序算法，因为平均时间复杂度$\Theta(n\log_2n)$中隐含的常数因子非常小，而且空间复杂度为$O(1)$。

时间复杂度：

• 最好情况：partition划分得到的两个子问题的规模都不大于n/2，这时候快速排序的时间性能为$\Theta(n\log_2n)$。
• 最坏情况：partition划分得到的两个字问题一个包含n-1个元素另一个包含0个元素，这时候快速排序的时间性能为$\Theta(n^2)$。
• 平均情况：快速排序的平均运行时间更接近最好情况是$O(n\log_2n)$。

空间复杂度：

• 最坏情况下：partition划分的子问题规模每次减少1，所以会进行n次递归，递归树的深度是$O(n)$。
• 除了最坏情况下，任何常数比例的划分都会产生深度为$\Theta(\log_2n)$的递归树。

性能优化

思路1: 快速排序+插入排序

我们知道对于小数组快速排序比插入排序慢，因为递归，快速排序quicksort()方法在小数组中也会调用自己，因此在排序小数组时应该切换到插入排序。

public void quicksort(int[] nums, int start, int end) {
    if (end - start <= M) { //数组长度小于M时转换为插入排序
        Insertionsort.sort(nums, start, end);
        return;
    }
    int q = partition(nums, start, end);
    quicksort(nums, start, q-1);
    quicksort(nums, q+1, end);
}

转换参数M的最佳值和系统相关，但是5～15之间的任意值在大多数情况下都能令人满意。

思路2: 随机化版本的快速排序

由于快速排序的运行时间依赖于划分是否平衡，而平衡与否依赖于选择划分元素的算法，所以第一种优化思路，是针对选取划分元素的算法进行优化。

与每次选取数组结尾元素作为拆分元素不同，我们每次从数组中随机选取一个元素与结尾元素交换，通过随机抽样我们保证了拆分元素是随机的从数组中选取的，因为拆分元素是随机选取的，所以在平均情况下对数组的划分是比较均衡的。

public void quicksort(int[] nums, int start, int end) {
    if (start >= end) return;
    int q = randomPartition(nums, start, end);
    quicksort(nums, start, q-1);
    quicksort(nums, q+1, end);
}
public int randomPartition(int[] nums, int start, int end) {
    Random r = new Random();
    int index = start + r.nextInt(end - start);
    swap(nums, index, end);
    return partition(nums, start, end);
}
public int partition(int[] nums, int start, int end) {
    int x = nums[end];
    int i = start-1;
    for (int j = start; j <= end-1; j++) {
        if (nums[j] <= x){
            i++;
            swap(nums, i, j);
        }
    }
    swap(nums, i+1, end);
    return i+1;
}

随机化版本的快速排序还可以进一步优化。

思路2进一步优化：三数取中划分

对随机化版本的快速排序做进一步优化，是要从子数组中更细致地选择拆分元素，而不是简单地随机选择，常用做法是三数取中划分：从子数组中随机选出三个元素，取其中位数作为拆分元素，会得到更好的拆分效果。

public void quicksort(int[] nums, int start, int end) {
    if (start >= end) return;
    int q = randomThreeMedianPartition(nums, start, end);
    quicksort(nums, start, q-1);
    quicksort(nums, q+1, end);
}
public int randomThreeMedianPartition(int[] nums, int start, int end) {
    Random r = new Random();
    int index = start + r.nextInt(end - start);
    if (end - start > 3){
        int a = start + r.nextInt(end - start);
        int b = start + r.nextInt(end - start);
        int c = start + r.nextInt(end - start);
        index = nums[a] > nums[b] ? (nums[a] < nums[c] ? a : (nums[b] > nums[c] ? b : c)) : (nums[b] < nums[c] ? b : c);
    }
    swap(nums, index, end);
    return partition(nums, start, end);
}
public int partition(int[] nums, int start, int end) {
    int x = nums[end];
    int i = start-1;
    for (int j = start; j <= end-1; j++) {
        if (nums[j] <= x){
            i++;
            swap(nums, i, j);
        }
    }
    swap(nums, i+1, end);
    return i+1;
}

思路3: 三向切分快排 3-Way Partition Quicksort

在前面的优化过程中，我们都没有考虑过数组中元素的情况，如果数组中存在很多重复元素，那么算法还有很大的优化空间。

如果待排序数组中存在大量重复数字，那么我们要修改原来的partition()函数，它返回两个数组下标$lt,gt$其中$start \leq lt \leq gt \leq end$ ，并且：

• A[start～lt-1]中的元素都小于A[start]
• A[lt～gt]中的元素都等于A[start]
• A[gt+1～end]中的元素都大于A[start]

这样分类后，相等的元素就不会被包含到递归排序的子数组中，这种算法就是3-Way Partition Quicksort(三向切分快速排序)。

对于存在大量重复元素的数组，这种方法比标准的快速排序的效率高得多，例如，对于只有若干不同值的随机数组，归并排序的时间复杂度是$O(n\log_2n)$，而三向切分快速排序则是$O(n)$。

**对于包含大量重复元素的数组，三向切分快速排序将排序时间从线性对数级降低到了线性级别。**这种对重复元素的适应性使得三向切分的快速排序成为排序库函数的最佳算法选择。

public void quick3Way(int[] nums, int start, int end) {
    if (end <= start) return;
    int x = nums[start]; //这里可以随机选取或者三数取中选取拆分元素
    int lt = start, i = start+1, gt = end;
    while (i <= gt) {
        if (nums[i] < x) swap(nums, lt++, i++);
        else if (nums[i] > x) swap(nums, i, gt--);
        else i++;
    }
    quick3Way(nums, start, lt-1);
    quick3Way(nums, gt+1, end);
}

这个算法还可以继续优化，在数组中重复元素不多的普通情况下，它比标准的二分法多使用了很多次交换，因为交换都发生在和切分元素不相等的元素上。所以，我们可以只对少数的重复元素进行交换。

Quick 3-Way Partition Quicksort 快速三向切分排序

快速三向切分排是将重复元素放置于子数组两端的方式实现一个更快的排序算法。

---

归并排序 Mergesort

和快速排序一样，归并排序也是基于分治法的思想，排序过程分三步：

1. 分解：将n个元素分成两份，每份n/2个元素。
2. 解决：递归排序两个字序列。
3. 合并：合并两个已排序的子序列。

算法运行过程如下所示：

自顶向下的归并排序

public class Mergesort {
    public void mergesort(int[] nums, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) >> 1;
        mergesort(nums, start, mid); //递归对前半部分数组排序
        mergesort(nums, mid + 1, end); //递归对后半部分数组排序
        merge(nums, start, mid, end); //将排序后的两个字数组合并
    }
    public void merge(int[] nums, int start, int mid, int end) {
        int len1 = mid - start + 1;
        int len2 = end - mid;
        int[] L = new int[len1 + 1];
        int[] R = new int[len2 + 1];
        for (int i = start, j = 0 ; i <= mid; i++) {
            L[j++] = nums[i]; //将nums[]数组的左半部分复制到L[]数组中
        }
        L[len1] = Integer.MAX_VALUE; //哨兵节点，表示数组到达末尾
        for (int i = mid + 1, j = 0; i <= end; i++) {
            R[j++] = nums[i]; //将nums[]数组的右半部分复制到R[]数组中
        }
        R[len2] = Integer.MAX_VALUE; //哨兵节点
        int i = 0, j = 0;
        for (int k = start; k <= end; k++) { //对比L[]和R[]中的元素，从小到大依次放入nums[]中
            if (L[i] <= R[j]) {
                nums[k] = L[i++];
            } else {
                nums[k] = R[j++];
            }
        }
    }
}

自底向上的归并排序

private static Comparable[] aux; //归并排序的辅助数组
public void mergesort(Comparable[] nums) {
    // 需要进行logN次两两归并
    int len = nums.length;
    aux = new Comparable[len];
    for (int size = 1; size < len; size <<= 1) { //size表示子数组长度
        for (int start = 0; start < len - size; start += (size<<1)) {
            merge(nums, start, start + size - 1, 
                  Math.min(start + size + size - 1, len - 1));
        }
    }
}
public void merge(Comparable[] nums, int start, int mid, int end) {
    //将nums[start~mid]和nums[mid+1~hi]归并
    int i = start, j = mid + 1;
    for (int k = start; k <= end; k++) {
        aux[k] = nums[k]; //将nums[start~end]复制到aux[start~end]
    }
    for (int k = start; k <= end; k++) {
        if (i > mid) nums[k] = aux[j++]; //如果左边到达边界
        else if (j > end) nums[k] = aux[i++]; //如果右边到达边界 
        else if (aux[j].compareTo(aux[i]) < 0) nums[k] = aux[j++];
        else nums[k] = aux[i++];
    }
}

性能分析

归并排序所用的时间和$O(nlog_2n)$成正比，可以用归并排序对大规模的数组进行排序。归并排序的主要缺点是辅助数组所使用的额外空间和n的大小成正比。

时间复杂度：$\Theta(n\log_2n)$

• 由于数组中元素的分布情况不会对归并排序的执行次数产生影响，所以没有最好情况和最坏情况，在所有情况下，归并排序的时间复杂的都是$\Theta(n\log_2n)$。

空间复杂度：$O(n)$。

性能优化

思路1: 归并排序+插入排序

跟快速排序算法一样，当数组规模比较小的时候，归并排序还需要调用自身进行递归排序，对于小数组，插入排序要比归并排序更快，所以当数组规模小于一定值的时候切换到插入排序。

使用插入排序处理小规模的子数组，一般可以将归并排序的时间缩短10%～15%。

public void mergesort(int[] nums, int start, int end) {
    if (end - start <= M) { //数组长度小于M时转换为插入排序
        Insertsort.sort(int[] nums, int start, int end);
        return;
    }
    int mid = (end - start) >> 1;
    mergesort(nums, start, mid);
    mergesort(nums, mid + 1, end);
    merge(nums, start, mid, end);
}

思路2: 合并子数组之前判断原数组是否有序

在对两个有序的子数组合并之前，可以先判断一下nums[mid]是否小于nums[mid + 1], 如果nums[mid] < nums[mid + 1]成立，说明原数组已经是有序的了，直接返回就可以。

public voie merge(int[] nums, int start, int mid, int end) {
    if (nums[mid] <= nums[mid + 1]) return;
    ...
    ...
    ...
}

思路3：不将元素复制到辅助数组

传统的归并排序要先将元素复制到两个辅助数组，然后再归并排序到原数组中，我们可以省略掉将元素复制到两个辅助数组的操作，直接将元素排序到一个大的辅助数组中（该辅助数组的长度是L和R长度的和），然后再和原数组的另一个排好序的子数组归并回原数组中，这种操作要求我们在每个层次交换输入数组和辅助数组的角色。

---

堆排序 HeapSort

二叉堆：是一个数组，它可以被看成一个近似的完全二叉树，树上的每一个结点对应数组中的一个元素。除了最底层外，该树是完全充满的，而且是从左向右填充。

表示堆的数组A有两个属性：

1. A.length表示数组元素个数。A.heap-size表示堆元素个数。A[1…A.length]可能都存有数据，但只有A[1…A.heap-size]中存放的是堆的有效元素，这里 0 <= A.heap-size <= A.length。
2. 树的根结点是A[1]，**注意：A[0]不使用，因为要计算左右结点坐标。**对于给定结点i，父结点坐标为i / 2，左子结点的坐标为2i，右子结点的坐标为2i+1。

二叉堆分为两种形式：最大堆和最小堆

最大堆：除了根结点以外的所有结点i都有：A[Parent(i)] >= A[i]。既某个结点最多和父结点一样大，因此堆中最大元素就是根结点。

最小堆：除了根结点以外的所有结点i都有：A[Parent(i)] <= A[i]。最小堆中的最小元素存放在根结点。

一个包含n个元素的堆可以看作一课完全二叉树，那么堆的高度是O(logn)，在堆结构上的一些基本操作的运行时间至多与树的高度成正比，既时间复杂度为O(logn)。

定理：当用数组表示存储n个元素的堆时，叶结点下标分别是[n/2]+1, [n/2]+2, … , n（[]表示向下取整）。

堆排序的基本步骤：对于一个输入数组A[1 … n]先用buildMaxHeap方法将其建成一个最大堆，此时数组中的最大元素中在根结点A[1]中，通过把A[1]和A[n]互换，我们可以将该元素放到正确的位置。然后我们从堆去去掉最有一个结点，既让heapSize减1，新的根结点有可能会违背最大堆的性质，为了维护最大堆的性质，我们调用maxHeapify(A, 1)， 在A[1 … n-1]上构建起一个新的最大堆，将A[1]和A[n-1]互换，既可将该元素放到正确位置。不断重复上述步骤，直到heapSize从n降到2。

public class Heapsort {
    private int heapSize;
    public void heapSort(int[] a) {
        heapSize = a.length - 1;
        buildMaxHeap(a);
        for (int i = heapSize; i >= 2; i--) {
            swap(a, 1, i);
            heapSize--;
            maxHeapify(a, 1);
        }
    }
    public void buildMaxHeap(int[] a) {
        for (int i = (heapSize>>1); i >= 1; i--)
            maxHeapify(a, i);
    }
    //maxHeapify的作用是：维护第i个元素最大堆性质，左右孩子都比它小
    public void maxHeapify(int[] a, int i) {
        int l = 2 * i;      //左子结点坐标
        int r = 2 * i + 1;  //右子结点坐标
        int largest = i;    //最大元素坐标初始值为i
        if (l <= heapSize && a[l] > a[i])
            largest = l;
        if (r <= heapSize && a[r] > a[largest])
            largest = r;
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest);
        }
    }
    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

堆排序中用到了两个重要函数：maxHeapify(A, i)和buildMaxHeap(A)。

在调用maxHeapify时我们假定第i个结点的左右子树都是最大堆，但A[i]有可能小于其孩子，maxHeapify通过让A[i]的值在最大堆中“逐级下降”，从而使得以下标i为根结点的子树重新遵循最大堆的性质。maxHeapify的时间复杂度为$O(\log_2n)$。

在buildMaxHeap中用自底向上的方法利用maxHeapify把输入数组转还为最大堆。buildMaxHeap的时间复杂度为$O(n)$。

性能分析

时间复杂度：$O(nlog_2n)$。

空间复杂度：$O(1)$。

性能优化

---

插入排序 Insertionsort

对于数组后面未排序的元素，在前面已排序序列中找到相应位置插入。

public class Insertionsort {
    public void insertionsort(int[] nums) {
        for (int i = 1; i <= nums.length-1; i++) {
            int key = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > key) {
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = key;
        }
    }
}

性能分析

时间复杂度：

• 最好情况：数组升序排列，算法只在while循环处做n次比较，while循环内的语句不会执行，所以时间复杂的是$O(n)$。
• 最坏情况：数组降序排列，算法每次都要进入while循环，进行比较操作和数据移动操作的次数是$1+2+3+…+n = n(n+1)/2$ 所以时间复杂度是$O(n^2)$。
• 平均情况：由定理1和定理2可得是$O(n^2)$。

空间复杂度：$O(1)$。

性能优化

思路1: 使用二分查找确定插入位置

在查找元素插入位置时，可以使用二分查找，让查找这部分时间复杂度降到$O(\log_2n)$，算法整体时间复杂度就可以降到$O(n\log_2n)$。

思路2: 使用递减增量的插入排序：希尔排序。

---

希尔排序 Shellsort

希尔排序也叫递减增量排序算法，是插入排序的一种高效改进版本。它对输入序列的周期子序列使用插入排序，形成了一种更快的排序算法。

希尔排序的执行过程如下图所示：

public class Shellsort {
    public void shellsort(int[] nums) {
        int inc = nums.length >> 1;
        while (inc > 0) {
            for (int i = inc; i <= nums.length-1; i++) {
                int tmp = nums[i];
                int j = i;
                while (j >= inc && nums[j-inc] > tmp) {
                    nums[j] = nums[j-inc];
                    j -= inc;
                }
                nums[j] = tmp;
            }
            inc >>= 1;
        }
    }
}

性能分析

时间复杂的：

• 最好情况：数组正序排列，目前最重要的结论是它的运行时间达不到$O(n^2)$。
• 最坏情况：数组逆序排列，$O(n^2)$。
• 平均情况：$<O(n^2)$。

性能优化

使用其他递减增量序列对原数组进行排序。如《算法》第4版中的1，4，13，40，121，364…序列。

---

冒泡排序 Bubblesort

循环遍历数组，交换相邻的未按次序排列的元素，每趟遍历可以至少将一个数组放到正确位置，中共进行n-1趟排序就可将数组排好。

public class Bubblesort {
    public void bubblesort(int[] nums) {
        for (int i = nums.length-1; i >= 1; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j+1]) {
                    swap(nums, j, j+1);
                }
            }
        }
    }
    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

性能分析

时间复杂度：

• 最好情况：数组已排序，交换元素操作没有执行，但是会进行$O(n^2)$次比较操作，所以最好情况时间复杂度还是$O(n^2)$。
• 最坏情况：数组倒序排列，$O(n^2)$
• 平均情况：$O(n^2)$

空间复杂度：$O(1)$

性能优化

记录最后进行元素交换的位置，此位置之后的元素是有序的不用在进行遍历，所以将遍历截止的位置直接设置到最后进行元素交换的位置可以提高程序性能。

public void bubblesort1(int[] nums) {
    int flag = 0;
    for (int i = nums.length-1; i >= 1; i--) {
        flag = 0;
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j+1]) {
                swap(nums, j, j+1);
                flag = j+1;
            }
        }
        i = flag;
    }
}

时间复杂度：

• 最好情况：数组已排序，则内层for循环遍历一遍数组不改变flag变量的初值，i=flag=0，然后跳出外层循环，所以时间复杂度为$O(n)$。

• 最坏情况：数组倒序，$O(n^2)$。

• 平均情况：$O(n^2)$

空间复杂度：$O(1)$

---

选择排序 Selectionsort

循环遍历数组，第一趟遍历数组是找出数组中最大元素和最后一个元素交换，第二次从剩下的元素开始遍历数组找出最小元素和倒数第二个元素交换，重复上述过程，执行n-1次遍历，每次确定一个元素的位置。

public class Selectionsort {
    public void selectionsort(int[] nums) {
        int max = 0;
        for (int i = nums.length-1; i >= 1; i--) {
            max = 0;
            for (int j = 0; j <= i; j++) {
                if (nums[j] > nums[max]) {
                    max = j;
                }
            }
            swap(nums, i, max);
        }
    }
    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

性能分析

时间复杂度：

• 最好情况：数组已排序，但是还是需要进行$O(n^2)$次比较。
• 最坏情况：数组倒序，$O(n^2)$。
• 平均情况：$O(n^2)$。

空间复杂度：$O(1)$

---

排序算法的选择