# 排序算法

排序算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定	算法步骤简介
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定	相邻元素两两比较，逆序则交换；每轮把未排序最大值沉到末尾，优化版无交换提前退出
快速排序	O(nlogn)	O(nlogn)	O(n²)	O(logn)	不稳定	选基准，分区：小于基准放左、大于放右；递归排序左右子数组
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定	递归对半拆分数组至单个元素；再两两合并有序子数组，复制回原数组
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定	分为已排序、未排序两部分；依次取出未排序元素，向前找到位置插入
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定	每一轮在未排序区间找到最小值下标，和未排序区间首位交换，逐步确定有序部分
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定	构建最大堆；堆顶最大值与堆尾交换，堆大小减 1，剩余元素重新堆化，循环直到有序
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定	找到最值确定范围，统计元素出现次数；累加计数确定位置，反向遍历填充结果数组
希尔排序	O(n)	O(n¹·³)	O(n²)	O(1)	不稳定	设置递减步长分组，每组内部做插入排序；步长不断缩小至 1，最后一次普通插入排序
桶排序	O(n)	O(n+k)	O(n²)	O(n+k)	取决于桶内排序	根据映射函数将元素分到各个桶；桶内单独排序，最后按桶顺序依次取出元素
基数排序	O(n×k)	O(n×k)	O(n×k)	O(n+k)	稳定	k 为最大位数；从最低位到最高位，每一轮对当前数位执行稳定的计数排序

# 1.冒泡排序

# 介绍（两两比较）

冒泡排序（Bubble Sort）的核心思想非常简单：从头开始，不断比较相邻的两个元素，如果前者比后者大，就交换位置。 这样从头到尾完整地走一趟，最大的那个元素就必然会“沉”到队尾的最终位置。只需不断重复这个过程，每一轮都将当前未排序部分的最大值找出来送到末端，直到所有元素都排列整齐。因为在这个过程中较小的元素会像气泡一样逐渐“冒”到数组的前方，所以叫冒泡排序故得此名。

# 优点

代码简单，容易实现
适合小规模数据排序
对于几乎已经排好序的数据，效率较高
稳定的排序算法

# 缺点

时间复杂度高，为O(n²)
随着元素数量增加，效率急剧下降
每次只能将一个元素移动到其最终位置，效率不高

public static void optimizedBubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // 如果没有发生交换，说明数组已经有序，可以提前退出排序
        if (!swapped) {
            break;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 2.快速排序

# 介绍

快速排序（Quick Sort）是一种极其高效的分治排序算法，也是实际应用中最常用的排序算法之一。

它的核心思想可以概括为“选个基准，然后左右站队”：

选基准(pivot)：首先，从数组中任意选择一个元素作为“基准”。
站队：接着，重新排列数组，将所有小于基准的元素移动到基准的左边，所有大于等于基准的元素移动到右边。这一步完成后，该基准元素就找到了它在最终有序序列中的“最终位置”。
分而治之：最后，对基准左右两边的子数组（现在它们是两个独立的、更小的问题），递归地重复上述过程，直到每个子数组都排序完毕。

通过这种巧妙的“分而治之”策略，快速排序能将一个大问题不断分解成小问题来解决，平均时间复杂度能达到卓越的 O(nlogn)。

# 算法步骤（选左元素为基准分治递归）

从数列中选择一个元素作为"基准"，本文采用最左侧元素作为基准
将所有比基准值小的元素放到基准前面，所有比基准值大的元素放到基准后面（分区操作）
对基准左右两个子序列分别重复步骤1和2，直到子序列只有一个元素或为空

# 核心特性

分治策略：将问题分解为更小的子问题，逐步解决
原地排序：只需要 O(logn) 的额外空间复杂度（主要用于递归调用的栈空间）
时间复杂度：平均情况为 O(nlogn)，最坏情况为 O(n²)，最好情况为 O(nlogn)
不稳定性：相等元素的相对位置在排序后可能会改变
高效性：在实际应用中，快速排序通常是最快的排序算法之一

# 优缺点

# 优点

平均情况下非常高效，时间复杂度为 O(nlogn)
原地排序，空间复杂度低
缓存友好，数据局部性好
适合处理大规模数据
在许多实际应用中表现优秀

# 缺点

最坏情况下性能退化至 O(n²)，比如当数组已经排序时
不稳定的排序算法
对于小数组，快速排序可能比其他基础排序慢
递归实现可能导致栈溢出（可以使用迭代方式解决）

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 获取分区点位置
            int pivotIndex = partition(arr, low, high);

            // 递归排序左右子数组
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // 选择最左侧元素作为基准
        int pivot = arr[low];
        int i = low + 1;

        for (int j = low + 1; j <= high; j++) {
            // 将小于基准的元素移到左侧
            if (arr[j] < pivot) {
                // 交换元素
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }

        // 将基准元素放到正确位置
        int temp = arr[low];
        arr[low] = arr[i - 1];
        arr[i - 1] = temp;

        return i - 1;
    }

    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("排序前的数组：");
        printArray(arr);

        quickSort(arr, 0, arr.length - 1);

        System.out.println("排序后的数组：");
        printArray(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
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

# 3.归并排序

# 介绍

归并排序（Merge Sort）是一种高效且稳定的“分治”排序算法。其核心策略可以概括为“先递归拆分，再有序合并”。它会持续地将一个大数组对半切分，直到每个部分都只剩一个元素（此时天然有序）。接着，再反向地将这些相邻的有序部分两两配对，按大小顺序合并成一个更长的有序数组，不断重复此过程，直到最终还原成一个完整的有序序列。

归并排序的性能极其稳定，无论原始序列是好是坏，时间复杂度都保持在卓越的 O(nlogn)。与快速排序的“就地交换”不同，它通过“有序合并”实现排序，这一特性也保证了其排序的稳定性（相同元素的原始相对顺序在排序后不会改变），但通常需要额外的存储空间来辅助合并操作。

# 核心特性

分治策略：将问题分解为更小的子问题，再将子问题的解合并
稳定排序：相等元素的相对位置在排序后不会改变
时间复杂度：最好、最坏、平均情况均为 O(nlogn)
空间复杂度：需要 O(n) 的额外空间
非原地排序：需要额外空间来存储临时数组

# 算法步骤（先分割成小数组排序再合并成大数组）

将待排序数组递归地分割成两半，直到每个子数组只包含一个元素（此时认为子数组已排序）
递归地合并相邻的子数组，合并时比较两个子数组的元素，按顺序放入临时数组（核心）
将临时数组中的元素复制回原数组对应的位置
重复步骤2和3，直到所有子数组合并成一个完整的有序数组

# 优缺点

# 优点

时间复杂度稳定，在最好、最坏和平均情况下均为 O(nlogn)
稳定排序算法，保持相等元素的相对顺序
适合处理大规模数据，尤其是外部排序
可以改造为并行算法，提高效率

# 缺点

需要 O(n) 的额外空间
对于小规模数据，递归开销较大
不是原地排序算法，空间效率不如快速排序等
在一些情况下，常数因子较大，实际性能可能不如快速排序

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // 找出中间点
            int mid = left + (right - left) / 2;

            // 递归排序左右两半
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // 合并已排序的两半
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        // 计算两个子数组的大小
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 创建临时数组
        int[] L = new int[n1];
        int[] R = new int[n2];

        // 复制数据到临时数组
        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];

        // 合并临时数组
        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 复制L[]的剩余元素
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // 复制R[]的剩余元素
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前的数组：");
        printArray(arr);

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("排序后的数组：");
        printArray(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
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

# 4.插入排序

# 介绍

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作方式类似于我们打牌时的整理牌序，它将待排序序列分为两部分：已排序部分和未排序部分。算法不断地从未排序部分取出元素，然后插入到已排序部分的正确位置，直到所有元素都排序完毕。

# 算法步骤（每次选一个往前插）

将第一个元素视为已排序序列，其余元素视为未排序序列
从未排序序列中取出第一个元素，称为"待插入元素"
从已排序序列的末尾开始，依次与待插入元素比较
如果已排序序列中的元素大于待插入元素，则将该元素后移一位
重复步骤3和4，直到找到小于或等于待插入元素的位置
将待插入元素插入到该位置
重复步骤2至6，直到未排序序列为空

# 优缺点

# 优点

算法实现简单，容易理解
对于小规模数据或基本有序的数据效率较高
稳定的排序算法
适合增量式排序（可以一边插入元素一边保持有序）
对于接近有序的数组，时间复杂度接近O(n)

# 缺点

对于大规模乱序数组，时间复杂度为O(n²)，效率较低
需要较多的元素移动操作
不适合对倒序或接近倒序的数组进行排序

private static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++){
            // t是待插入的元素
            int t = arr[i];
            // j是已排序元素的索引
            int j = i - 1;
            while(j>=0 && arr[j]>t){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = t;
        }
        for (int i : arr){
            System.out.print(i+" ");
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 5.选择排序

# 介绍

选择排序是一种非常简单直观的排序算法，工作原理可以概括为“每次从未排序的队伍中，选出最优者，让它归位”。具体来说，算法在每一轮都会遍历所有还未排序的元素，从中找出最小（或最大）的一个，然后将其与未排序部分的第一个元素交换位置。这个操作能确保每一轮过后，都有一个元素被精准地放在它最终的正确位置上。接着，算法会缩小范围，在剩下的元素中重复这个“选择与交换”的过程，直到整个序列完全有序。

# 算法步骤（每次选最小的）

首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到未排序部分的起始位置
重复步骤2，直到所有元素均排序完毕

# 核心特性

稳定性：选择排序是不稳定的排序算法，它可能会改变相等元素的相对位置
原地排序：只需要常数级的额外空间
时间复杂度：最好、最坏和平均情况均为 O(n²)
比较排序：基于元素间的比较进行排序
交换次数少：最多进行 n-1 次交换，比冒泡排序的交换次数要少

# 优缺点

# 优点

实现简单，思路清晰
交换操作的次数比冒泡排序少，平均性能比冒泡排序好
对于小规模的数据效率还算可以
不占用额外内存空间

# 缺点

时间复杂度固定为 O(n²) ，无论输入数据如何都要扫描全部未处理的元素
不稳定的排序算法，可能会改变相同元素的相对位置
当数据量较大时，效率低下

public static void selectionSort(int[] arr) {
        int n = arr.length;

        // 遍历数组
        for (int i = 0; i < n - 1; i++) {
            // 找出从i到n-1中最小值的索引
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            if (i != minIndex) {
                // 将找到的最小值与当前位置i交换
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 6.堆排序

# 介绍

堆排序（Heap Sort）是一种高效的原地排序算法，它巧妙地利用了“堆”数据结构。其核心思想是首先将待排序的数组重构成一个最大堆（Max Heap）。在最大堆中，根节点（数组的第一个元素）始终是所有元素中的最大值。

构建好最大堆后，算法将堆顶的最大元素与堆末尾的元素交换，从而将当前的最大值放置到数组的正确最终位置。接着，将堆的大小减一，并对剩余的元素进行“堆化”调整，确保新的根节点仍然是剩余元素中的最大值。此过程不断重复——交换、缩小堆、重新堆化——直到所有元素都被放置到其最终的有序位置，完成整个排序。

堆（Heap）是一种特殊的完全二叉树结构，它的两个重要特性：

堆是一个完全二叉树，除了最底层外，其他层的节点都是满的，最底层的节点从左到右填充。

在最大堆中，每个节点的值都大于或等于其子节点的值；在最小堆中，每个节点的值都小于或等于其子节点的值。

堆的数组表示：

虽然堆是一种树结构，但是也可以用数组高效地表示，这是堆的一个重要特性。

对于数组中索引为 i 的节点：

其左子节点的索引为 2*i + 1

其右子节点的索引为 2*i + 2

这种表示方法非常紧凑，不需要使用额外的指针，充分利用了完全二叉树的性质。

# 算法步骤（堆排序后，堆顶元素与末尾交换）

将无序序列构建成一个最大堆
将堆顶元素（最大值）与堆的最后一个元素交换
剔除最后一个元素（已排序），将剩余元素重新构建为最大堆
重复步骤2和3，直到堆中只剩下一个元素

# 核心特性

堆数据结构：利用完全二叉树的性质，可以用数组高效表示
原地排序：只需要常数级的额外空间
时间复杂度：建堆时间为O(n)，排序时间为O(nlogn)，总体时间复杂度为O(nlogn)
不稳定性：相等元素的相对位置在排序后可能会改变
自适应性：对于部分有序或完全无序的数据，性能比较稳定

# 优缺点

# 优点

时间复杂度稳定，最好、最坏、平均情况均为O(nlogn)
原地排序，空间复杂度为O(1)
可以用于实现优先队列
适合处理大规模数据
不受输入数据分布影响，性能稳定

# 缺点

不是稳定的排序算法
在实际应用中，常数因子较大，可能比快速排序慢
对缓存不够友好，数据访问的局部性不好
实现复杂度较高，特别是构建堆的部分

package day01Sort.HeapSort;

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 逐个从堆顶取出元素
        for (int i = n - 1; i > 0; i--) {
            // 将当前堆顶（最大值）移到末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 对剩余元素重新构建最大堆
            heapify(arr, i, 0);
        }
    }

    // 调整以root为根的子树为最大堆
    private static void heapify(int[] arr, int n, int root) {
        int largest = root;      // 初始化最大值为根节点
        int left = 2 * root + 1; // 左子节点
        int right = 2 * root + 2; // 右子节点

        // 如果左子节点大于根节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 如果右子节点大于当前最大值
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 如果最大值不是根节点
        if (largest != root) {
            // 交换根节点和最大值
            int swap = arr[root];
            arr[root] = arr[largest];
            arr[largest] = swap;

            // 递归调整被影响的子树
            heapify(arr, n, largest);
        }
    }

    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前的数组：");
        printArray(arr);

        heapSort(arr);

        System.out.println("排序后的数组：");
        printArray(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
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
64
65
66
67
68
69
70
71

# 7.计数排序

# 介绍

计数排序（Counting Sort）是一种非比较型的排序算法，核心思想是通过统计元素出现的次数进行排序，利用数组的索引来确定元素的正确位置。

计数排序特别适合于已知范围不大的整数序列排序，其时间复杂度为 O(n+k)，其中 n 是待排序数组的长度，k 是整数的范围。当 k 不是很大时，计数排序可以实现线性时间排序，这是基于比较的排序算法（快速排序、归并排序等）无法达到的。

# 算法步骤（统计元素出现次数并记录位置）

找出待排序数组中的最大值和最小值，确定计数数组的大小
创建一个计数数组，统计每个元素出现的次数
对计数数组进行累加，得到每个元素在排序后数组中的位置
创建一个临时数组，从后向前扫描原数组，根据计数数组确定元素位置
将临时数组复制回原数组

# 核心特性

非比较排序：不通过比较元素大小进行排序
稳定排序：相等元素的相对位置在排序后不会改变
时间复杂度：O(n+k)，其中 k 是数据范围
空间复杂度：O(n+k)，需要额外空间存储计数数组和临时数组
适用范围：整数且范围较小的数据集

# 优缺点

# 优点

时间复杂度为 O(n+k)，当 k 不大时可以达到线性时间
稳定排序算法
适合对整数进行排序
不需要比较元素，对于范围小的数据集非常高效

# 缺点

只适用于整数排序
当数据范围 k 很大时，空间复杂度高
不适合对浮点数、字符串等进行排序（需要额外转换）
对于数据分布极不均匀的情况效率低下

public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 找出数组中的最大值和最小值
        int max = arr[0], min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }

        // 计算计数数组的大小
        int range = max - min + 1;

        // 创建计数数组并统计每个元素出现的次数
        int[] count = new int[range];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;
        }

        // 计算累加数组，确定每个元素在排序后的位置
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        // 创建临时数组存储排序结果
        int[] output = new int[arr.length];

        // 从后往前遍历原数组，保证排序的稳定性
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }

        // 将排序结果复制回原数组
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("排序前的数组：");
        printArray(arr);

        countingSort(arr);

        System.out.println("排序后的数组：");
        printArray(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
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
64
65
66

# 8.希尔排序

# 介绍

希尔排序（Shell Sort）是插入排序的一种改进版本，它是第一个突破O(n²)的排序算法，核心思想是利用步长序列对数据进行分组，在每个分组内使用插入排序，逐步减小步长直到为1，完成最终排序。

希尔排序时元素会大跨度移动，解决了插入排序在处理大规模乱序数组效率低下的问题，让元素更快移动到正确位置。虽然说后来出现了更高效的排序算法，但是希尔排序凭借其简单性和在中等规模数据上的良好表现，仍然是实际应用中的重要排序算法。

# 算法步骤（按步长分组插入排序）

选择一个步长序列，建议初始步长 n/2，每次减半直到步长为1
对每个步长，对数组进行分组，对应位置相隔为步长的元素视为一组
对每一组使用插入排序进行排序
减小步长，重复步骤2和3，直到步长减少到1
当步长为1时，相当于对整个数组做一次插入排序，此时数组已基本有序，所需的比较和移动次数大大减少

为了帮助大家更好的理解，我们以初始数组 [8, 9, 1, 7, 2, 6, 3, 5, 4] 为例，查看每一步的详细流程：

1）第一轮排序

选择间隔 (Gap): 4 (数组长度9除以2取整)
分组: 按照间隔4将数组分为4个子序列。
- 第1组 (下标0, 4, 8): [8, 2, 4]
- 第2组 (下标1, 5): [9, 6]
- 第3组 (下标2, 6): [1, 3]
- 第4组 (下标3, 7): [7, 5]
对每组进行插入排序:
- [8, 2, 4] 排序后变为 [2, 4, 8]
- [9, 6] 排序后变为 [6, 9]
- [1, 3] 排序后变为 [1, 3]
- [7, 5] 排序后变为 [5, 7]
本轮结果: 将排序后的元素放回原位置，数组变为 [2, 6, 1, 5, 4, 9, 3, 7, 8]。

2）第二轮排序

缩小间隔 (Gap): 2 (上一间隔4除以2)
分组: 此时基于新数组 [2, 6, 1, 5, 4, 9, 3, 7, 8]，按照间隔2分为2个子序列。
- 第1组 (偶数下标): [2, 1, 4, 3, 8]
- 第2组 (奇数下标): [6, 5, 9, 7]
对每组进行插入排序:
- [2, 1, 4, 3, 8] 排序后变为 [1, 2, 3, 4, 8]
- [6, 5, 9, 7] 排序后变为 [5, 6, 7, 9]
本轮结果: 将元素放回原位置，数组变为 [1, 5, 2, 6, 3, 7, 4, 9, 8]。此时数组已经比之前更加有序。

3）第三轮排序（最终轮）

缩小间隔 (Gap): 1。
操作: 当间隔为1时，希尔排序就等同于对整个数组进行一次普通插入排序。
排序过程: 对 [1, 5, 2, 6, 3, 7, 4, 9, 8] 进行插入排序。由于数组已基本有序，这次排序的效率非常高。
最终排序结果: 数组变为完全有序的 [1, 2, 3, 4, 5, 6, 7, 8, 9]。

# 核心特性

递减步长序列：初始较大步长让元素大幅度移动，后续减小步长微调元素位置
分组插入排序：对每个步长形成的分组独立应用插入排序
时间复杂度：取决于步长序列，一般在O(n1.3)到O(n2)之间
不稳定性：相等元素的相对位置在排序后可能会改变
适应性：对于中等大小的数组表现良好

# 优缺点

# 优点

比插入排序更高效，尤其是对于大规模乱序数组
代码简单，容易实现
在中等大小的数组中性能良好
对于几乎已排序的数据效率很高
不需要额外的空间（原地排序）

# 缺点

不是稳定的排序算法
步长序列的选择对性能影响很大
时间复杂度分析复杂，依赖于所选的步长序列
对于非常大的数据集，其他高级排序算法（如快速排序、堆排序）可能更高效
对于非常小的数据集，简单的插入排序可能更高效

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        
        // 初始步长为n/2，每次减半
        for (int gap = n/2; gap > 0; gap /= 2) {
            // 对每个步长进行插入排序
            for (int i = gap; i < n; i++) {
                // 保存当前元素
                int temp = arr[i];
                int j;
                
                // 对同一组的元素进行插入排序
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                
                // 将temp放到正确位置
                arr[j] = temp;
            }
        }
    }
    
    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3, 1, 23, 45, 19, 92};
        System.out.println("排序前的数组：");
        printArray(arr);
        
        shellSort(arr);
        
        System.out.println("排序后的数组：");
        printArray(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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 9.桶排序

# 介绍

桶排序（Bucket Sort）是一种分布式排序算法，核心思想是将数据分散到有限数量的桶中，然后对每个桶中的数据进行排序，最后将各个桶中的数据有序地合并起来。桶排序是计数排序的扩展版本，特别适合均匀分布的数据集。

桶排序的效率取决于数据分布的均匀性。在最佳情况下，桶排序的时间复杂度可以达到 O(n)，在特定场景下非常高效。桶排序结合了哈希表的思想，通过映射函数将元素分配到不同的桶中实现排序。

# 算法步骤（按照规定范围放入桶、排序、拿出）

确定桶的数量和范围，创建对应数量的桶（通常是数组或链表）
根据映射函数将每个元素分配到对应的桶中
对每个桶内的元素分别进行排序（可以使用任何排序算法）
按照桶的顺序将各个桶中的元素依次取出，组成有序序列

# 核心特性

分布式排序：将元素分散到多个桶中进行局部排序
映射函数：需要一个合理的映射函数决定元素与桶的对应关系
时间复杂度：平均情况为 O(n+k)，其中 k 是桶的数量，最坏情况为 O(n²)
空间复杂度：O(n+k)，需要额外空间存储桶和临时数据
稳定性：取决于桶内排序使用的算法，如果使用稳定的排序算法那么桶排序也是稳定的

# 优缺点

# 优点

当数据分布均匀时，时间复杂度接近 O(n)，非常高效
适合外部排序，可以有效处理大规模数据
可以与其他排序算法结合使用
适合对浮点数进行排序
适合并行化实现

# 缺点

对数据分布敏感，最坏情况下可能退化到 O(n²)
需要额外的空间存储桶
桶的数量和映射函数选择对性能影响很大
对于非均匀分布的数据，可能导致某些桶过大，效率下降
需要知道数据的大致分布情况才能设计最优的桶数量

public class BucketSort {
    public static void bucketSort(double[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        // 确定桶的数量
        int bucketCount = arr.length;
        
        // 创建桶
        List<List<Double>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        
        // 找出数组中的最大值和最小值
        double max = arr[0], min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        
        // 计算每个桶的范围大小
        double range = (max - min) / bucketCount;
        
        // 将元素分配到对应的桶中
        for (double item : arr) {
            // 计算元素应该放入哪个桶
            int bucketIndex = (int)((item - min) / range);
            
            // 处理最大值的边界情况
            if (bucketIndex == bucketCount) {
                bucketIndex--;
            }
            
            buckets.get(bucketIndex).add(item);
        }
        
        // 对每个桶中的元素进行排序
        for (List<Double> bucket : buckets) {
            Collections.sort(bucket);
        }
        
        // 将桶中排序好的元素放回原数组
        int index = 0;
        for (List<Double> bucket : buckets) {
            for (double item : bucket) {
                arr[index++] = item;
            }
        }
    }
    
    // 打印数组
    public static void printArray(double[] arr) {
        for (double item : arr) {
            System.out.print(item + " ");
        }
        System.out.println();
    }
    
    // 测试
    public static void main(String[] args) {
        double[] arr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
        System.out.println("排序前的数组：");
        printArray(arr);
        
        bucketSort(arr);
        
        System.out.println("排序后的数组：");
        printArray(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
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77

# 10.基数排序

# 介绍

基数排序（Radix Sort）是一种非比较型的排序算法，核心思想是按照数位来排序，从最低有效位（Least Significant Digit, LSD）或最高有效位（Most Significant Digit, MSD）开始，依次对每个位置的数字进行排序。基数排序特别适合用于整数或定长字符串的排序，时间复杂度是 O(n×k)，其中 n 是待排序数组的长度，k 是数据的最大位数。

基数排序不会直接比较元素之间的大小，通过分配和收集过程实现排序，在一些特定场景下性能优于比较排序算法。

# 算法步骤（每一位都排序一次）

找出待排序数组中的最大值，确定最大位数
从最低位开始，对每一位上的数字进行计数排序（或桶排序）
按照当前位的数字大小将元素重新排列
对下一个更高位重复步骤2和3，直到处理完所有位

# 优缺点

# 优点

在固定位数的情况下，时间复杂度可达到 O(n)，比比较排序更快
稳定排序算法，能保持相等元素的相对顺序
适合处理大量数据和长整数
不受输入数据分布影响，排序性能稳定
适合处理位数相同的字符串

# 缺点

只适用于整数和定长字符串等可以分解为独立"位"的数据
需要额外的空间进行计数和输出
如果数据最大值很大，但数据量很小，会导致很多不必要的空桶操作
对负数需要特殊处理
不适合对浮点数直接进行排序（需要特殊转换）

public class RadixSort {
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        // 找出最大值，确定最大位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        
        // 对每一位进行计数排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }
    
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 输出数组
        int[] count = new int[10]; // 计数数组，默认为10，因为一位数字的范围是0~9
        
        // 统计当前位上每个数字出现的次数
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }
        
        // 计算累加数组，确定每个数字在输出数组中的位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        
        // 构建输出数组，从后向前遍历以保持稳定性
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }
        
        // 将排序好的数组复制回原数组
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
    
    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("排序前的数组：");
        printArray(arr);
        
        radixSort(arr);
        
        System.out.println("排序后的数组：");
        printArray(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
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
64
65
66
67
68
69
70