梦想还是要有的，万一忘了咋办？

0%

排序算法

发表于 分类于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

排序算法算是最基础、常见的算法了。同时排序算法也拥有相当多的方案，选择排序、冒泡排序、插入排序、希尔排序、快速排序，归并排序、计数排序、基数排序、通排序。

排序算法评价指标

执行效率

  • 时间复杂度（最好、坏、平均）
  • 时间复杂度系数、常数、低阶
  • 比较次数和交换（移动）次数

内存消耗

  • 空间复杂度
  • 原地排序，特指空间复杂度是O(1)

稳定性

经过排序后相等元素之间原有的先后顺序不变。例如订单，先按照时间排序、再按照金额排序。

常见排序算法

算法 时间复杂度 空间复杂度 原地 稳定性
冒泡 O(n^2) O(1) ✔️ ✔️
选择 O(n^2) O(1) ✔️ ❌
插入 O(n^2) O(1) ✔️ ✔️
归并 O(nlogn) O(n) ❌ ✔️
快排 O(nlogn) O(1) ✔️ ✔️

冒泡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 冒泡排序
 * 时间复杂度：O(N^2)
 * 空间复杂度：O(1)
 * 原地排序：是
 *
 * @param arrs
 */
public static void bubble(int[] arrs) {
    for (int i = 0; i < arrs.length - 1; i++) {
        for (int j = 0; j < arrs.length - i - 1; j++) {
            if (arrs[j] > arrs[j + 1]) {
                int temp = arrs[j];
                arrs[j] = arrs[j + 1];
                arrs[j + 1] = temp;
            }
        }
    }
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
   * 插入排序(直接)
   * 时间复杂度：O(n^2)
   * 空间复杂度：O(1)
   * 原地排序：是
   *
   * @param arrs
   */
  public static void insertSort(int[] arrs) {
      for (int i = 1; i < arrs.length; i++) {
          int tmp = arrs[i];
          for (int j = i - 1; j >= 0; j--) {
              if (tmp < arrs[j]) {
                  arrs[j + 1] = arrs[j];
                  arrs[j] = tmp;
              }
          }
      }
  }

选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
   * 选择排序
   * 1、遍历i-len 数组，找出最小值游标。
   * 2、将最小值与i交换。
   *
   * @param arrs
   */
  public static void selectionSort(int[] arrs) {
      for (int i = 0; i < arrs.length - 1; i++) {
          int tmpIdx = i;
          for (int j = i + 1; j < arrs.length; j++) {
              if (arrs[tmpIdx] > arrs[j]) {
                  tmpIdx = j;
              }
          }
          int tmp = arrs[i];
          arrs[i] = arrs[tmpIdx];
          arrs[tmpIdx] = tmp;
      }
  }

快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/***
     * 快速排序
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     * 是原地排序
     * @param arrs
     */
    public static void quickSort(int[] arrs) {
        quickSortC(arrs, 0, arrs.length - 1);
    }

    /***
     * 快速排序递归函数
     * @param arrs
     * @param p
     * @param r
     */
    private static void quickSortC(int[] arrs, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = partition(arrs, p, r);
        quickSortC(arrs, p, q - 1);
        quickSortC(arrs, 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;
    }

线性排序算法

以下排序算法对场景要求苛刻但时间复杂度非常棒：O(n)，因此称为线性排序算法，包含：桶排序、计数排序、基数排序。

桶排序

核心思想：将要排序的数据分到几个有序的桶里面，每个桶的数据再进行单独的排序。桶内数据排完序后，按照排序顺序依次取出，组成的序列就是有序的了。

要求：

  • 要排序数据很容易划分为m个有序的桶。
  • 各个桶之间的分布是比较均匀的。

案例：
有限内存中对10GB的订单数据依照订单金额进行排序，可以按照订单金额将数据分割成m个文件。

  • 假如订单金额取值范围（0，10万），可以分成100个文件（00，99）分别对应0-1000，1001-2000…的数据。
  • 70%金额集中在1001-2000的，01文件数据量依旧很大。对其再次按金额分割
  • 重复上面两步，直到所有文件都可以加载到内存为止

示例

1

计数排序

计数排序是特殊的桶排序，即 每个桶的值是相同的。
要求

  • 数据范围有限，比如（0,k）我们可以将数据划分为k个桶。
  • 每个桶数据相同，省去桶内排序时间了
  • 值必须是正整数
    • 若小数可以通过扩大10的倍数转换为正整数
         - 取值（-1000，1000）通过+1000解决

案例
高考查分系统，系统需要显示：成绩、省内排名。假如有50万考生，满分是900分

  • 我们可以将其分为901个桶（0，900）
  • 将考生划分到这901个桶内
  • 依次扫描每个桶，将桶内考生依次输出就实现了50万考生的排序。

为何叫计数排序？
还是高考查分系统案例，

  • 申请一个901的数组，数组下标=成绩（0，900）。
  • 数组内记录，对应学生个数
  • 依公式arr[n]=arr[n]+arr[n-1],对数组进行计算后可以理解为≤n的人数一共有arr[n]个。
  • 依次遍历学生成绩n，此时的arr[n]就是其排名，同时n–。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/***
   * 计数排序
   * 时间复杂度：O(n)
   * 适用场景：待排序数据，可以分为k个桶，其中k比较小。
   */
  public static void countSort(int[] arrs) {
      int max = 0;
      for (int i = 0; i < arrs.length; i++) {
          if (arrs[i] > max) {
              max = arrs[i];
          }
      }
      //设置桶的数量
      int[] tmp = new int[max + 1];
      //统计每个数字出现个数
      for (int i = 0; i < arrs.length; i++) {
          tmp[arrs[i]]++;
      }
      //累加
      for (int i = 1; i < tmp.length; i++) {
          tmp[i] += tmp[i - 1];
      }
      //申请新的数组空间
      int[] result = new int[arrs.length];
      //依次将待排序数据放到指定位置
      //必须倒着来
      for (int i = arrs.length-1; i >=0; i--) {
          int pos = tmp[arrs[i]]--;
          result[pos - 1] = arrs[i];
      }
      //拷贝回原数组
      for (int i = 0; i < result.length; i++) {
          arrs[i] = result[i];
      }
  }


基数排序

要求：

  • 可以分割出独立的“位”来比较
    • 位数不同时可以补齐
  • 位之间有递进关系高位大的低位不用比较。
  • 每位数据范围不应太大，要可以使用线性排序算法

案例

给10万个手机号进行从小到大排序。

  • 取个位进行计数排序
  • 取十位进行计数排序
  • 依次直到最后一位为止

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/***
     * 基数排序
     * 时间复杂度:O(n)
     * 适用场景：
     *  a、可以按位分割、且位之间递进关系，即 高位大的一定大
     * @param arrs
     */
    public static void radixSort(long[] arrs) {
        long pos = 1;
        for (int i = 0; i < 11; i++) {
            countSort(arrs, pos );
            pos *= 10;
        }
    }
    /**
     * pos=10,100,1000...
     */
    public static void countSort(long[] arrs, long pos) {
        //设置桶的数量
        int[] tmp = new int[10];
        //统计每个数字出现个数
        for (int i = 0; i < arrs.length; i++) {
            int n=(int)(arrs[i]/pos%10);
            tmp[n]++;
        }
        //累加
        for (int i = 1; i < tmp.length; i++) {
            tmp[i] += tmp[i - 1];
        }
        //申请新的数组空间
        long[] result = new long[arrs.length];
        //依次将待排序数据放到指定位置
        //这里必须是 倒着开始
        for (int i = arrs.length-1; i >= 0; i--) {
            int n=(int)(arrs[i] / pos%10);
            int m = tmp[n]--;
            result[m - 1] = arrs[i];
        }
        //拷贝回原数组
        for (int i = 0; i < result.length; i++) {
            arrs[i] = result[i];
        }
    }