Java实现十大经典排序算法

小管
算法排序

发布于：Nov 28, 2020
次浏览

5.8k words

24 min
0  

排序算法分类

  • 内部排序：指在排序期间，元素全部存放在内存中的排序，常见的内部排序算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、基数排序等。
  • 外部排序：指在排序期间，元素无法完全全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。
  • 比较类排序：：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破$\mathrm O({\mathrm{Nlog}}_2\mathrm N)$，因此也称为非线性时间比较类排序。
  • 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 常见的非比较类排序算法有：基数排序、计数排序、桶排序。

一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。但是，并非所有的内部排序算法都要基于比较操作。

每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性能而言，很难提出一种被认为是最好的算法。通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序和基数排序五大类，内部排序算法的性能取决于算法的时间复杂度和空间复杂度，而时间复杂度一般是由比较和移动的次数决定的。

一、冒泡排序 (Bubble Sort)

1.原理

每次检查相邻的两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻元素需要交换时，排序就完成了。

经过$i$次扫面后，数列的末尾$i$项必然是最大的$i$项，因此冒泡排序最多需要扫描$n-1$遍数组就能完成扫描。

2.步骤

  • ① 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  • ② 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  • ③ 针对所有的元素重复步骤 ① ~ ②，除了最后一个元素，直到排序完成。

3.动画演示

Bubble-sort

4.性能分析

平均时间复杂度：$\mathrm O(\mathrm N^2)$

最佳时间复杂度：$\mathrm O(\mathrm N)$

最差时间复杂度：$\mathrm O(\mathrm N^2)$

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

排序方式：In-place
稳定性：稳定

5.代码

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

冒泡排序还有一种优化算法，就是立一个 flag，当某一趟序列遍历中元素没有发生交换，则证明该序列已经有序，就不再进行后续的排序。动画演示里就是改进后的算法，改进后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void bubbleSort(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length - 1; j++)
                if (arr[j - 1] > arr[j]) {
                    int temp;
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                    flag = false;
                }
            if (flag)
                return;
        }
    }

二、选择排序 (Selection Sort)

1.原理

每次找出第$i$小的元素 (也就是$A_{i..n}$中最小的元素)，然后将这个元素与数组第$i$个位置上的元素交换。

2.步骤

  • ① 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
  • ② 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
  • ③ 重复步骤 ②，直到所有元素均排序完毕。

3.动画演示

4.性能分析

平均时间复杂度：$\mathrm O(\mathrm N^2)$

最佳时间复杂度：$\mathrm O(\mathrm N^2)$

最差时间复杂度：$\mathrm O(\mathrm N^2)$

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

排序方式：In-place
稳定性：不稳定

5.代码

1
2
3
4
5
6
7
8
9
10
11
public void selectionSort(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[min] > arr[j])
                    min = j;
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }

三、插入排序 (Insertion Sort)

1.原理

将排列元素划分为“已排序”和”未排序”两部分，每次从”未排序的”元素中选择一个插入到”已排序”的元素中的正确位置。

一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌。按牌面大小插到手牌后，再抓下一张牌。

2.步骤

  • ① 从第一个元素开始，该元素可以认为已经被排序；
  • ② 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  • ③ 如果该元素（已排序的）大于新元素，将该元素往右移到下一位置，重复该步骤，直到找到已排序的元素小于或者等于新元素的位置；
  • ④ 将新元素插入到步骤 ③ 找到的位置的后面；
  • ⑤ 重复步骤 ② ~ ④。

3.动画演示

4.性能分析

平均时间复杂度：$\mathrm O(\mathrm N^2)$

最差时间复杂度：$\mathrm O(\mathrm N^2)$

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

排序方式：In-place
稳定性：稳定

5.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void insertSort(int arr[]) {
        if(arr == null || arr.length <= 0){
            return;
        }
        for(int i = 1; i < arr.length; i++){
            int tmp = arr[i];
            int j;
            for(j = i-1; j >= 0; j--){
                //如果比tmp大把值往后移动一位
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }
                else{
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

四、希尔排序 (Shell Sort)

1.原理

排序对不相邻的记录进行比较和移动：

  1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）

  2. 对这些子序列进行插入排序；

  3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。

2.步骤

  • ① n 为数组长度，首先取一个整数$d1=n/2$，将元素分为$d1$ 个组，每组相邻量元素之间距离为$d1-1$，在各组内进行直接插入排序；

  • ② 取第二个整数$d2=d1/2$，重复步骤 ① 分组排序过程，直到$di=1$，即所有元素在同一组内进行直接插入排序。

PS：希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。

3.动画演示

4.性能分析

平均时间复杂度：$\mathrm O({\mathrm{Nlog}}_2\mathrm N)$

最佳时间复杂度：
最差时间复杂度：$\mathrm O(\mathrm N^2)$

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

稳定性：不稳定
复杂性：较复杂

5.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public void shellSort(int arr[]) {
        int gap = 1;
        int j;
        while (gap < arr.length / 3)
            gap = gap * 3 + 1;
        for (; gap > 0; gap /= 3)
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                    arr[j + gap] = arr[j];
                arr[j + gap] = temp;
            }
    }

五、归并排序 (Merge Sort)

1.原理

归并排序分为三个步骤：

  1. 将数列划分为两部分；
  2. 递归地分别对两个子序列进行归并排序；
  3. 合并两个子序列。

不难发现，归并排序的前两步都很好实现，关键是如何合并两个子序列。注意到两个子序列在第二步中已经保证了都是有序的了，第三步中实际上是想要把两个 有序 的序列合并起来。

2.步骤

  1. 归并的基本步骤

    • ① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
    • ② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
    • ③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
    • ④ 重复步骤 ③ 直到某一指针达到序列尾；
    • ⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。

  2. 归并排序的步骤

    • ① 分解：将列表越分越小，直至分成一个元素，终止条件：一个元素是有序的。
    • ② 合并：不断将两个有序列表进行归并，列表越来越大，直到所有序列归并完毕。

3.动画演示

4.性能分析

平均时间复杂度：$\mathrm O({\mathrm{Nlog}}_2\mathrm N)$

最佳时间复杂度：$\mathrm O(\mathrm N)$

最差时间复杂度：$\mathrm O({\mathrm{Nlog}}_2\mathrm N)$

空间复杂度：$\mathrm O(\mathrm N)$

排序方式：In-place
稳定性：稳定

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
public void mergeSort(int arr[]) {
        int len = arr.length;
        int[] result = new int[len];
        int block, start;

        // 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
        for (block = 1; block < len * 2; block *= 2) {
            for (start = 0; start < len; start += 2 * block) {
                int low = start;
                int mid = (start + block) < len ? (start + block) : len;
                int high = (start + 2 * block) < len ? (start + 2 * block) : len;
                //两个块的起始下标及结束下标
                int start1 = low, end1 = mid;
                int start2 = mid, end2 = high;
                //开始对两个block进行归并排序
                while (start1 < end1 && start2 < end2) {
                    result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
                }
                while (start1 < end1) {
                    result[low++] = arr[start1++];
                }
                while (start2 < end2) {
                    result[low++] = arr[start2++];
                }
            }
            int[] temp = arr;
            arr = result;
            result = temp;
        }
        result = arr;
    }

递归法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void mergeSortRecursive(int[] arr, int[] result, int start, int end) {
        if (start >= end)
            return;
        int len = end - start, mid = (len >> 1) + start;
        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;
        mergeSortRecursive(arr, result, start1, end1);
        mergeSortRecursive(arr, result, start2, end2);
        int k = start;
        while (start1 <= end1 && start2 <= end2)
            result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
        while (start1 <= end1)
            result[k++] = arr[start1++];
        while (start2 <= end2)
            result[k++] = arr[start2++];
        for (k = start; k <= end; k++)
            arr[k] = result[k];
    }

    public static void mergeSort(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];
        mergeSortRecursive(arr, result, 0, len - 1);
    }

六、快速排序 (Quick sort)

1.原理

通过分治的方式来将一个数组排序。

快速分为三个过程：

  1. 将数列划分为两部分 (要保证相对大小关系);
  2. 递归到连个子序列中分别进行快速排序;
  3. 不用合并，因为此时数列已经完全有序。

和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择一个数$m$来当作两个子数列的分界。

之后，维护一前一后两个指针$p$和$q$，依次考虑当前的数是否放在了应该放的位置 (前还是后)。如果当前的数没放对，比如说如果后面的指针$q$遇到了一个比$m$小的数，那么可以交换$p$和$q$位置上的数，再把$p$向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。

2.步骤

  • ① 从数列中挑出一个元素，称为 “基准值”;
  • ② 重新排序数列，所有元素比基准值小的放在基准值的左边，比基准值大的放在基准值的右边（相同的数可以到任一边）。在这个分区退出之后，该基准值就处于数列的中间位置。这个称为分区（partition）操作，也可以称为一次归位操作，归位操作的过程见下动图；
  • ③ 递归地把小于基准值元素的子数列和大于基准值元素的子数列按照步骤 ① ② 排序。

3.动画演示

4.性能分析

平均时间复杂度：$\mathrm O({\mathrm{Nlog}}_2\mathrm N)$

最佳时间复杂度：$\mathrm O({\mathrm{Nlog}}_2\mathrm N)$

最差时间复杂度：$\mathrm O(\mathrm N^2)$

空间复杂度：根据实现方式的不同而不同

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
class quickSort {
    int[] arr;
    private void swap(int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
    private void quick_sort_recursive(int start, int end) {
        if (start >= end)
            return;
        int mid = arr[end];
        int left = start, right = end - 1;
        while (left < right) {
            while (arr[left] <= mid && left < right)
                left++;
            while (arr[right] >= mid && left < right)
                right--;
            swap(left, right);
        }
        if (arr[left] >= arr[end])
            swap(left, end);
        else
            left++;
        quick_sort_recursive(start, left - 1);
        quick_sort_recursive(left + 1, end);
    }
    public void sort(int[] arrin) {
        arr = arrin;
        quick_sort_recursive(0, arr.length - 1);
    }
}

七、堆排序 (Heap Sort)

1.原理

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

  • 堆：一种特殊的完全二叉树结构
  • 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
  • 小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小

2.步骤

  • ① 构建堆：将待排序序列构建成一个堆 H[0……n-1]，从最后一个非叶子结点开始，从左至右，从下至上进行调整。根据升序或降序需求选择大顶堆或小顶堆；
  • ② 此时的堆顶元素，为最大或者最小元素；
  • ③ 把堆顶元素和堆尾元素互换，调整堆，重新使堆有序；
  • ④ 此时堆顶元素为第二大元素；
  • ⑤ 重复以上步骤，直到堆变空。

3.动画演示

4.性能分析

平均时间复杂度：$\mathrm O({\mathrm{Nlog}}_2\mathrm N)$

最佳时间复杂度：$\mathrm O({\mathrm{Nlog}}_2\mathrm N)$

最差时间复杂度：$\mathrm O({\mathrm{Nlog}}_2\mathrm N)$

稳定性：不稳定

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
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
import java.util.Arrays;
public class HeapSort {

    private int[] arr;

    public HeapSort(int[] arr){
        this.arr = arr;
    }

    /**
     * 堆排序的主要入口方法，共两步。
     */
    public void sort(){
        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1;
        for(int i = beginIndex; i >= 0; i--){
            maxHeapify(i, len);
        }

        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for(int i = len; i > 0; i--){
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

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

    /**
     * 调整索引为 index 处的数据，使其符合堆的特性。
     *
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆（数组）的长度
     */
    private void maxHeapify(int index,int len){
        int li = (index << 1) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cMax = li;             // 子节点值最大索引，默认左子节点。

        if(li > len) return;       // 左子节点索引超出计算范围，直接返回。
        if(ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
            cMax = ri;
        if(arr[cMax] > arr[index]){
            swap(cMax, index);      // 如果父节点被子节点调换，
            maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }

八、计数排序 (Counting Sort)

1.原理

使用一个额外的数组 $C$，其中第$i$ 个元素是待排序数组$A$中值等于$i$的元素的个数，然后根据数组$C$来将$A$中的元素排到正确的位置。

他的工作过程分为三个步骤：

  1. 计算每个数出现了几次；
  2. 求出每个数的前缀和；
  3. 利用出现次数的前缀和，从右至左计算每个数的排名。

2.步骤

  • ① 找到待排序列表中的最大值 k，开辟一个长度为 k+1 的计数列表，计数列表中的值都为 0。
  • ② 遍历待排序列表，如果遍历到的元素值为 i，则计数列表中索引 i 的值加1。
  • ③ 遍历完整个待排序列表，计数列表中索引 i 的值 j 表示 i 的个数为 j，统计出待排序列表中每个值的数量。
  • ④ 创建一个新列表（也可以清空原列表，在原列表中添加），遍历计数列表，依次在新列表中添加 j 个 i，新列表就是排好序后的列表，整个过程没有比较待排序列表中的数据大小。

3.动画演示

4.性能分析

平均时间复杂度：$\mathrm O(\mathrm N+\mathrm K)$

最佳时间复杂度：$\mathrm O(\mathrm N+\mathrm K)$

最差时间复杂度：$\mathrm O(\mathrm N+\mathrm K)$

空间复杂度：$\mathrm O(\mathrm N+\mathrm K)$

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
33
public class CountingSort {
    public static void main(String[] argv) {
        int[] A = CountingSort.countingSort(new int[]{16, 4, 10, 14, 7, 9, 3, 2, 8, 1});
        Utils.print(A);
    }
    public static int[] countingSort(int[] A) {
        int[] B = new int[A.length];
        // 假设A中的数据a'有，0<=a' && a' < k并且k=100
        int k = 100;
        countingSort(A, B, k);
        return B;
    }
    private static void countingSort(int[] A, int[] B, int k) {
        int[] C = new int[k];
        // 计数
        for (int j = 0; j < A.length; j++) {
            int a = A[j];
            C[a] += 1;
        }
        Utils.print(C);
        // 求计数和
        for (int i = 1; i < k; i++) {
            C[i] = C[i] + C[i - 1];
        }
        Utils.print(C);
        // 整理
        for (int j = A.length - 1; j >= 0; j--) {
            int a = A[j];
            B[C[a] - 1] = a;
            C[a] -= 1;
        }
    }
}

九、桶排序 (Bucket Sort)

1.原理

桶排序又叫箱排序，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。

桶排序也是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  • 在额外空间充足的情况下，尽量增大桶的数量；
  • 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

  • 最快情况：当输入的数据可以均匀的分配到每一个桶中；
  • 最慢情况：当输入的数据被分配到了同一个桶中。

2.步骤

  • ① 创建一个定量的数组当作空桶子；
  • ② 遍历序列，把元素一个一个放到对应的桶子去；
  • ③ 对每个不是空的桶子进行排序；
  • ④ 从不是空的桶子里把元素再放回原来的序列中。

3.动画演示

4.性能分析

平均时间复杂度：$\mathrm O(\mathrm N+\mathrm K)$

最佳时间复杂度：$\mathrm O(\mathrm N+\mathrm K)$

最差时间复杂度：$\mathrm O(\mathrm N^2)$

空间复杂度：$\mathrm O(\mathrm N\ast\mathrm K)$

稳定性：稳定

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class BucketSort {

    /**
     * 桶排序
     * @param arr
     * @return
     */
    public static double[] bucketSort(double[] arr){
        //1.计算出最大值和最小值，求出两者的差值
        double min = arr[0];
        double max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]){
                max = arr[i];
            }
            if (arr[i] < min){
                min = arr[i];
            }
        }
        double d = max - min;

        //2.初始化桶
        int bucketNum = arr.length;
        List<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<>());
        }

        //3.遍历数组中的元素，把所有元素都放入对应的桶当中
        for (int i = 0; i < arr.length; i++) {
            //计算当前元素应该放在哪个桶里面
            int num = (int)((arr[i] - min) / (d / (bucketNum - 1)));
            bucketList.get(num).add(arr[i]);
        }

        //4.对每个桶里面的元素进行排序
        for (int i = 0; i < bucketNum; i++) {
            Collections.sort(bucketList.get(i));
        }

        //5.输出全部元素
        int k = 0;
        for(LinkedList<Double> doubles : bucketList){
            for (Double aDouble : doubles) {
                arr[k] = aDouble;
                k++;
            }
        }

        return arr;
    }
}

十、基数排序 (Radix Sort)

1.原理

基数排序属于分配式排序，是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序、计数排序、桶排序三种排序算法都利用了桶的概念，但对桶的使用方法上是有明显差异的：

  • 基数排序：根据键值的每位数字来分配桶；
  • 计数排序：每个桶只存储单一键值；
  • 桶排序：每个桶存储一定范围的数值。

2.步骤

  • ① 取数组中的最大数，并取得位数；
  • ② 从最低位开始，依次进行一次排序；
  • ③ 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

3.动画演示

4.性能分析

时间复杂度：$\mathrm O(\mathrm N\ast\mathrm K)$

空间复杂度：$\mathrm O(\mathrm N+\mathrm K)$

稳定性：稳定

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class RadixSort{
    public static void radixSort(int[] arr) {
        int maxValue = arr[0];
        int minValue = arr[0];
        for (int i = 1; i < arr.length; i++) {
            maxValue = Math.max(maxValue, arr[i]);
            minValue = Math.min(minValue, arr[i]);
        }
        // 如果最小值为负数，则数组中的数全部减去最小值，这样能保证数组中最小数是0
        if (minValue < 0) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] -= minValue;
            }
            // 最大值也需要减，不然可能出现位数发生变化
            maxValue -= minValue;
        }

        int length = String.valueOf(maxValue).length();
        // 表示10个桶
        int[][] bucket = new int[10][arr.length];
        // 记录每个桶实际存放几个数据，比如：bucketElementCount[0]记录着bucket[0]桶放入数据个数
        int[] bucketElementCount = new int[10];

        for (int i = 0, j = 1; i < length; i++, j *= 10) {
            for (int k = 0; k < arr.length; k++) {
                int element = arr[k] / j % 10;
                bucket[element][bucketElementCount[element]] = arr[k];
                bucketElementCount[element]++;
            }

            int index = 0;
            // 遍历每个桶的数量，放入原数组
            for (int n = 0; n < bucketElementCount.length; n++) {
                if (bucketElementCount[n] != 0) {
                    for (int t = 0; t < bucketElementCount[n]; t++) {
                        arr[index++] = bucket[n][t];
                    }
                }
                // 需要把bucketElementCount置为0，不然会出错
                bucketElementCount[n] = 0;
            }
        }

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

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gleaming.cn/Ten-classic-sorting-algorithms/

更新于：Jul 28, 2022

排序

评论




Blog content follows the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License

载入天数...载入时分秒... Use Volantis as theme

Copyright © 2019-2022 XXX

鲁ICP备20003069号