---

	平均时间	是否原地排序	是否基于比较	稳定性
冒泡排序	$O(n^2)$	是	是	稳定
插入排序	$O(n^2)$	是	是	稳定
选择排序	$O(n^2)$	是	是	不稳定
快速排序	$O(nlogn)$	是	是	不稳定
归并排序	$O(nlogn)$	否	是	稳定
桶排序	$O(n)$	否	否	稳定
计数排序	$O(n)$	否	否	稳定
基数排序	$O(n)$	否	否	稳定

原地排序算法：特指空间复杂度是$O(1)$的排序算法

稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变

冒泡排序(Bubble Sort)

• 基本思想：冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复$n$次，就完成了$n$个数据的排序工作

• 优化：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作

public void bubbleSort(int[] array) {
    int n = array.length;
    if (n <= 1) {
        return ;
    }
    for (int i = 0; i < n-1; i++) {   // 遍历次数
        boolean isChange = false;
        for (int j = 0; j < n-1-i; j++) {  // 比较相邻元素
            // 比较相邻两个元素的大小，前一个大于后一个就交换
            if (array[j] > array[j+1]) {
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                isChange = true;
            }
        }
        if (!isChange) {
            // 如果某次未发生数据交换，说明数据已排序
            break;
        }
    }
}

• 冒泡排序是原地排序算法：冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法

• 冒泡排序是稳定的排序算法：在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法

• 冒泡排序的时间复杂度：

  • 最好情况：要排序的数据已经是有序的了，只需要进行一次冒泡操作，所以最好情况时间复杂度是$O(1)$
  • 最坏情况：要排序的数据刚好是倒序排列的，需要进行$n$次冒泡操作，所以最坏情况时间复杂度为$O(n^2)$
  • 平均时间复杂度：$O(n^2)$

插入排序(Insertion Sort)

• 基本思想：将数组中的数据分为两个区间， 已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素，取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束
  • 插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当需要将一个数据$a$插入到已排序区间时，需要拿$a$与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素插入

public void insertSort(int[] arr) {
    int n = arr.length;
    if (n <= 1) {
        return ;
    }
    for (int i = 1; i < n; i++) {
        int insertVal = arr[i];       // 待插入的数
        int insertIndex = i - 1;
        // 给insertVal找到插入的位置
        // 1. insertIndex >= 0 保证在给insertVal找插入位置，不越界
        // 2. insertVal < arr[insertIndex]待插入的数还没有找到插入的位置，需要将arr[insertIndex]后移
        while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex]; // 大数后移
            insertIndex--;
        }

        // 退出while循环时，说明找到插入位置：insertIndex+1
        if (insertIndex + 1 != i) {
            arr[insertIndex + 1] = insertVal;
        }
    }
}

• 插入排序是原地排序算法：插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是$O(1)$
• 插入排序是稳定的排序算法：在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法
• 插入排序的时间复杂度
  • 最好情况：如果要排序的数据已经是有序的，并不需要搬移任何数据。如果从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为$O(n)$
  • 最坏情况：如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，需要移动大量的数据，所以最坏情况时间复杂度为$O(n^2)$
  • 平均时间复杂度：在数组中插入一个数据的平均时间复杂度是$O(n)$。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行$n$次插入操作，所以平均时间复杂度为$O(n^2)$

选择排序(Selection Sort)

• 基本思想：选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾

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

• 选择排序不是稳定的排序算法：选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性
  • 比如$5,8,5,2,9$这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素$2$，与第一个$5$交换位置，那第一个$5$和中间的$5$顺序就变了，所以就不稳定了

归并排序(Merge Sort)

• 采用分治思想，先把待排序序列拆分成一个个子序列，直到子序列只有一个元素，停止拆分，然后对每个子序列进行边排序边合并
• 分治算法一般都是用递归来实现，分治是一种解决问题的处理思想，递归是一种编程技巧
• 归并排序的递推公式：$mergeSort(p...r)=merge(mergeSort(p...q),merg{e}_{s}ort(q+1...r))$
• 归并排序的终止条件：$p>=r$不用再继续分解

public void mergeSort(int[] arr, int left, int right, int[] tmp) {
        // 递归终止条件
        if (left >= right) {
            return ;
        }
        // 在 left 和 right 都是大整数时，即使溢出，结论依然正确
        int mid = (left + right) >>> 1;
        // 分治递归
        mergeSort(arr, left, mid, tmp);
        mergeSort(arr, mid+1, right,tmp);
        // 如果数组的这个子区间本身有序，无需合并
        if (arr[mid] <= arr[mid+1]) {
            return ;
        }
        // 合并
        merge(arr, left, mid, right, tmp);
    }
    public void merge(int[] arr, int left, int mid, int right, int[] tmp) {
        int i = left, j = mid+1, k = left;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
        // 拷贝某个子区间的剩余数据到临时数组
        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= right) {
            tmp[k++] = arr[j++];
        }
        // 将tmp中的数组拷贝回arr
        System.arraycopy(tmp, left, arr, left, right-left+1);
    }

• 归并排序是稳定的排序算法
• 归并排序不是原地排序算法，空间复杂度是$O(n)$
• 归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情
  况，还是平均情况，时间复杂度都是$O(nlogn)$

快速排序(Quick Sort)

• 快排利用的也是分治思想
• 快速排序的核心思想是对待排序序列通过一个「支点」（支点就是序列中的一个元素，别把它想的太高大上）进行拆分，使得左边的数据小于支点，右边的数据大于支点。然后把左边和右边再做一次递归，直到递归结束
• 快排的思想是这样的：如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。
  遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的
• 最理想的分区点是： 被分区点分开的两个分区中，数据的数量差不多
• 递归公式：$quickSort(p...r)=quickSort(p...q-1)+quickSort(q+1...r)$
• 终止条件：$p>=r$

public void quickSort(int[] arr, int left, int right) {
        // 递归终止条件
        if (left >= right) {
            return ;
        }
        // 获取分区点
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot-1);
        quickSort(arr, pivot+1, right);
    }
public int partition(int[] arr, int left, int right) {
		if (right > left) {
			// 在区间随机选择一个元素作为标定点
			Random random = new Random(System.currentTimeMillis());
			int randomIndex = left + 1 + random.nextInt(right - left);
			int tmp = arr[right];
			arr[right] = arr[randomIndex];
			arr[randomIndex] = tmp;
		}
        int pivot = arr[right];

        // 原地分区
        int i = left;
        for (int j = left; j <= right-1; j++) {
            if (arr[j] < pivot) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[right];
        arr[right] = tmp;
        return i;
    }

• 快速排序并不是一个稳定的排序算法：因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列$6,8,7,6,3,5,9,4$，在经过第一次分区操作之后，两个6的相对先后顺序就会改变

• 快速排序是原地排序算法

• 时间复杂度

  • 最坏情况：(分区极其不均衡)如果数组中的数据原来已经是有序的了，比如$1,3,5,6,8$。如果我们每次选择最后一个元素作为pivot，那每次分区得到的两个区间都是不均等的，需要进行大约$n$次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约$n/2$个元素，这种情况下，快排的时间复杂度就从$O(nlogn)$退化成了$O(n^2)$

    • [1, 3, 5, 6, 8]
      pivot = 4
      [1, 3, 5, 6][8]
      pivot = 3
      [1, 3, 5][6][8]
      pivot = 2
      [1, 3][5][6][8]
      pivot = 1
      [1][3][5][6][8]
      

  • 最好情况：(分区极其均衡)如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，快排的时间复杂度也是$O(nlogn)$

• 剑指 Offer 40. 最小的k个数

• 215. 数组中的第K个最大元素

桶排序(Bucket Sort)

• 核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了
• 桶排序对要排序数据的要求非常苛刻
  • 首先，要排序的数据需要很容易就能划分成$m$个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序
  • 其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为$O(nlogn)$的排序算法了
• 桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中
  • 比如说有10GB的订单数据，希望按订单金额（假设金额都是正整数）进行排序，但是内存有限，只有几百MB，没办法一次性把10GB的数据都加载到内存中。这个时候该怎么办呢？
    • 可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后得到：订单金额最小是1元，最大是10万元。将所有订单根据金额划分到100个桶里，第一个桶存储金额在1元到1000元之内的订单，第二桶存储金额在1001元到2000元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名$（00，01，02\dots 99）$
    • 理想的情况下，如果订单金额在1到10万之间均匀分布，那订单会被均匀划分到100个文件中，每个小文件中存储大约100MB的订单数据，就可以将这100个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了
    • 不过，订单按照金额在1元到10万元之间并不一定是均匀分布的 ，所以10GB订单数据是无法均匀地被划分到100个文件中的。有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。这又该怎么办呢?
      • 针对这些划分之后还是比较大的文件，可以继续划分，比如，订单金额在1元到1000元之间的比较多，我们就将这个区间继续划分为10个小区间， 1元到100元， 101元到200元， 201元到300元…901元到1000元。如果划分之后， 101元到200元之间的订单还是太多，无法一次性读入内存，那就继续再划分，直到所有的文件都能读入内存为止。

桶排序的时间复杂度为什么是$O(n)$？

• 如果要排序的数据有$n$个，把它们均匀地划分到$m$个桶内，每个桶里就有$k=n/m$个元素。每个桶内部使用快速排序，时间复杂度为$O(k\ast logk)$。 $m$个桶排序的时间复杂度就是$O(m\ast k\ast logk)$，因为$k=n/m$，所以整个桶排序的时间复杂度就是$O(n\ast log(n/m))$。当桶的个数$m$接近数据个数$n$时， $log(n/m)$就是一个非常小的常量，这个时候桶排序的时间复杂度接近$O(n)$

/**
     * 桶排序
     *
     * @param arr 数组
     * @param bucketSize 桶容量
     */
public static void bucketSort(int[] arr, int bucketSize) {
    if (arr.length < 2) {
        return;
    }

    // 数组最小值
    int minValue = arr[0];
    // 数组最大值
    int maxValue = arr[1];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < minValue) {
            minValue = arr[i];
        } else if (arr[i] > maxValue) {
            maxValue = arr[i];
        }
    }

    // 桶数量
    int bucketCount = (maxValue - minValue) / bucketSize + 1;
    int[][] buckets = new int[bucketCount][bucketSize];
    int[] indexArr = new int[bucketCount];

    // 将数组中值分配到各个桶里
    for (int i = 0; i < arr.length; i++) {
        int bucketIndex = (arr[i] - minValue) / bucketSize;
        if (indexArr[bucketIndex] == buckets[bucketIndex].length) {
            ensureCapacity(buckets, bucketIndex);
        }
        buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];
    }

    // 对每个桶进行排序，这里使用了快速排序
    int k = 0;
    for (int i = 0; i < buckets.length; i++) {
        if (indexArr[i] == 0) {
            continue;
        }
        quickSortC(buckets[i], 0, indexArr[i] - 1);
        for (int j = 0; j < indexArr[i]; j++) {
            arr[k++] = buckets[i][j];
        }
    }
}

/**
     * 数组扩容
     *
     * @param buckets
     * @param bucketIndex
     */
private static void ensureCapacity(int[][] buckets, int bucketIndex) {
    int[] tempArr = buckets[bucketIndex];
    int[] newArr = new int[tempArr.length * 2];
    for (int j = 0; j < tempArr.length; j++) {
        newArr[j] = tempArr[j];
    }
    buckets[bucketIndex] = newArr;
}

/**
     * 快速排序递归函数
     *
     * @param arr
     * @param p
     * @param r
     */
private static void quickSortC(int[] arr, int p, int r) {
    if (p >= r) {
        return;
    }

    int q = partition(arr, p, r);
    quickSortC(arr, p, q - 1);
    quickSortC(arr, q + 1, r);
}

/**
     * 分区函数
     *
     * @param arr
     * @param p
     * @param r
     * @return 分区点位置
     */
private static int partition(int[] arr, int p, int r) {
    int pivot = arr[r];
    int i = p;
    for (int j = p; j < r; j++) {
        if (arr[j] <= pivot) {
            swap(arr, i, j);
            i++;
        }
    }

    swap(arr, i, r);
    return i;
}

/**
     * 交换
     *
     * @param arr
     * @param i
     * @param j
     */
private static void swap(int[] arr, int i, int j) {
    if (i == j) {
        return;
    }

    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

计数排序(Counting Sort)

• 当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，就可以把数据划分成k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间
• 计数排序的算法思想很简单，跟桶排序非常类似，只是桶的大小粒度不一样
• 高考查分系统是如何通过成绩快速排序得出名次的？
  • 考生的满分是900分，最小是0分，这个数据的范围很小，所以可以分成901个桶，对应分数从0分到900分。根据考生的成绩，将所有考生划分到这901个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了所有考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是$O(n)$

// 快速计算出每个桶内的数据在有序数组中对应的存储位置
// 计数排序， a是数组， n是数组大小。假设数组中存储的都是非负整数
public void countingSort(int[] a, int n) {
    if (n <= 1) return;
    // 查找数组中数据的范围
    int max = a[0];
    for (int i = 1; i < n; ++i) {
        if (max < a[i]) {
            max = a[i];
        }
    }
    int[] c = new int[max + 1]; // 申请一个计数数组c，下标大小[0,max]
    for (int i = 0; i <= max; ++i) {
        c[i] = 0;
    }
    // 计算每个元素的个数，放入c中
    for (int i = 0; i < n; ++i) {
        c[a[i]]++;
    }
    // 依次累加 c[i]里存储小于等于i的个数
    for (int i = 1; i <= max; ++i) {
        c[i] = c[i - 1] + c[i];
    }
    // 临时数组r，存储排序之后的结果
    int[] r = new int[n];
    // 计算排序的关键步骤，有点难理解
    for (int i = n - 1; i >= 0; --i) {
        int index = c[a[i]] - 1;    // c[i]里存储小于等于i的个数 也就是说 c[i]-1 就是 i 在有序数组中的下标
        r[index] = a[i];
        c[a[i]]--;                  
    }
    // 将结果拷贝给a数组
    for (int i = 0; i < n; ++i) {
        a[i] = r[i];
    }
}

• 计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大很多，就不适合用计数排序了。而且， 计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数

  • 如果考生成绩精确到小数后一位，就需要将所有的分数都先乘以10，转化成整数，然后再放到9010个桶内。再比如，如果要排序的数据中有负数，数据的范围是$[-1000,1000]$，那就需要先对每个数据都加1000，转化成非负整数

• 剑指 Offer 40. 最小的k个数

基数排序(Radix Sort)

• 问题引入：如何给10万个手机号码从小到大排序？
  • 手机号码有11位，范围太大，显然不适合用桶排序和计数排序
  • 快排，时间复杂度可以做到$O(nlogn)$
  • 基数排序，时间复杂度$O(n)$
• 问题解决：
  • 这个问题里有这样的规律：假设要比较两个手机号码a， b的大小，如果在前面几位中， a手机号码已经比b手机号码大了，那后面的几位就不用看了
  • 借助稳定排序算法，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过11次排序之后，手机号码就都有序了

• 根据每一位来排序，可以用刚讲过的桶排序或者计数排序，它们的时间复杂度可以做到$O(n)$。如果要排序的数据有$k$位，那就需要$k$次桶排序或者计数排序，总的时间复杂度是$O(k\ast n)$。当$k$不大的时候，比如手机号码排序的例子， $k$最大就是11，所以基数排序的时间复杂度就近似于$O(n)$
• 有时候要排序的数据并不都是等长的，对于这种不等长的数据可以考虑把数据补齐到相同长度
  • 例如给牛津字典中的单词排序，这些单词不等长，可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据ASCII值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了
• 基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到$O(n)$了

/**
     * 基数排序
     *
     * @param arr
     */
public void radixSort(int[] arr) {
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    // 从个位开始，对数组arr按"指数"进行排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

/**
     * 计数排序-对数组按照"某个位数"进行排序
     *
     * @param arr
     * @param exp 指数
     */
public static void countingSort(int[] arr, int exp) {
    if (arr.length <= 1) {
        return;
    }

    // 计算每个元素的个数
    int[] c = new int[10];
    for (int i = 0; i < arr.length; i++) {
        c[(arr[i] / exp) % 10]++;
    }

    // 计算排序后的位置
    for (int i = 1; i < c.length; i++) {
        c[i] += c[i - 1];
    }

    // 临时数组r，存储排序之后的结果
    int[] r = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        r[c[(arr[i] / exp) % 10] - 1] = arr[i];
        c[(arr[i] / exp) % 10]--;
    }

    for (int i = 0; i < arr.length; i++) {
        arr[i] = r[i];
    }
}

归并排序与快速排序的区别

• 归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为$O(nlogn)$的排序算法，但是它是非原地排序算法。归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题

为什么要考察排序算法的稳定性？

在真正软件开发中，要排序的往往不是单纯的整数，而是一组对象，需要按照对象的某个$key$来排序

比如说，现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果现在有$10$万条订单数据，希望按照金额从小到大对订单数据排序。对于金额相同的订单，希望按照下单时间从早到晚有序。对于这样一个排序需求，应该怎么来做呢？

• 借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，用稳定排序算法，按照订单金额重新排序。两遍排序之后，得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。
  • 稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序

为什么插入排序要比冒泡排序更受欢迎？

冒泡排序和插入排序的时间复杂度都是$O(n^2)$，都是原地排序算法，冒泡排序不管怎么优化，元素交换的次数是一个固定值。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度，但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要$3$个赋值操作，而插入排序只需要$1$个

// 冒泡排序中数据交换操作：
// 比较相邻两个元素的大小，前一个大于后一个就交换
if (array[j] > array[j+1]) {
    int tmp = array[j];
    array[j] = array[j+1];
    array[j+1] = tmp;
    isChange = true;
}

// 插入排序中数据的移动操作：
while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
    arr[insertIndex + 1] = arr[insertIndex]; // 大数后移
    insertIndex--;
}

Reference

• 数据结构与算法之美