排序算法


阅读数: 次   

排序算法概述

排序算法主要分为内部排序和外部排序两大类别

  • 内部排序 ：将数据加载进内存进行排序
  • 外部排序 ：使用内存和外存相结合的方式对数据进行排序
0

相关概念

  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
  • 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面
  • 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律
  • 空间复杂度：指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数
  • k代表数值中的”数位”个数
  • n代表数据规模
  • m代表数据的最大值减最小值
排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
冒泡排序 O(n2) O(n2) O(n) O(1) img
插入排序 O(n2) O(n2) O(n) O(1) img
选择排序 O(n2) O(n2) O(n2) O(1) img
快速排序 O(nlogn) O(n2) O(nlogn) O(nlogn) img
希尔排序 O(nlogn) O(n2) O(n) O(1) img
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) img
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) img
计数排序 O(n + m) O(n + m) O(n + m) O(n + m) img
桶排序 O(n + m) O(n2) O(n) O(n + m) img
基数排序 O(n * k) O(n * k) O(n * k) O(n + k) img

冒泡排序

基本思想

通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

冒泡排序的优化

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。

代码实现

1
2
3
4
5
6
7
8
9
10
11
public void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) { //一共进行 arr.length - 1 次大循环-> 每次冒往出冒一个
        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;
            }
        }
    }
}

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void bubbleSort(int[] arr) {
    boolean flag = false; //flag 初始为 false
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true; //如果在一次小的循环中发生了交换则将 flag 置为 true
                arr[j + 1] = arr[j] + arr[j + 1];
                arr[j] = arr[j + 1] - arr[j];
                arr[j + 1] = arr[j + 1] - arr[j];
            }
        }
        if (!flag) break; //如果判断小循环中没有发生交换则表示序列已经有序 --> 直接退出循环即可
        else flag = false; //重置 flag
    }
}

快速排序

基本思想

  • 从数组中取出一个数，称之为基数（pivot）
  • 遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
  • 将左右两个区域视为两个数组，重复前两个步骤，递归排序即可

基准元素的选择

快速排序是首先定义基准元素 –> 基准元素的选取一般分三种

  • 数组起始元素–> 下标为0
  • 数组的末尾元素 –> 下标为 arr.length - 1
  • 随机选取

选择的基数不同，算法的实现也不同。实际上随机选取的方式的平均时间复杂度是最优的。

分区方法的设计

分区方法的目的包括

  • 将当前数组元素按照基准元素分区，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。
  • 返回当前基准元素的下标 ，为接下来的递归分区确定边界。 –> 基准值的下标在分区的过程是不断变化的

递归退出的条件

我们定义两个指针L， R， 初始分别指向数组的起始和末尾位置 –> L = 0; R =arr.length - 1；

在递归的过程中根据基准元素下标的变化动态的调整 L 及 R ,当 L >= R 时即退出递归

  • L = R ：分区中只有一个元素
  • L > R：分区中没有元素

代码实现

移动”填坑法”实现分区方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void quickSort(int[] arr, int L, int R) {
    if (L > R) return;  //递归推出的条件
    int pivotIndex = partition(arr, L, R); //将数组分区,并返回基准值下标
    quickSort(arr, L, pivotIndex - 1); //对左侧分区进行递归排序
    quickSort(arr, pivotIndex + 1, R); //对右侧分区进行递归排序
}

private static int partition(int[] arr, int L, int R) {
    int left = L;
    int right = R;
    int pivot = arr[left]; //选取数组起始元素为基准值
    while (left != right) {
        //从右向左遍历找到第一个小于基准值的元素
        while (right > left && arr[right] >= pivot) right--;
        arr[left] = arr[right]; //挖坑-> 将right位置处的元素挖走放到 left处
        //从左向右遍历找到第一个比基准值大的元素
        while (left < right && arr[left] <= pivot) left++;
        arr[right] = arr[left]; //填坑 -> 将当前left处的元素填到之前挖走的 right地址处
    }
    //退出循环时-> 基准元素左侧全部小于基准值，基准元素右侧全部大于基准值
    arr[right] = pivot; //将基准值归位
    return left; //返回基准值的当前下标位置,为之后递归分区确定边界, 此时left == right 都指向基准值
}

交换法实现分区方法

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
public void quickSort(int[] arr, int L, int R) {
    if (L > R) return;  
    int pivotIndex = partition(arr, L, R);
    quickSort(arr, L, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, R);
}

private static int partition(int[] arr, int L, int R) {
    int left = L;
    int right = R;
    int pivot = arr[left]; //定义基准值
    while (left != right) {
        while (right > left && arr[right] >= pivot) right--;
        while (left < right && arr[left] <= pivot) left++;
        swap(arr, left, right);
    }
    //退出循环后 left 及 right 相等 -> 同时指向从左到右最后一个小于基准值的元素
    swap(arr, left, L); //将基准值归位 --> 此时基准元素左侧全部小于基准值 基准元素右侧全部大于基准值
    return left;
}

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

插入排序

基本思想

把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，并依次与有序表中的元素值进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

代码实现

交换法

1
2
3
4
5
6
7
8
9
public void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) {
            int temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
        }
    }
}

移动法

1
2
3
4
5
6
7
8
9
10
11
12
public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int curInsertValue = arr[i]; //先将待插入的元素存储起来 --> 前面的元素后移会覆盖它
        int j = i - 1; //从待插入的元素前一个元素开始逐个遍历 并 与待插入元素比较 如果大于待插入元素则向后移动
        while (j >= 0 && arr[j] > curInsertValue) {
            arr[j + 1] = arr[j];
            j--;
        }
        //循环跳出后 -->前面有序数列中空出的位置即为待插入元素的位置 --> 直接赋值即可
        arr[j + 1] = curInsertValue;
    }
}

希尔排序

基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；

随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，所有元素恰被分成一组。

算法图解

1

代码实现

交换法 -> 分组 + 冒泡交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void shellSort(int[] arr) {
    //分组 -> 以间隔 gap 进行分组 [arr[0], arr[0 + gap], arr[0 + gap + gap], ....]
    //每组中共有 arr.length / gap 个元素
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        //对组内元素进行直接插入排序 -> 从 gap 开始，按照顺序将每个元素依次向前插入自己所在的组
        for (int i = gap; i < arr.length; i++) { 
            //在有序序列中依次与待插入元素进行比较，j + gap -> 始终指向待插入元素
            for (int j = i - gap; j >= 0; j -= gap) {
                //将待插入元素冒泡到当前分组的合适位置
                if (arr[j] > arr[j + gap]) {
                    int temp = arr[j];
                    arr[j] = arr[j + gap];
                    arr[j + gap] = temp;
                }
            }
        }
    }
}

移动法 -> 分组 + 插入移动 ==> 真正的希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void shellSort(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            int curInsertValue = arr[i]; //保存当前待插入的元素
            int j = i - gap; //在当前分组中,从待插入元素的前一个元素进行比较
            while (j >= 0 && arr[j] > curInsertValue) {
                arr[j + gap] = arr[j]; //将所有比待插入元素大的元素后移
                j -= gap;
            }
            //循环退出后 j + gap 的指向即为 待插入元素的合适位置
            arr[j + gap] = curInsertValue;
        }
    }
}

简单选择排序

基本思想

从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

同冒泡排序一样都是双层循环，只不过选择排序是每次选定外层循环为基准值 -> 代表最小值；内层循环每次找到当前循环的最小值，并与外层的基准元素进行交换。每次都将最小值交换到序列头部，当外层循环结束的时，序列自然有序~

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i; //记录最小值下标
        for (int j = i + 1; j < arr.length; j++) { //找到最小值下标
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        //循环退出后  minIndex -> 最小值下标 -> 与基准值交换
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

堆排序

基本思想

将无序序列构建成一个堆，根据升序或者降序要求选择大顶堆或者小顶堆

将堆顶元素与末尾元素交换 ==> 将最大元素”沉”到数组的末端

每次交换之后重新调整结构 使其满足堆结构，然后继续交换堆顶元素与当前末尾元素 反复交换 + 调整 直到整个序列有序

注意

堆排序并不是要我们真的建立一颗二叉树 而是借助 顺序存储二叉树的思想 将数据存储从数组形式 ==> 二叉树的存储形式

本质仍然是从一个数组的一般排序状态 ===> 当前数组的特定排序状态

与简单选择排序的区别

选择排序每次通过全盘扫描的方式找到当前循环的最大值 而堆排序是通过创建堆结构的形式通过取出堆顶元素找到当前循环的最大值

代码实现

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
public static void heapSort(int[] arr) {
    //初始创建大顶堆 --> 从右向左,自底向上构建
    //arr.length / 2 - 1 -> 完全二叉树中最后一个非叶子节点的下标
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.length);
    }
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i); //将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
        adjustHeap(arr, 0, i); //在剩余数组空间上调整为大顶堆
    }
}

/**
 * 将数组转换成 "局部大顶堆" -->将以非叶子节点为根节点的子树调整为大顶堆
 *
 * @param arr      待调整数组
 * @param i        非叶子节点在数组中的索引
 * @param heapSize 表示要对数组中多少个元素进行调整
 */
public static void adjustHeap(int[] arr, int i, int heapSize) {
    int l = 2 * i + 1; //左子节点
    int r = l + 1; //右子节点
    int maxIndex = i; //记录最大值的元素下标
    if (l < heapSize && arr[l] > arr[maxIndex]) maxIndex = l;
    if (r < heapSize && arr[r] > arr[maxIndex]) maxIndex = r;
    if (maxIndex != i) {
        swap(arr, i, maxIndex); //将最大值交换为根节点
        adjustHeap(arr, maxIndex, heapSize); //保证交换后仍然是局部大顶堆
    }
}

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

归并排序

基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法

先将整个待排序的数组向下分割成最小块，然后将最小单元按照排序规则向下逐渐进行组合

注意：

在拷贝到原数组时并不是只拷贝最后一次，而是从栈顶开始合并时就开始拷贝，一共合并arr.length - 1 次，所以也一共拷贝了arr.length - 1次

算法图解

2

代码实现

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
62
63
public static void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, temp);
}

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);
        //从栈顶开始合并 一共合并 arr.length - 1 次
        merge(arr, left, mid, right, temp);
    }
}

/**
 * 合并 + 拷贝
 *
 * @param arr   待排序的原始数组
 * @param left  分区后的左边索引
 * @param mid   中间索引 -> 左侧分区的最后一个元素下标
 * @param right 右侧索引
 * @param temp  辅助数组
 */
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left; //初始化 i -> 左边有序序列的初始索引
    int j = mid + 1; // 初始化 j -> 右边有序序列的初始索引
    int t = 0; //t -> 指向temp辅助数组的当前索引 初始为 0
    //1->如果左边有序序列的当前元素小于等于右边的有序序列的当前元素
    //即将左边的当前元素 填充到 temp数组中
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t] = arr[i];
            t++;
            i++;
        } else { //反之 将右边的有序序列的当前元素 填充到 temp 数组中
            temp[t] = arr[j];
            t++;
            j++;
        }
    }
    //2->将有剩余数据的一边的数据全部填充到temp
    while (i <= mid) { //左边的有序序列还有剩余数据，就将全部的数据填充到temp中
        temp[t] = arr[i];
        t++;
        i++;
    }
    while (j <= right) { //右边的有序序列还有剩余数据，就将全部的数据填充到temp中
        temp[t] = arr[j];
        t++;
        j++;
    }
    //3->将temp数组的元素拷贝到arr
    t = 0;
    int start = left; //辅助拷贝指针 -> 初始为 0
    while (start <= right) {
        arr[start] = temp[t];
        t++;
        start++;
    }
}

计数排序

直观的想法

  1. 定义一个能够覆盖数组中最小值到最大值之间各数的数组 –> 作为计数数组
  2. 从头到尾遍历数组中的各个元素，在计数数组中存储各个数字出现的次数
  3. 最后遍历计数数组，将每个元素输出，输出的次数就是对应位置记录的次数

[1,9]数字范围的代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   public static void main(String[] args) {
       int[] arr = {1, 2, 3, 4, 5, 6, 9, 8, 2, 1, 1, 5, 7, 6, 4, 5, 6, 1, 8, 4};
       System.out.println("排序前" + Arrays.toString(arr));
       countingSort(arr);
       System.out.println("排序后" + Arrays.toString(arr));
   }

//对范围[1,9]的数进行排序
   public static void countingSort(int[] arr) {
       int[] count = new int[9];
       for (int element : arr) {
           count[element - 1]++;
       }
       int index = 0;
       for (int i = 0; i < 9; i++) {
           for (int j = 0; j < count[i]; j++) {
               arr[index++] = i + 1;
           }
       }
   }

运行结果

1
2
排序前[1, 2, 3, 4, 5, 6, 9, 8, 2, 1, 1, 5, 7, 6, 4, 5, 6, 1, 8, 4]
排序后[1, 1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 8, 8, 9]

问题

我们发现，在排序完成后，arr 中记录的元素已经不再是最开始的那个元素了，他们只是值相等，但却不是同一个对象。也就是说这样的算法实现是不稳定的—> 因为被排序的对象往往都会携带其他的属性，但这份算法将被排序对象的其他属性都丢失了。

计数排序的基本思想

通过上面的分析我们发现只是通过简单的统计然后按照下标来赋值这样的方式是不稳定的。那么我们可以通过计数的结果，先统计出每个元素在排序完成后的位置，然后将元素赋值到对应位置即可。

算法图解

3

[1,9]数字范围的代码实现如下：

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
public static void countingSort(int[] arr) {
    //定义一个长度为 9 的计数数组 -> 对应元素 [1,9]
    int[] counting = new int[9];
    for (int element : arr) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置
        counting[element - 1]++;
    }
    int pre = 0; //pre -> 记录前面比自己小的数字的总数
    for (int i = 0; i < counting.length; i++) {
        int temp = counting[i];
        counting[i] = pre;
        pre += temp;
    }
    int[] res = new int[arr.length];
    //将arr[]元素按照counting[]中存储的相应位置给res[]赋值
    for (int element : arr) {
        int index = counting[element - 1];
        res[index] = element;
        // 更新 counting[element - 1] -> 特定
        counting[element - 1]++;
    }
    //将结果重新赋值回arr
    for (int i = 0; i < arr.length; i++) {
        arr[i] = res[i];
    }
}

优化代码使其适用于不同数字范围的的排序，代码实现如下：

代码实现-> 真正的计数排序

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
public static void countingSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
        else if (arr[i] < min) min = arr[i];
    }
    int range = max - min + 1; //确定计数范围
    int[] counting = new int[range];
    for (int element : arr) { //统计各个元素个数
        counting[element - min]++;
    }
    int pre = 0;
    for (int i = 0; i < range; i++) { //更新 counting -> 确定位置
        int temp = counting[i];
        counting[i] = pre;
        pre += temp;
    }
    int[] res = new int[arr.length];
    for (int element : arr) {
        res[counting[element - min]] = element;
        counting[element - min]++;
    }
    for (int i = 0; i < arr.length; i++) {
        arr[i] = res[i];
    }
}

桶排序

基本思想

将数据集划分多个范围相同的区间，每个自区间自排序，最后合并。

与计数排序的联系

桶排序是对计数排序的改进，计数排序申请的额外空间跨度从最小元素值到最大元素值，若待排序集合中元素不是依次递增的，则必然有空间浪费情况。桶排序则是弱化了这种浪费情况，将最小值到最大值之间的每一个位置申请空间，更新为最小值到最大值之间每一个固定区域申请空间，尽量减少了元素值大小不连续情况下的空间浪费情况。

实现步骤

  1. 根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数；
  2. 遍历待排序集合，将每一个元素移动到对应的桶中；
  3. 对每一个桶中元素进行排序，并移动到已排序集合中；

算法图解

将元素分配到桶中

4

对桶中的元素进行排序

5

代码实现

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
public static void bucketSort(int[] arr) {
    //确定最大值,最小值
    int max = 0;
    int min = 0;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    //计算桶的数量
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    //创建相应的桶
    for (int i = 0; i < bucketNum; i++) {
        list.add(new ArrayList<>());
    }
    //将各个元素放入到对应的桶中
    for (int element : arr) {
        int bucketIndex = (element - min) / arr.length;
        list.get(bucketIndex).add(element);
    }
    //对各个单独的桶进行排序 -> 此处的内部排序算法可以自行选择
    for (int i = 0; i < list.size(); i++) {
        Collections.sort(list.get(i));
    }
    //将已排序好的元素拷贝到原数组中
    int index = 0;
    for (int i = 0; i < list.size(); i++) {
        for (int j = 0; j < list.get(i).size(); j++) {
            arr[index++] = list.get(i).get(j);
        }
    }
}

基数排序

基本思想

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零

然后，从最低位开始，依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

主要步骤

  • 找出数组中最大的数字的位数 maxLength
  • 获取数组中每个数字的基数
  • 遍历 maxLength 轮数组，每轮按照基数对其进行排序

负数的处理

在对基数进行计数排序时，申请长度为 19 的二维数组数组–> 申请19个桶，用来存储 [-9, 9] 这个区间内的所有整数。

在把每一位基数计算出来后，加上 9，就能对应上bucketElementCounts 数组的下标了，bucketElementCounts 数组的下标 [0, 18] 对应基数 [-9, 9]；

代码实现

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
    public static void radixSort(int[] arr) {
        int max = arr[0]; //初始化数组的最大值
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //记录数组中最大值的位数
        int maxLength = (max + "").length();
        //定义一个二维数组表示十个桶-> 每个桶就是一个一维数组
        //防止数据溢出->每个桶的大小设置为 arr.length
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //比如：bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];
        //一共进行maxLength次循环->每次循环按照元素对应的数位,放入不同的桶中,在依次取出排序
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素对应位的值 -> 123 ==> 3, 2, 1 
                int digitOfElement = arr[j] / n % 10; 
                //将元素按照个位、十位、百位...依次放入对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            int index = 0;
            //遍历十个桶,依次将将桶中的元素放入到原数组
            for (int k = 0; k < 10; k++) {
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    arr[index++] = bucket[k][l];
                }
                //每轮处理后清空当前桶
                bucketElementCounts[k] = 0; 
            }
//            System.out.println("第" + (i + 1) + "轮的排序处理 arr =" + Arrays.toString(arr));
        }
    }

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true