排序算法的执行效率

  • 最好情况、最坏情况、平均时间复杂度；
  • 时间复杂度的系数、常数、低阶；
  • 比较次数和交换次数。

排序算法的稳定性

概念：

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

场景：

如果要给电商交易系统中的订单排序，订单有两个属性，一个是下单时间、一个是订单金额；现在有10万条数据，希望按照金额从小到大对订单数据进行排序；对于金额相同的订单，按照下单时间从早到晚排序，如何实现？
  • 普通思路：先按照金额对订单数据排序，在遍历订单数据对每个金额相同的小区间再按照下单时间排序；
  • 最优思路：借助稳定排序算法，先按照下单时间对订单数据排序，在使用稳定排序算法按照订单金额重新排序，即得到。


冒泡排序

  • 概念：只会操作相邻的两个数据，每次遍历只保证一个数字。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小要求，不满足就交换；
  • 稳定性：当有相邻的两个元素大小相等的时候，我们不做交换，那么就不会改变顺序；

早期代码：

最优时间复杂度、最坏时间复杂度都为：O(n^2)；因为无论是否有序，都经过两层循环。 
package com.hshuo.sort;

import java.util.Arrays;

/**
 * @author SHshuo
 * @data 2022/5/10--23:10
 * 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] res = new int[]{4, 1, 5, 6, 3, 2};
        for(int i = 0; i < res.length; i++){
            for(int j = 0; j < res.length - i - 1; j++){
//                不加=、实现稳定排序
                if(res[j] > res[j + 1]){
                    swap(res, j, j + 1);
                }
            }
        }

        System.out.println(Arrays.toString(res));
    }
}

平时代码：

  • 最优时间复杂度为：O（n）；有序的时候，通过一次遍历会调出两层循环。
  • 最坏时间复杂度都为：O(n^2)； 
package com.hshuo.sort;

import java.util.Arrays;

/**
 * @author SHshuo
 * @data 2022/5/10--23:10
 * 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] res = new int[]{4, 1, 5, 6, 3, 2};

//        平时版本：
//        最优时间复杂度：O(n)、一次遍历，跳出两个循环
//        最坏时间复杂度都为：O(n^2)
        for(int i = 0; i < res.length; i++){

            boolean flag = false;

            for(int j = 0; j < res.length - i - 1; j++){
//                不加=、实现稳定排序
                if(res[j] > res[j + 1]){
                    flag = true;
                    swap(res, j, j + 1);
                }
            }
            
//            说明完全有序，比较的结果全部递增
            if(!flag){
                break;
            }
        }

        System.out.println(Arrays.toString(res));
    }
}

插入排序

  • 概念：将数组分为两个区间，已排序区间和未排序区间；取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。
  • 稳定性：对于值相同的元素，将后出现的元素放在先出现元素的后面，也就是遇到相同元素不交换；

  • 最优时间复杂度：O（n）；如果面对数据有序的时候，当前值比前一个大，默认为之前的数据全部有序，不用交换；所以时间复杂度会退化成O（n）
  • 最坏时间复杂度：O（n^2）。 
package com.hshuo.sort;

import java.util.Arrays;

import static com.hshuo.sort.BubbleSort.swap;

/**
 * @author SHshuo
 * @data 2022/4/3--10:23
 * 插入排序
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 4, 2};
        for(int i = 0; i < arr.length; i++){
            for(int j = i; j > 0; j--){
//                不加=、保证了稳定性
                if(arr[j] < arr[j - 1]){
                    swap(arr, j, j - 1);
                }else{
//                    保证了最好时间复杂度
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

补充：为什么插入排序比冒泡排序更受欢迎？

  • 主要原因是由于冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个；所以插入排序用时更短。

选择排序（不常用）

  • 概念：数组分为已排序区间和未排序区间；选择排序每次会从未排序区间中找到最小的元素，与已排序区间的末尾进行交换；
  • 不稳定：每次都要找到剩余未排序元素中的最小值，与前面的元素进行交换位置。

  • 最好时间复杂度：O（n^2）；因为每次都要在未排序区间寻找最小值，这个过程与是否排序无关。
  • 最坏时间复杂度：O（n^2）； 
package com.hshuo.sort;

import java.util.Arrays;

import static com.hshuo.sort.BubbleSort.swap;

/**
 * @author SHshuo
 * @data 2022/5/11--9:45
 * 选择排序（根据未排序区间的最小值进行排序害了它）
 * 逊色太多、基本不会用到
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] res = new int[]{4, 1, 5, 6, 3, 2};

        for(int i = 0; i < res.length; i++){
//            假设当前位置是最小值的位置
            int min = i;

            for(int j = i + 1; j < res.length; j++){
//                无论是否有序都需要找到最小值
                if(res[j] < res[min]){
                    min = j;
                }
            }

            if(min != i){
                swap(res, i, min);
            }
        }

        System.out.println(Arrays.toString(res));
    }
}

桶排序

亿级数据进行排序？

场景题：我们有10GB的订单数据，希望按订单金额进行排序，但是我们的内存有限，只有几百MB，没办法一次性把10GB的数据加载到内存中？
  • 使用桶排序（分桶的过程其实也是分治的思想），对数据进行划分，使得每个桶存储大约100MB的订单数据；（如果数据不是均匀分布，可能出现比较大的桶，则继续划分）；
  • 将桶内的数据一次读入到内存中，进行快排排序；
  • 将排序好的订单数据写入到一个文件中（合并），此文件就存储了按照金额从小到大排序的订单数据。

计数排序

是一种特殊的桶排序，当范围很小的时候，每个桶只有一个数值；
场景题：高考查分，考生的分数范围是固定的（750~0），需要将100万个考生进行成绩排序？
  • 使用计数排序，将100万考生分到751个桶里，桶内的数据都是分数相同的考生，所以不需要再进行排序；
  • 只需要一次扫描每个桶，就实现了考生成绩的排序，时间复杂度为：O（n）。
具体实现：
每个桶存储的是元素的个数，通过res[i] += res[i - 1]累加的方式，计算出比这个桶小的个数，也就是对应的位置。

基数排序

场景题：希望将10万个手机号码从小到大排序？
  • 按照位来进行运算，建立0~9个桶；
  • 先按照最后一位来排序手机号，进桶出桶；
  • 之后按照代数第二位来排序手机号，进桶出桶，依次类推；
  • 依靠稳定性排序。


bitmap

从亿级数据中寻找最多重复一次的条件的数据？

  • 使用位图法、2-bitmap实现。每个数分配2bit，00表示不存在，01表示出现一次，10表示出现多次，11表示没有意义；
  • 初始化均为00，遍历修改bitmap对应的位置；如果是00则变为01,01则变为10,10则保持不变；最后输出对应位为01的数据。

时间复杂度