十大排序算法

时间复杂度

排序算法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
归并排序	$O(nlog^n)$	$O(nlog^n)$	$O(nlog^n)$	$O(n)$	稳定
快速排序	$O(nlog^n)$	$O(n^2)$	$O(nlog^n)$	$O(nlog^n)$	不稳定
堆排序	$O(nlog^n)$	$O(nlog^n)$	$O(nlog^n)$	$O(1)$	不稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定
桶排序	$O(n+k)$	$O(n^2)$	$O(n)$	$O(n+k)$	稳定
基数排序	$O(n*k)$	$O(n*k)$	$O(n*k)$	$O(n+k)$	稳定

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破$O(nlog^n)$，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；
不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；

一、冒泡排序

1. 图解

冒泡排序（Bubble Sort），他重复地走访要排序的数列，一次比较两个元素，如果顺序错误，就将它们交换位置。无论是最坏时间复杂度还是平均时间复杂度都为$O(n^2)$，但算法稳定。

冒泡排序

2. 算法步骤

比较相邻的两个元素，如果第一个比第二个大，就交换
对每一对相邻元素做同样的工作，从开始到结束，这一趟结束之后，最后那个元素就是最大的数
对所有的元素重复以上步骤，除了最后一个元素
持续每次对越来越少的元素重复上面的操作，直到没有任何一个数字需要比较。

3. 程序

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

二、选择排序

1. 图解

选择排序（Selection Sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

选择排序

2. 步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
重复第2步，直到所有元素均排序完毕。

3. 算法

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                j = minIndex;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

三、插入排序

1. 图解

插入排序（Insertion Sort）的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序

2. 步骤

首先从第一个元素开始，该元素被认为是有序的；
取出下一个元素，在已经排序的元素序列中从后往前进行扫描；
如果该已排好序的元素大于新元素，则将该元素移到下一位置；
重复步骤3一直往前进行扫描比较，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

3. 算法

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int val = arr[i];
        int j = i - 1;
        while(j >= 0 && val < arr[j]) { //找到第一个比val小的元素
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = val; //插入到该元素之后
    }
}

四、希尔排序

1. 图解

希尔排序（Shell Sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

希尔排序

2. 步骤

选择一个增量序列 {t1, t2, …, tk} ；
按增量序列个数k，对序列进行k趟排序；
每趟排序，根据对应的增量t，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。（增量为1时，就是直接插入排序）
其中，增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，**{n/2, (n/2)/2, …, 1}**，称为增量序列。一般的增量序列都选择以上说明的这个，但不一定是最优的。

3. 算法

public static void shellSort(int[] arr) {
    int n = arr.length;
    int gap = n / 2;
    while (gap > 0) {
        // 每一组子序列进行插入排序
        for (int i = gap; i < n; i++) { //子序列中找到第一个比val小的元素
            int val = arr[i];
            int j = i - gap;
            while(j >= 0 && val < arr[j]) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = val;
        }
        gap /= 2;
    }
}

五、归并排序

1. 图解

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 $O(nlog^n)$ 的时间复杂度。代价是需要额外的内存空间。

归并排序

2. 步骤

将长度为n的子序列递归进行分割，分割长度为n/2的两个子序列，如果子序列中只有1个元素，则认为是有序的，直接返回该子序列
对于递归返回的每个子序列被认为是有序的，然后将递归返回子序列进行两两合并；
合并过程中完成排序操作，具体操作为设定两个指针，分别指向两个已经排序子序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并数组，并移动指针到下一位置；
重复步骤3~4直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾部，最终得到的新序列就是有序序列。

3. 算法

public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, mid + 1, right, temp);

    }

}

public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
    int i = left, j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) { //双指针
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    // 将序列剩下的元素直接复制到合并序列尾部
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right){
        temp[k++] = arr[j++];
    }
    for (int l = 0; l < k; l++) {
        arr[left + l] = temp[l];
    }
}

六、快速排序

1. 图解

快速排序采用分治法策略，把一个串行（list）分成两个子串行（sub-list）。最坏的情况下，时间复杂度为$O(n^2)$，但平均时间复杂度为$O(nlogn)$，不稳定。
归并排序是局部有序到整体有序的过程；快速排序是整体有序到局部有序的过程。

快速排序

2. 算法步骤

从数列中挑出一个元素，称为基准（pivot），一般选取第一个元素作为基准
重新排列数列，将所有小于基准的元素放在基准的左边，大于基准的元素放在基准的右边，相同的元素可以放在任意一边，直到low不小于high。在这个分区结束后，该基准就处于数列的中间，这个称为分区（partition）操作。
递归把小于基准值元素的子数列和大于基准值元素的子数列排序。

3. 程序

public static void quickSort(int[] arr, int start, int end) {
    if (start < end) {
        int pivot = partition(arr, start, end);
        quickSort(arr, start, pivot - 1);
        quickSort(arr, pivot + 1, end);
    }
}

public static int partition(int[] arr, int start, int end) {
    int pivot  = arr[start];
    while (start < end) {
        while (start < end && arr[end] > pivot) { //右指针，找到小于基准的那个数

        }
        while (start < end && arr[start] <= pivot) { //左指针，找到大于基准的那个数
            start++;
        }
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
    return start;
}

七、堆排序

1. 图解

堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
- 堆排序（超详细图解 Java版）

堆排序

2. 步骤

将待排序列(R0, R1, ……, Rn)构建成最大堆（最小堆）；
将堆顶元素R[0]与最后一个元素R[n]进行交换，此时得到新的无序区(R0, R1, ……, Rn-1)和新的有序区(Rn)，且满足R[0, 1, ……, n-1]<=R[n]（或>=R[n]）
由于调整后的新堆可能违反堆的性质，因此需要对当前无序区(R0, R1, ……, Rn-1)进行调整；
重复步骤2~3直到有序区的元素个数为n。

3. 算法

public static void heapSort(int[] arr) {
    //1.构建初始堆，arr[0]堆顶为最大元素
    buildMaxHeap(arr);
    //2.交换堆顶和最后一个元素，从上至下继续调整堆、
    for (int i = arr.length - 1; i >= 1; i--) {
        swap(arr,0, i);
        adjustHeap(arr,0, i);
    }
}

/**
     * 构建最大堆，arr[0]为最大值
     *
     * @param arr
     */
public static void buildMaxHeap(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(arr, i, n);
    }
}

/**
     * 调整堆
     *
     * @param arr
     * @param i      父节点编号
     * @param length 对应节点i的调整，可能会影响到已经调整好的子堆,
     *               需要调整的范围是（i, length）
     */
public static void adjustHeap(int[] arr, int i, int length) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    // 让largest指向【根节点，左节点，右节点】中最大的那一个节点
    if (left < length && arr[left] > arr[i]) {
        largest = left;
    }
    if (right < length && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) { //根节点不是最大的，需要交换
        swap(arr, i, largest);
        // 调整之后，被调整的子堆需要重新调整（直到子堆内部无交换）
        adjustHeap(arr, largest, length);
    }
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

八、计数排序

1. 图解

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序

2. 步骤

找出数组中的最大值maxVal和最小值minVal；
创建一个计数数组countArr，其长度是maxVal-minVal+1，元素默认值都为0；
遍历原数组arr中的元素arr[i]，以arr[i]-minVal作为countArr数组的索引，以arr[i]的值在arr中元素出现次数作为countArr[a[i]-min]的值；
遍历countArr数组，只要该数组的某一下标的值不为0，则循环将下标值+minVal输出返回到原数组即可。

3. 算法

public static void countingSort(int[] arr) {
    int n = arr.length;
    int max = arr[0], min = arr[0];
    for (int i = 0; i < n; i++) {
        max = max > arr[i] ? max : arr[i];
        min = min < arr[i] ? min : arr[i];
    }

    int[] count = new int[max - min + 1];
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }

    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while(count[i] > 0) {
            arr[index++] = i + min;
            count[i]--;
        }
    }
}

九、桶排序

1. 图解

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

桶排序

2. 步骤

设置一个bucketSize（该数值的选择对性能至关重要，性能最好时每个桶都均匀放置所有数值，反之最差），表示每个桶最多能放置多少个数值；
遍历输入数据，并且把数据依次放到到对应的桶里去；
对每个非空的桶进行排序，可以使用其它排序方法；
从非空桶里把排好序的数据拼接起来即可。

3. 算法

public static void bucketSort(int[] arr) {
    int n = arr.length;
    int max = arr[0], min = arr[0];
    for (int i = 0; i < n; i++) {
        max = max > arr[i] ? max : arr[i];
        min = min < arr[i] ? min : arr[i];
    }

    int bucketSize = 10;
    int bucketCount = (max - min) / bucketSize + 1;
    List<List<Integer>> buckets = new ArrayList<>(bucketCount); //桶集合
    for (int i = 0; i < bucketCount; i++) {
        buckets.add(new ArrayList<>());
    }

    for (int i = 0; i < n; i++) {
        int bucketIndex = (arr[i] - min) / bucketSize;
        buckets.get(bucketIndex).add(arr[i]);
    }
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        List<Integer> bucket = buckets.get(i);
        Collections.sort(bucket); //桶内部排序
        for (int j = 0; j < bucket.size(); j++) {
            arr[index++] = bucket.get(j);
        }
    }
}

十、基数排序

1. 图解

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序

2. 步骤

取得数组中的最大数，并取得位数，即为迭代次数n（例如：数组中最大数为123，则 n=3）；
arr为原始数组，从最低位（或最高位）开始根据每位的数字组成radix数组（radix数组是个二维数组，其中一维长度为10），例如123在第一轮时存放在下标为3的radix数组中；
将radix数组中的数据从0下标开始依次赋值给原数组；
重复2~3步骤n次即可。

3. 算法

public static void radixSort(int[] arr) {
    int n = arr.length;
    int max = arr[0]; //最大值
    for (int i = 0; i < n; i++) {
        max = max > arr[i] ? max : arr[i];
    }

    int k = 1; //最大值位数
    while (max / 10 != 0) {
        max /= 10;
        k++;
    }

    for (int i = 0; i < k; i++) {
        List<List<Integer>> radix = new ArrayList<>();
        for (int j = 0; j < 10; j++) {
            radix.add(new ArrayList<>());
        }
        int index;
        for (int j = 0; j < n; j++) {
            index = (arr[j] / (int) Math.pow(10, i)) % 10; //取第i位
            radix.get(index).add(arr[j]);
        }
        index = 0;
        for (List<Integer> list : radix) { //赋值给原数组
            for (int a : list) {
                arr[index++] = a;
            }
        }
    }
}

4. 基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

十一、总结

数据量规模较小，考虑插入或选择。当元素分布有序时插入将大大减少比较和移动记录的次数，如果不要求稳定性，可以使用选择，效率略高于插入；$O(n^2)$
数据量规模中等，使用希尔排序；$O(n^{1.3})$
数据量规模较大，考虑堆排序（元素分布接近正序或逆序）、快速排序（元素分布随机）和归并排序（稳定性）；
一般来说不使用冒泡。$O(nlog^n)$