旧金山大学 (University of San Francisco) 可视化学习网站 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html (opens new window)

评价指标

时间复杂度

含义：随着数据规模$n$ 的增加，算法运行时间的变化趋势。

排序算法的时间复杂度主要有以下几种：

${\rm O}(n^2)$：最原始的排序算法，如冒泡排序、选择排序、插入排序

${\rm O}(nlogn)$：这是较高效的排序算法，如快速排序、归并排序

${\rm O}(n)$：线性时间排序，基于桶排序和计数排序的算法。

${\rm O}(1)$：对已经排序好的数组而言，时间复杂度为常数。

空间复杂度

含义：反映排序算法占用内存空间的情况。

常见的排序算法空间复杂度有：

${\rm O}(1)$：仅使用固定的额外空间，通常是原地排序，如冒泡排序、插入排序。

${\rm O}(n)$：使用的额外空间与$n$ 成线性比例，通常使用辅助数组，如选择排序、基数排序。

${\rm O}(nlogn)$ ：使用的额外空间与$nlogn$ 成比例，通常使用分治编程思想，如快速排序、归并排序。

更高：某些排序算法会占用更多的内存空间。

相同时间复杂度的算法，空间复杂度低的算法更可取。

比如快速排序和归并排序都为${\rm O}(nlogn)$，但快速排序是${\rm O}(logn)$ 的空间复杂度，而归并排序为${\rm O}(n)$，所以快速排序在内存占用上更有优势。

稳定性

若待排序表中有两个元素$Ri$ 和$Rj$，其对应的关键字相同即$keyi=keyj$，且在排序前$Ri$ 在$Rj$ 的前面，若使用某⼀排序算法排序后，$Ri$ 仍然在$Rj$ 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

分类

内部排序

插入排序（Insert Sort）

算法思想：每次将⼀个待排序的记录按其关键字大小插入到前面已排好序的子序列中， 直到全部记录插⼊完成。

演示：https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html (opens new window)

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

时间复杂度：

• 最好（全部有序）：$O(n)$
• 最坏（全部逆序）：$O(n^2)$
• 平均：$O(n^2)$

稳定性：稳定

    public void insertSort(int[] arr) {
        // 构建有序序列，默认第一个元素为有序序列，从第二个元素开始
        for (int i = 1; i < arr.length; i++) {
            // 如果当前元素小于前一个元素，则需要插入有序序列；反之说明有序
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i];
                int j;
                // 从后往前遍历有序序列，找到插入位置
                for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = temp;
            }
            // 本次循环结束，表示0到i的元素已经有序
        }
    }

存在的问题

上述代码中，在将当前遍历的元素插入到有序序列时，是逐个比较的，可使用二分查找提高效率。

优化：折半插入排序（Binary Insertion Sort）

    public void insertSort(int[] arr) {
        // 构建有序序列，默认第一个元素为有序序列，从第二个元素开始
        for (int i = 1; i < arr.length; i++) {
            // 如果当前元素小于前一个元素，则需要插入有序序列；反之说明有序
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i];
                // 通过二分查找找到插入索引low
                int low = 0;
                int high = i - 1;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (arr[mid] > temp) {
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                // 将low到i-1的元素后移一位
                for (int j = i - 1; j >= low; j--) {
                    arr[j + 1] = arr[j];
                }
                // 插入元素
                arr[low] = temp;
            }
            // 本次循环结束，表示0到i的元素已经有序
        }
    }

笔记

虽然优化之后，减少了查找插入索引的次数，但移动元素的次数不变，因此其平均时间复杂度依然是$O(n^2)$。

希尔排序（Shell Sort）

先追求表中元素部分有序，再逐渐逼近全局有序

思想：先将待排序表分割成若干形如 L[i, i + d, i + 2d,…, i + kd] 的 “特殊” 子表，对各个子表分别进行直接插入排序。缩小增量 d，重复上述过程，直到 d=1 为止。

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

时间复杂度：

• 最好：$O(n^{1.3})$
• 最坏：$O(n^2)$
• 平均：$O(nlogn)$ （也有说是未知，目前无法用数学手段证明确切的时间复杂度）

稳定性：不稳定 （相同元素排序后先后顺序）

适用性：需要具备随机访问的能力，因此仅适用于顺序表，不适用于链表

点击查看

第一趟排序前：

第一趟排序后：

第二趟排序前：

第二趟排序后：

第三躺排序前：

第三趟排序后：

    public void shellSort(int[] arr) {
        // 希尔排序
        // 1.确定增量
        int gap = arr.length / 2;
        while (gap > 0) {
            // 2.分组进行插入排序
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = temp;
            }
            // 3.缩小增量
            gap /= 2;
        }
    }

冒泡排序（Bubble Sort）

交换排序

基于 “交换” 的排序：根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。属于交换排序的有冒泡排序、快速排序。

思想：从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即$A[i-1]>A[i]$），则交换它们，直到序列比较完。称这样过程为 “一趟” 冒泡排序。

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

时间复杂度：

• 最好：$O(n)$
• 最坏：$O(n^2)$
• 平均：$O(n^2)$

为什么最好时间复杂度不是O(n²)？

时间复杂度是根据 比较次数 + 交换次数 来计算的，在最好（有序）的情况下，只需要比较 n-1 次，交换 0 次即可，因此最好的时间复杂度是$O(n)$

稳定性：稳定

点击查看

以此类推，直到 n-1 趟完成

代码实现

    public void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 标记是否发生交换，如果没有发生交换，则说明已经有序
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }

            }
            if (!flag) {
                return;
            }
        }
    }

⭐️快速排序（Quick Sort）

提示

平均性能最优秀的排序算法

思想：在待排序表 L[1…n] 中任取⼀个元素 pivot 作为枢轴（或基准，通常取首元素），通过⼀趟排序将待排序表划分为独立的两部分 L[1…k-1] 和 L[k+1…n] ，使得 L[1…k-1] 中的所有元素小于 pivot， L[k+1…n] 中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L (k) 上，这个过程称为⼀次 “划分”。然后分别递归地对两个⼦表重复上述过程，直至每部分内只有⼀个元素或空为止，即所有元素放在了其最终位置上。

1. 取一个元素（通常是索引 0）作为基准（变量记录）
2. 设两指针，一个左指针、一个右指针
3. 右指针从右往左，找到小于基准元素的元素，将其插入左指针索引位
4. 左指针从左往右，找到大于等于基准元素的元素，将其插入右指针索引位
5. 反复步骤 3、4，直到左右指针相遇时，将步骤 1 的基准元素插入头 (尾) 指针索引位

上述操作一次后，基准元素完成排序，基准元素左边都是小于基准元素的，右边都是大于基准元素的。将基准元素分割的左右表重复上述步骤，直至无法分割。

时间复杂度：$O(n\times \mathrm{递}\mathrm{归}\mathrm{层}\mathrm{数})$

• 最好：$O(nlogn)$
• 最坏：$O(n^2)$（数组原本就有序）
• 平均：$O(nlogn)$

空间复杂度：

• 最好：$O(logn)$
• 最坏：$O(n)$

稳定性：不稳定

代码实现

    // 用第一个元素将待排序序列划分成左右两个部分
    public int Partition(int[] arr, int low, int high) {
        int pivot = arr[low]; // 第一个元素作为基准
        while (low < high) { // 当不满足时，说明low、high指针都指向基准元素排序后的位置
            while (low < high && arr[high] >= pivot) { // high找到小于基准元素的索引位置
                high--;
            }
            arr[low] = arr[high]; // 把找到小于基准元素的元素放到low指向的坑

            while (low < high && arr[low] <= pivot) { // low指针找到大于基准元素的索引位置
                low++;
            }
            arr[high] = arr[low]; // 把找到大于基准元素的元素放到high指向的坑
        }
        arr[low] = pivot;
        return low;
    }

    public void QuickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotpos = Partition(arr, low, high); // 划分并返回基准元素的索引位置
            QuickSort(arr, low, pivotpos - 1);
            QuickSort(arr, pivotpos + 1, high);
        }
    }

若每一次选中的基准元素将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高。

优化思路：

• 选头、中、尾三个位置的元素，取中间值作为基准元素

• 随机选一个元素作为基准元素

简单选择排序（Select Sort）

选择排序

每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列，属于交换排序的有：简单选择排序、堆排序。

思想：每一趟在待排序元素中选取关键字最小的元素加入有序子序列

笔记

遍历 n-1 遍，在待排序集合中找出最小的，与当前 arr [i] 交换（导致不稳定），直至遍历完成。

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

时间复杂度：$O(n^2)$

稳定性：不稳定（可以稳定）

适用性：顺序表、链表都可

代码实现

    public void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }

堆排序（Heap Sort）

前置知识

若 n 个关键字序列 L [1…n] 满足下面某⼀条性质，则称为堆（Heap）：

• 若满足：L (i)≥L (2i) 且 L (i)≥L (2i+1) （1 ≤ i ≤n/2 ）—— 大根堆（大顶堆），排序后递增

• 若满足：L (i)≤L (2i) 且 L (i)≤L (2i+1) （1 ≤ i ≤n/2 ）—— 小根堆（小顶堆），排序后递减

思路（以大根堆为例）：

1. 将排序数组理解成顺序存储的完全二叉树
2. 建堆：从后往前检查所有非终端结点（$\lfloor n/2\rfloor$ 至 1）检查一遍，是否满足大根堆的要求（ 根≥左、右 ）。
   1. 如不满足，将当前结点与更大的一个孩子互换。
3. 排序：基于选择排序思想，每一趟将堆顶元素加入有序子序列（与待排序序列的最后一个元素交换），每次交换后，重构大根堆。待排序列继续此操作，直至完成（length <= 1）。

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

时间复杂度：

• 建堆：$O(n)$
• 排序：$O(nlogn)$
• 平均：$O(n)+O(nlog2n)=O(nlogn)$

稳定性：不稳定

代码实现

package cn.nipx.atguigu.datastructure;

import java.util.Arrays;

/**
 * 大顶堆排序
 *
 * @author NipGeihou
 * @create 2021-09-27 17:16
 */
public class MaxHeapSortDemo {

    public static void main(String[] args) {
        int[] ints = {0, 23, 54, 23, 52, 5, 73};
        HeapSort(ints, 6);
        System.out.println(Arrays.toString(ints));
    }


    // 将以k为根的子树调整为大根堆
    public static void HeadAdjust(int[] arr, int k, int len) {
        arr[0] = arr[k];
        for (int i = 2 * k; i <= len; i *= 2) {

            if (i < len && arr[i] < arr[i + 1]) {   // 左结点 小于 右结点
                i++; // 指向较大的子结点
            }

            if (arr[0] >= arr[i]) {
                break; // 根结点 大于等于 子结点；调整完毕 跳出循环
            } else {
                arr[k] = arr[i];   // 将arr[i] 调整到 双亲结点上
                k = i;
            }

        }

        arr[k] = arr[0]; // 被筛选结点的值放入最终位置
    }

    // 建立大顶堆
    public static void BuildMaxHeap(int[] arr, int len) {
        for (int i = len / 2; i > 0; i--) {  // 从后往前调整所有非终端结点
            HeadAdjust(arr, i, len);
        }
    }


    public static void HeapSort(int[] arr, int len) {
        BuildMaxHeap(arr, len);  // 初始建堆
        for (int i = len; i > 1; i--) {
            int temp = arr[i];
            arr[i] = arr[1];
            arr[1] = temp;

            HeadAdjust(arr, 1, i - 1);
        }
    }

}

插入

1. 对于小根堆，新元素放到队尾。
2. 与父节点对比，若新元素比父节点更小，则将二者互换。新元素就这样一路 “上升”，直到无法继续上升为止。

删除

1. 被删除的元素用堆底元素替代
2. 然后让该元素不断 “下坠”，直到无法下坠为止

⭐️归并排序（Merge Sort）

笔记

• 局部有序到整体有序
• 效率上不如快排，但他是稳定的

归并：把两个或多个已经有序序列的合并

空间复杂度：$O(n)$（来自于辅助数组）

时间复杂度：$O(nlogn)$ （归并树）

稳定性：稳定

二路归并，即有两个有序序列：

代码实现

package cn.nipx.atguigu.datastructure;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author NipGeihou
 * @create 2021-09-27 19:11
 */
public class MergeSortDemo {

    public static void main(String[] args) {
        int[] ints = {12, 432, 56, 3, 64, 73, 5};
        MergeSort(ints,0,6);
        System.out.println(Arrays.toString(ints));

    }

    // 两个数组归并，min为第一个数组最后一个元素
    public static void Merge(int[] arr, int low, int mid, int high) {
        // 辅助数组
        int[] arr2 = new int[arr.length];

        int i, j, k;

        // 复制数组arr合并部分的元素到arr2
        for (k = low; k <= high; k++) {
            arr2[k] = arr[k];
        }

        // 将辅助数组中的两个有序子数组，合并到原数组，使得原数组low到high区间有序
        // i指向arr2第一子数组第一个元素开始，j指向arr2第二子数组第一个元素开始，k指向arr元素第一个元素开始
        for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {  // 一旦某个子数组遍历完了，跳出循环

            if (arr2[i] <= arr2[j]) {
                arr[k] = arr2[i++];
            } else {
                arr[k] = arr2[j++];
            }
        }

        // 处理跳出循环后，另一个子数组的直接合并到原素组
        while (i <= mid) {
            arr[k++] = arr2[i++];
        }

        while (j <= high) {
            arr[k++] = arr2[j++];
        }

    }

    public static void MergeSort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2; // 中间划分
            MergeSort(arr, low, mid); // 对左半部分归并排序
            MergeSort(arr, mid + 1, high); // 对右半部分归并排序
            Merge(arr, low, mid, high); // 归并
        }
    }

}

基数排序（Radix sort）

空间复杂度：$O(r)$，$r$ 个辅助队列

时间复杂度：$O(d(n+r))$ $d$ 趟分配、收集

稳定性：稳定

擅长解决的问题：

1. 数据元素的关键字可以方便地拆分为 d 组，且 d 较小。（反例：给 (r=5) 个人的身份证号码 (d=18) 位 排序）
2. 每组关键字的取值范围不大，即 r 较小。（反例：给中文 (r=100+) 人名排序）
3. 数据元素个数 n 较大。（正例：给 (r=10 亿) 人的身份证号码 (d=18) 排序）

点击查看

原数组 按个位分配： 从大到小收集： 按十位分配： 从大到小收集： 按百位分配： 从大到小收集，完成排序：

外部排序（大数据）

归并排序（Merge Sort）

笔记

外存版的归并排序，先局部有序，再到整体有序。

场景：数据元素太多，无法一次全部读入内存进行排序。

特点：最少只需在内存中分配 3 块磁盘块大小的缓冲区即可对任意一个大文件进行排序。

时间开销：读写外存的时间 + 内部排序所需时间 + 内部归并所需时间

优化

1. 增加归并路数 k，进行多路平衡归并
   1. 代价 1：需要增加相应的输入缓冲区关键字对比次数
   2. 代价 2：每次从 k 个归并段中选一个最小元素需要 (k-1) 次关键字对比 。（可用 “败者树” 减少关键字比较次数）
2. 减少初始归并段数量 r

延伸

JDK 用的那些排序算法？

Previously, Java’s Arrays.sort method used Quicksort for arrays of primitives and Merge sort for arrays of objects. In the latest versions of Java, Arrays.sort method and Collection.sort() uses Timsort.

以前，Java 的 Arrays.sort 方法对基本类型数组使用快速排序，对对象数组使用归并排序。在 JDK7 后， Arrays.sort 方法和 Collection.sort() 使用 Timsort。

TimSort

TimSort 是插入排序和归并排序的结合。它使用插入排序来排序连续近序的子序列，再用合并这些排序好的子序列来完成整个数组的排序。

特点

1. 时间复杂度为$O(nlogn)$ ，与归并排序相同
2. 空间复杂度为$O(n)$，原地排序，不需要额外的空间
3. 能充分利用已排序的序列，效率更高
4. 稳定性更高，相同元素的相对次序保持不变

工作过程

1. 使用插入排序对数组的前 32 个元素进行排序。这一步能较快地构建一些有序的子序列。
2. 根据数组的中位数找到一个基准值 pivot 。
3. 从 pivot 分割整个数组，将小于 pivot 的子序列和大于 pivot 的子序列分别排序。
4. 重复上一步，直到整个数组都是有序的或只剩下几个元素为止。
5. 将这些有序的子序列合并成最终的有序数组。

TimSort 相比插入排序更高效，因为它能充分利用数组中已经有序的子序列。 对于那些有大量有序序列的数组，TimSort 可以达到近乎线性时间复杂度 Ο(n)。

总的来说，TimSort 是一种结合了插入排序和归并排序优点的有效排序算法。 它由于稳定性高和性能理想，所以成为了 Python 排序算法的首选。

参考：世界上最快的排序算法 ——Timsort - 佛西先森 - 博客园 (opens new window)

猴子排序（Bogo Sort）

Bogo 排序（bogo-sort）是个非常低效率的排序算法，通常用在教学或测试。

思想：随机打乱顺序，检测是否有序，无序再次打乱，直至有序。

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

时间复杂度：

• 最坏：$\infty$
• 最好：$O(n)$
• 平均：$O(n\times n!)$

稳定性：不稳定