常见排序算法

1. 冒泡排序

1.1 原理

重复遍历数组，比较相邻元素。如果前一个元素大于后一个元素，则交换它们。每轮遍历会将当前未排序部分的最大值"冒泡"到末尾。

1.2 特点

• 稳定性：稳定（相同元素顺序不变）
• 原地排序：仅需常量级额外空间
• 实现简单，但效率低
• 适用于小规模数据

1.3 复杂度

• 时间复杂度：
  • 最优：O(n)（已有序时）
  • 最差：O(n²)
  • 平均：O(n²)
• 空间复杂度：O(1)

1.4 java代码

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;  // 优化：检查是否发生交换
        for (int j = 0; j < n - 1 - i; 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;  // 未交换说明已有序
    }
}

2. 选择排序

2.1 原理

将数组分为已排序和未排序两部分。每轮从未排序部分选出最小值，与未排序部分的第一个元素交换。

2.2 特点

• 稳定性：不稳定（如 [5, 5, 2] 会破坏顺序）
• 原地排序：仅需常量级空间
• 交换次数少（O(n)次交换）

2.3 复杂度

• 时间复杂度：始终 O(n²)（无最优/最差区分）
• 空间复杂度：O(1)

2.4 java代码

public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        // 寻找未排序部分的最小值索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 将最小值交换到已排序末尾
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

3. 插入排序

3.1 原理

将数组分为已排序和未排序两部分。每轮取未排序部分的第一个元素，在已排序部分中从后向前扫描，找到合适位置插入。

3.2 特点

• 稳定性：稳定
• 原地排序：仅需常量级空间
• 对小规模或基本有序数据效率高

3.3 复杂度

• 时间复杂度：
  • 最优：O(n)（已有序时）
  • 最差：O(n²)
  • 平均：O(n²)
• 空间复杂度：O(1)

3.4 java代码

public void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 待插入元素
        int j = i - 1;
        // 将比key大的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;  // 插入到正确位置
    }
}

4. 希尔排序

4.1 原理

改进的插入排序。通过将数组按增量序列分组（如 n/2, n/4, ...），对每组进行插入排序，逐步缩小增量至1。

4.2 特点

• 稳定性：不稳定（分组破坏顺序）
• 原地排序：仅需常量级空间
• 效率高于简单插入排序

4.3 复杂度

• 时间复杂度：
  • 取决于增量序列
  • 平均：O(n log² n) 或 O(n^(3/2))
• 空间复杂度：O(1)

4.4 java代码

public void shellSort(int[] arr) {
    int n = arr.length;
    // 初始增量gap=n/2，逐步缩小
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个分组进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            // 组内插入排序
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

5. 快速排序

5.1 原理

采用分治法：

1. 选择基准元素（pivot）
2. 分区：将小于pivot的元素移到左侧，大于的移到右侧
3. 递归排序左右子数组

5.2 特点

• 稳定性：不稳定
• 原地排序：递归栈空间 O(log n)
• 实际应用中最快的排序算法之一

5.3 复杂度

• 时间复杂度：
  • 最优：O(n log n)（每次分区平衡）
  • 最差：O(n²)（已有序时）
  • 平均：O(n log n)
• 空间复杂度：O(log n)（递归栈）

5.4 java代码

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 获取分区点
        quickSort(arr, low, pi - 1);         // 递归左子数组
        quickSort(arr, pi + 1, high);         // 递归右子数组
    }
}

private int partition(int[] arr, int low, int high) {
    int pivot = arr[high];  // 选择末尾元素为基准
    int i = low - 1;         // 小于pivot的边界指针
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // 交换元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将pivot放到正确位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

6. 归并排序

6.1 原理

采用 分治法（Divide and Conquer）：

1. 分：将数组递归拆分成两半，直到子数组长度为1（天然有序）。
2. 治：合并两个有序子数组。比较两个子数组的元素，按顺序放入临时数组，最后拷贝回原数组。

6.2 特点

• 稳定性：稳定（相同元素顺序不变）
• 空间占用：需要额外O(n)空间
• 适用场景：链表排序、外部排序（大数据量）

6.3 复杂度

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)

6.4 java代码

public class MergeSort {
    public void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        mergeSort(arr, 0, arr.length - 1);
    }

    private void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);      // 递归左半部分
        mergeSort(arr, mid + 1, right); // 递归右半部分
        merge(arr, left, mid, right);    // 合并有序数组
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        // 比较两个子数组元素
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }

        // 处理剩余元素
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        // 拷贝回原数组
        System.arraycopy(temp, 0, arr, left, temp.length);
    }
}

7. 堆排序

7.1 原理

基于 二叉堆（完全二叉树）：

1. 建堆：将数组视为完全二叉树，从最后一个非叶子节点开始调整成大顶堆（父节点 ≥ 子节点）。
2. 排序：交换堆顶（最大值）与末尾元素，缩小堆范围，重新调整堆结构。重复直到堆为空。

7.2 特点

• 稳定性：不稳定（交换可能破坏顺序）
• 空间占用：原地排序（O(1)额外空间）
• 适用场景：TopK问题、实时排序

7.3 复杂度

• 时间复杂度：O(n log n)
• 空间复杂度：O(1)

7.4 java代码

public class HeapSort {
    public void sort(int[] arr) {
        // 1. 构建大顶堆（从最后一个非叶子节点开始）
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }

        // 2. 交换堆顶与末尾元素 + 调整堆
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);           // 交换堆顶和末尾
            heapify(arr, i, 0);        // 调整剩余堆
        }
    }

    private void heapify(int[] arr, int n, int i) {
        int largest = i;       // 假设当前节点最大
        int left = 2 * i + 1;  // 左子节点
        int right = 2 * i + 2; // 右子节点

        // 比较左子节点
        if (left < n && arr[left] > arr[largest]) largest = left;
        // 比较右子节点
        if (right < n && arr[right] > arr[largest]) largest = right;

        // 若最大值不是当前节点，则交换并递归调整
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

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

8. 计数排序

8.1 原理

非比较排序，适用于整数：

1. 统计频次：遍历数组，统计每个元素出现次数。
2. 累加计数：计算每个元素在有序数组中的最后位置。
3. 反向填充：从原数组末尾开始，根据计数数组确定元素位置。

8.2 特点

• 稳定性：稳定（反向填充保证）
• 限制：仅适用于整数且范围较小（k为最大值）
• 优势：速度快于O(n log n)的排序

8.3 复杂度

• 时间复杂度：O(n + k)（k为数据范围）
• 空间复杂度：O(n + k)

8.4 java代码

public class CountingSort {
    public void sort(int[] arr) {
        if (arr.length == 0) return;

        // 1. 找到最大值
        int max = arr[0];
        for (int num : arr) if (num > max) max = num;

        // 2. 创建计数数组
        int[] count = new int[max + 1];
        for (int num : arr) count[num]++;

        // 3. 累加计数（确定元素最终位置）
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }

        // 4. 反向填充结果数组
        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            output[count[num] - 1] = num; // 位置=计数-1
            count[num]--; // 更新计数
        }

        // 拷贝回原数组
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

9. 桶排序

9.1 原理

分桶 + 子排序：

1. 分桶：根据范围将元素分配到多个桶中。
2. 桶内排序：每个桶使用其他排序算法（如插入排序）。
3. 合并结果：按桶顺序合并所有元素。

9.2 特点

• 稳定性：取决于桶内排序算法
• 性能关键：数据均匀分布时效率最高
• 适用场景：均匀分布的浮点数排序

9.3 复杂度

• 时间复杂度：
  • 平均：O(n + k)（k为桶数）
  • 最坏：O(n²)（所有元素集中在一个桶）
• 空间复杂度：O(n + k)

9.4 java代码

import java.util.*;

public class BucketSort {
    public void sort(double[] arr) {
        int n = arr.length;
        // 1. 初始化桶（链表实现）
        List<Double>[] buckets = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 2. 元素分桶（桶数=数组长度）
        for (double num : arr) {
            int bucketIdx = (int) (num * n); // 适用于[0,1)的浮点数
            buckets[bucketIdx].add(num);
        }

        // 3. 每个桶内排序（使用Collections.sort）
        for (List<Double> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 4. 合并所有桶
        int idx = 0;
        for (List<Double> bucket : buckets) {
            for (double num : bucket) {
                arr[idx++] = num;
            }
        }
    }
}

10. 基数排序

10.1 原理

按位排序（从低位到高位）：

1. 准备：确定最大数字的位数（d）。
2. 按位排序：从最低位（个位）到最高位，每次使用稳定排序（通常用计数排序）。
3. 合并结果：每一轮排序后，数组按当前位有序。

10.2 特点

• 稳定性：稳定（依赖底层排序）
• 限制：仅适用于整数或定长字符串
• 优势：比快速排序稳定，适合大范围整数

10.3 复杂度

• 时间复杂度：O(d·(n + k))（d为位数，k为基数）
• 空间复杂度：O(n + k)

10.4 java代码

public class RadixSort {
    public void sort(int[] arr) {
        if (arr.length == 0) return;

        // 1. 找到最大值（确定位数）
        int max = Arrays.stream(arr).max().getAsInt();

        // 2. 从个位开始，按每一位计数排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    // 基于某一位的计数排序
    private void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // 0~9的计数器

        // 统计当前位的出现次数
        for (int num : arr) {
            int digit = (num / 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]--;
        }

        // 拷贝回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }
}

11. 总结

以下是10种排序算法的比较表格，涵盖最佳场景、稳定性、时间复杂度（最佳/最坏/平均）和空间复杂度：

排序算法	最佳场景	稳定性	时间复杂度（最佳）	时间复杂度（最坏）	时间复杂度（平均）	空间复杂度
冒泡排序	输入序列基本有序	稳定	O(n)	O(n²)	O(n²)	O(1)
选择排序	无特定最佳场景	不稳定	O(n²)	O(n²)	O(n²)	O(1)
插入排序	输入序列基本有序	稳定	O(n)	O(n²)	O(n²)	O(1)
希尔排序	中等规模数据	不稳定	O(n log n)	O(n²)	O(n log n) ~ O(n²)	O(1)
快速排序	每次划分后子数组均衡	不稳定	O(n log n)	O(n²)	O(n log n)	O(log n)（递归栈）
归并排序	无特定最佳场景	稳定	O(n log n)	O(n log n)	O(n log n)	O(n)（辅助数组）
堆排序	无特定最佳场景	不稳定	O(n log n)	O(n log n)	O(n log n)	O(1)
计数排序	数据范围小（如0~100）	稳定	O(n + k)	O(n + k)	O(n + k)	O(n + k)（k为范围）
桶排序	数据均匀分布	稳定	O(n + k)	O(n²)	O(n + k)	O(n + m)（m为桶数）
基数排序	数据为整数或字符串，位数少	稳定	O(d(n + k))	O(d(n + k))	O(d(n + k))	O(n + k)（k为基数）