十大排序算法

初级排序 - O(n^2)

1、插入排序

将待排序数组分为已排序和未排序两个数组，每次从未排序数组中取一个值，插入有序数组中，此过程重复 n 次。

向有序数组中插入一个数：1、寻找插入位置；2、搬移数据。

性能分析：

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定
• 原地排序：是

代码实现：

public static void insertSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {  // n - 1 次插入
        int val = a[i], j = i - 1;
        for (; j >= 0; --j) {  // 寻找插入位置并移动数据
            if (a[j] > val) a[j + 1] = a[j];
            else break;
        }
        a[j + 1] = val; 
    }
}

二分插入

寻找插入位置时，使用二分查找

public static void insertSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        int val = a[i];
        int ind = bsearch(a, i);  // 查找插入位置
        for (int j = i - 1; j >= ind; --j) // 搬移元素
            a[j + 1] = a[j];
        a[ind] = val;
    }
}

private static int bsearch(int[] a, int i) {
    int l = 0, r = i - 1;
    while (l <= r) {
        int m = l + ((r - l) >>> 1);
        if (a[m] <= a[i]) l = m + 1;
        else r = m - 1;
    }
    return l;
}

参考文档

https://juejin.cn/post/6844903640256217102

https://zhuanlan.zhihu.com/p/122293204

https://juejin.cn/post/6844903433372188686

https://www.mdeditor.tw/pl/pL94/zh-tw

成对插入

一次插入两个数

官方源码

/**
 * @param a the array to be sorted
 * @param left the index of the first element, inclusive, to be sorted
 * @param right the index of the last element, inclusive, to be sorted
 */

/*
 * Skip the longest ascending sequence.
 */
do {
    if (left >= right) {
        return;
    }
} while (a[++left] >= a[left - 1]);

/*
 * Every element from adjoining part plays the role
 * of sentinel, therefore this allows us to avoid the
 * left range check on each iteration. Moreover, we use
 * the more optimized algorithm, so called pair insertion
 * sort, which is faster (in the context of Quicksort)
 * than traditional implementation of insertion sort.
 */
for (int k = left; ++left <= right; k = ++left) {
    int a1 = a[k], a2 = a[left];

    if (a1 < a2) {
        a2 = a1; a1 = a[left];
    }
    while (a1 < a[--k]) {
        a[k + 2] = a[k];
    }
    a[++k + 1] = a1;

    while (a2 < a[--k]) {
        a[k + 1] = a[k];
    }
    a[k + 1] = a2;
}

int last = a[right];

while (last < a[--right]) {
    a[right + 1] = a[right];
}
a[right + 1] = last;

代码实现

public static void pairInsertSort(int[] a, int l, int r) {
    if (r - l < 2) return;

    int left = l;   // 左边界

    // 检测开头是否有升序段
    do {
        if (r <= l) return;
    } while (a[++l] >= a[l - 1]);

    for (int i = l; ++l <= r; i = ++l) {
        int v1 = a[i], v2 = a[l];
        if (v1 < v2) {  // 维护 v1 > v2
            v2 = v1;
            v1 = a[l];
        }

        // 先插入较大元素 v1
        while (--i >= left && v1 < a[i])
            a[i + 2] = a[i];
        a[++i + 1] = v1;

        // 再插入较小元素 v2
        while (--i >= left && v2 < a[i])
            a[i + 1] = a[i];
        a[i + 1] = v2;

        // 处理多余元素
        if (l == r) {
            int tail = a[r];
            while (--l >= left && tail < a[l])
                a[l + 1] = a[l];
            a[l + 1] = tail;
        }
    }
}

参考链接

https://github.com/kaaass/KFlight/blob/7aa7b64e8f7dcf40a686af58952840bd690cbc88/src/main/java/net/kaaass/kflight/algorithm/sort/BiInsertSort.java#L14

希尔排序（Shellsort）

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

性能分析：

• 时间复杂度：根据步长序列的不同而不同！
  • 
• 空间复杂度：O(1)
• 稳定性：不稳定
• 原地排序：是

代码实现：

public static void shellSort(int[] arr) {
    int length = arr.length;
    int temp;
    for (int step = length / 2; step >= 1; step /= 2) {
        for (int i = step; i < length; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

2、选择排序

将待排序数组分为已排序和未排序两个数组，每次从未排序数组中选择一个最值，放入已排序数组的末尾，此过程重复 n 次。

性能分析：

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定
  • 举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
• 原地排序：是

代码实现：

public static void selectSort(int[] a) {
    for (int i = 0; i < a.length - 1; ++i) {  // n - 1 次选择
        int min = i;
        for (int j = i + 1; j < a.length; ++j) {  // 查找最值
            if (a[j] < a[min]) min = j;
        }
        // 交换
        int tmp = a[i]; 
        a[i] = a[min];
        a[min] = tmp;
    }
}

3、冒泡排序

对于待排序数组中的元素，从数组首部或尾部开始，元素之间两两进行比较，根据排序规则（从大到小/从小到大），进行交换；

一趟下来，数组中的一个最值元素就被移动到了数组末尾或开头。

性能分析：

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定
• 原地排序：是

代码实现：

从前往后冒泡：

public static void bubbleSort(int[] a) {
    for (int i = 0; i < a.length - 1; ++i) {  // n -1 趟冒泡
        // 一趟冒泡的比较次数
        for (int j = 1; j < a.length - i; ++j) {   // j 的范围：[1, len - i)
            if (a[j] < a[j - 1]) {  // 是否交换
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
            }
        }
    }
}

另一种形式：

public static void bubbleSort(int[] a) {
    for (int i = 0; i < a.length - 1; ++i) {
        for (int j = 0; j < a.length - i - 1; ++j) {  // j 的范围：[0, len - i - 1)
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

从后往前冒泡：

public static void bubbleSort(int[] a) {
    for (int i = 0; i < a.length - 1; ++i) {
        for (int j = a.length - 1; j > i; --j) {  // j 的范围：(i, len - 1]
            if (a[j] < a[j - 1]) {
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
            }
        }
    }
}

优化：

public static void bubbleSort(int[] a) {
    for (int i = 0; i < a.length - 1; ++i) {  // n -1 趟冒泡
        boolean flag = false;  // 记录一趟冒泡是有否有数据进行交换
        for (int j = 1; j < a.length - i; ++j) {  // 一趟冒泡的比较次数
            if (a[j] < a[j - 1]) {  // 是否交换
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
                flag = true;
            }
        }
        if (!flag) break;  // 无数据交换，说明数据已排序完成！
    }
}

继续优化：

public static void bubbleSort(int[] a) {
    int sortBorder = a.length - 1;  // 无序数据的边界，每次只需比较到这里即可退出
    int lastExchange = 0;  // 记录最后一次交换的位置
    for (int i = 0; i < a.length - 1; ++i) {
        boolean flag = false;
        for (int j = 1; j <= sortBorder; ++j) {  // j 的范围：[1, sortBorder]
            if (a[j] < a[j - 1]) {
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
                flag = true;
                lastExchange = j; // 更新最后一次交换的位置
            }
        }
        sortBorder = lastExchange;
        if (!flag) break;
    }
}

另一种形式：

public static void bubbleSort(int[] a) {
    int sortBorder = a.length - 1;  // 无序数据的边界，每次只需比较到这里即可退出
    int lastExchange = 0;  // 记录最后一次交换的位置
    for (int i = 0; i < a.length - 1; ++i) {
        boolean flag = false;
        for (int j = 0; j < sortBorder; ++j) {  // j 的范围：[0, sortBorder)
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                flag = true;
                lastExchange = j; // 更新最后一次交换的位置
            }
        }
        sortBorder = lastExchange;
        if (!flag) break;
    }
}

向下冒泡

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; ++i) {
        for (int j = i + 1; j < arr.length; ++j) {
            if (arr[i] > arr[j]) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

高级排序 - O(nlogn)

1、快速排序

public static void quickSort(int[] a, int l, int r) {
    if (r <= l) return;
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);
    quickSort(a, p + 1, r);
}

private static int partition(int[] a, int l, int r) {
    swap(a, new Random().nextInt(r - l + 1) + l, r);
    int p = r, n = l;
    for (int i = l; i < r; ++i) {
        if (a[i] < a[p]) swap(a, i, n++);
    }
    swap(a, p, n);
    return n;
}

private static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

优化一：单边递归

public static void quickSort(int[] a, int l, int r) {
    while (l < r) {
        int p = partition(a, l, r);
    	quickSort(a, p + 1, r);
        r = p - 1;
    }
}

private static int partition(int[] a, int l, int r) {
    swap(a, new Random().nextInt(r - l + 1) + l, r);
    int p = r, n = l;
    for (int i = l; i < r; ++i) {
        if (a[i] < a[p]) swap(a, i, n++);
    }
    swap(a, p, n);
    return n;
}

private static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

优化二：三点取中

public static void quickSort(int[] a, int l, int r) {
    while (l < r) {
        int p = partition(a, l, r);
    	quickSort(a, p + 1, r);
        r = p - 1;
    }
}

private static int partition(int[] a, int l, int r) {
    median(a, l, r);
    int p = r, n = l;
    for (int i = l; i < r; ++i) {
        if (a[i] < a[p]) swap(a, i, n++);
    }
    swap(a, p, n);
    return n;
}

private static void median(int[] a, int l, int r) {
    int m = l + ((r - l) >> 1);
    if (a[l] > a[r]) swap(a, l, r);
    if (a[l] > a[m]) swap(a, l, m);
    if (a[r] > a[m]) swap(a, r, m);
}

private static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

2、归并排序

二路归并：

public static void mergeSort(int[] a, int l, int r) {
    if (r <= l) return;
    int m = l + ((r - l) >> 1);
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    merge(a, l, m, r);
}

private static void merge(int[] a, int l, int m, int r) {
    int[] tmp = new int[r - l + 1];
    int i = l, j = m + 1, k = 0;
    while (i <= m || j <= r)
        tmp[k++] = j > r || (i <= m && a[i] < a[j]) ? a[i++] : a[j++];
    for (int p = 0; p < tmp.length; ++p)
        a[l + p] = tmp[p]; 
}

特殊排序 - O(n)

1、计数排序

2、基数排序

3、桶排序

脑洞排序

1、睡眠排序

2、猴子排序

3、珠排序

4、面条排序

Arrays.sort 源码分析

Dual-Pivot Quicksort 双轴快速排序

从 JDK 1.7 开始采用这种 Dual-Pivot Quicksort，首先会根据数组的长度选择对应的排序算法：

1. 需要排序的数组为a，判断数组的长度是否大于==286==，大于使用Timesort 归并排序，否则执行2；
2. 判断数组长度是否小于==47==，小于则采用插入排序，否则执行3；
3. 双轴快排。

package java.util;

/**
 * This class implements the Dual-Pivot Quicksort algorithm by
 * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
 * offers O(n log(n)) performance on many data sets that cause other
 * quicksorts to degrade to quadratic performance, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * All exposed methods are package-private, designed to be invoked
 * from public methods (in class Arrays) after performing any
 * necessary array bounds checks and expanding parameters into the
 * required forms.
 *
 * @author Vladimir Yaroslavskiy
 * @author Jon Bentley
 * @author Josh Bloch
 *
 * @version 2011.02.11 m765.827.12i:5\7pm
 * @since 1.7
 */
final class DualPivotQuicksort {

    /**
     * Prevents instantiation.
     */
    private DualPivotQuicksort() {}

    /*
     * Tuning parameters.
     */

    /**
     * The maximum number of runs in merge sort.
     */
    private static final int MAX_RUN_COUNT = 67;

    /**
     * The maximum length of run in merge sort.
     */
    private static final int MAX_RUN_LENGTH = 33;

    /**
     * If the length of an array to be sorted is less than this
     * constant, Quicksort is used in preference to merge sort.
     */
    private static final int QUICKSORT_THRESHOLD = 286;

    /**
     * If the length of an array to be sorted is less than this
     * constant, insertion sort is used in preference to Quicksort.
     */
    private static final int INSERTION_SORT_THRESHOLD = 47;

    /**
     * If the length of a byte array to be sorted is greater than this
     * constant, counting sort is used in preference to insertion sort.
     */
    private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;

    /**
     * If the length of a short or char array to be sorted is greater
     * than this constant, counting sort is used in preference to Quicksort.
     */
    private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
    
    // ...
    
}

参考链接

• https://zh.wikipedia.org/wiki/Timsort
• https://www.infoq.cn/article/vmz6h4iwmr5twwbp4oyz
• https://blog.csdn.net/octopusflying/article/details/52388012
• http://www.blossomingmay.com/blog/2019-05/jdk1.8-arrays.sort-%E6%BA%90%E7%A0%81%E6%B5%85%E6%9E%90/
• https://liam.page/2018/09/18/std-sort-in-STL/