Java 经典排序算法学习笔记
·
概述
排序算法是将一组数据按照指定顺序（升序 / 降序）重新排列的算法，核心评价维度：
| 评价维度 | 说明 |
|---|---|
| 时间复杂度 | 最好 / 最坏 / 平均情况下的执行效率（O (1) < O (logn) < O (n) < O (nlogn) < O (n²)） |
| 空间复杂度 | 算法执行过程中额外占用的内存空间（原地排序：O (1)，非原地：O (n)/O (logn)） |
| 稳定性 | 排序后，相等值元素的相对位置是否保持不变（稳定：是，不稳定：否） |
| 适用性 | 适合的数据集规模、数据分布特点 |
一、冒泡排序（Bubble Sort）
1.1 算法原理
- 核心思想：重复遍历数组，每次比较相邻元素，若顺序错误则交换，直到没有交换发生（像气泡逐渐上浮）。
- 优化点：设置标志位，若某一轮无交换，说明数组已有序，直接退出。
1.2 核心代码
public class BubbleSort {
// 升序排序
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 外层循环：控制排序轮数（最多 n-1 轮）
for (int i = 0; i < n - 1; i++) {
boolean swapped = false; // 标记是否发生交换
// 内层循环：每轮比较到 n-1-i 位置（后 i 个元素已排好）
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;
}
}
// 测试
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // 输出：[1, 1, 2, 3, 4, 5, 6, 9]
}
}1.3 性能分析
- 时间复杂度：最好 O (n)（已有序）、最坏 O (n²)（逆序）、平均 O (n²)
- 空间复杂度：O (1)（原地排序）
- 稳定性：稳定（相等元素不交换）
- 适用场景：小规模数据、基本有序的数据
二、选择排序（Selection Sort）
2.1 算法原理
- 核心思想：将数组分为「已排序区」和「未排序区」，每轮从未排序区找到最小（大）值，放到已排序区末尾。
2.2 核心代码
public class SelectionSort {
public static void selectionSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 外层循环：已排序区边界（0 ~ i-1 已排序）
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;
}
}
// 交换最小值到已排序区末尾
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
selectionSort(arr);
System.out.println(Arrays.toString(arr)); // 输出：[1, 1, 2, 3, 4, 5, 6, 9]
}
}2.3 性能分析
- 时间复杂度：最好 / 最坏 / 平均 O (n²)（无论数据是否有序，都要遍历找最小值）
- 空间复杂度：O (1)（原地排序）
- 稳定性：不稳定（例如 [2, 2, 1]，第一轮交换后第一个 2 会到最后）
- 适用场景：小规模数据，对稳定性无要求的场景
三、插入排序（Insertion Sort）
3.1 算法原理
- 核心思想：将数组分为「已排序区」和「未排序区」，每轮取未排序区第一个元素，插入到已排序区的合适位置（像整理扑克牌）。
- 优化点：折半插入（减少比较次数）、希尔排序（分组插入）。
3.2 核心代码
public class InsertionSort {
public static void insertionSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 外层循环：未排序区第一个元素（0 位置默认已排序）
for (int i = 1; i < n; i++) {
int temp = arr[i]; // 待插入元素
int j = i - 1; // 已排序区末尾索引
// 内层循环：找插入位置（已排序区元素后移）
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j]; // 元素后移
j--;
}
// 插入元素到合适位置
arr[j + 1] = temp;
}
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
insertionSort(arr);
System.out.println(Arrays.toString(arr)); // 输出：[1, 1, 2, 3, 4, 5, 6, 9]
}
}3.3 性能分析
- 时间复杂度：最好 O (n)（已有序）、最坏 O (n²)（逆序）、平均 O (n²)
- 空间复杂度：O (1)（原地排序）
- 稳定性：稳定（相等元素插入到后方，不改变相对位置）
- 适用场景：小规模数据、基本有序的数据（比冒泡 / 选择排序效率高）
四、希尔排序（Shell Sort）
4.1 算法原理
- 核心思想：插入排序的优化版，将数组按「步长 gap」分组，对每组进行插入排序；逐步缩小 gap 到 1，最终完成整体排序（gap 通常取 n/2、n/4...1）。
- 优势：减少插入排序的元素移动次数，适合中等规模数据。
4.2 核心代码
public class ShellSort {
public static void shellSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 步长 gap 逐步缩小
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每组进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
// 组内元素比较（步长 gap）
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
shellSort(arr);
System.out.println(Arrays.toString(arr)); // 输出：[1, 1, 2, 3, 4, 5, 6, 9]
}
}4.3 性能分析
- 时间复杂度：取决于 gap 序列，平均约 O (n^1.3)（优于 O (n²)）、最坏 O (n²)
- 空间复杂度：O (1)（原地排序）
- 稳定性：不稳定（分组排序会打乱相等元素的相对位置）
- 适用场景：中等规模数据（比插入排序效率高）
五、快速排序（Quick Sort）
5.1 算法原理
- 核心思想：分治思想，选择一个「基准值 pivot」，将数组分为「小于 pivot」「等于 pivot」「大于 pivot」三部分，递归排序左右两部分。
- 优化点：
- 基准值选择：三数取中法（左、中、右取中间值），避免极端数据（如已排序数组）导致性能退化；
- 小规模数据：递归到一定深度后改用插入排序；
- 三路快排：处理大量重复元素的场景。
5.2 核心代码（经典快排 + 三数取中优化）
public class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
quickSort(arr, 0, arr.length - 1);
}
// 递归排序 [left, right] 区间
private static void quickSort(int[] arr, int left, int right) {
// 小规模数据改用插入排序（优化）
if (right - left <= 10) {
insertionSort(arr, left, right);
return;
}
// 三数取中选基准值
int pivotIndex = medianOfThree(arr, left, right);
// 将基准值交换到 left 位置
swap(arr, left, pivotIndex);
int pivot = arr[left];
// 分区：[left+1, i) <= pivot，(j, right] >= pivot
int i = left + 1, j = right;
while (true) {
// 找大于 pivot 的元素
while (i <= j && arr[i] < pivot) i++;
// 找小于 pivot 的元素
while (i <= j && arr[j] > pivot) j--;
if (i >= j) break;
// 交换元素
swap(arr, i, j);
i++;
j--;
}
// 将基准值放到正确位置（j 是小于 pivot 的最后一个元素）
swap(arr, left, j);
// 递归排序左右区间
quickSort(arr, left, j - 1);
quickSort(arr, j + 1, right);
}
// 三数取中：返回 left、mid、right 中中间值的索引
private static int medianOfThree(int[] arr, int left, int right) {
int mid = left + (right - left) / 2;
if (arr[left] > arr[mid]) swap(arr, left, mid);
if (arr[left] > arr[right]) swap(arr, left, right);
if (arr[mid] > arr[right]) swap(arr, mid, right);
return mid; // 中间值放到 mid 位置，返回 mid
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 局部插入排序（[left, right] 区间）
private static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= left && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
quickSort(arr);
System.out.println(Arrays.toString(arr)); // 输出：[1, 1, 2, 3, 4, 5, 6, 9]
}
}5.3 性能分析
- 时间复杂度：最好 / 平均 O (nlogn)、最坏 O (n²)（已排序数组，优化后可避免）
- 空间复杂度：O (logn)（递归调用栈，最坏 O (n)）
- 稳定性：不稳定（分区交换会打乱相等元素位置）
- 适用场景：大规模数据（工业界最常用的排序算法）
六、归并排序（Merge Sort）
6.1 算法原理
- 核心思想：分治思想，将数组递归拆分为两半，分别排序后再合并为一个有序数组。
- 特点：稳定排序，不受数据分布影响，时间复杂度稳定 O (nlogn)。
6.2 核心代码
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
// 辅助数组（避免频繁创建）
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
}
// 递归拆分 [left, right] 区间
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left >= right) return;
int mid = left + (right - left) / 2;
// 拆分左半区
mergeSort(arr, left, mid, temp);
// 拆分右半区
mergeSort(arr, mid + 1, right, temp);
// 合并两个有序区
merge(arr, left, mid, right, temp);
}
// 合并 [left, mid] 和 [mid+1, right] 两个有序数组
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 左半区指针
int j = mid + 1;// 右半区指针
int k = left; // 辅助数组指针
// 合并两个有序数组到 temp
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++];
}
// 将 temp 中有序数据复制回原数组
for (k = left; k <= right; k++) {
arr[k] = temp[k];
}
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
mergeSort(arr);
System.out.println(Arrays.toString(arr)); // 输出：[1, 1, 2, 3, 4, 5, 6, 9]
}
}6.3 性能分析
- 时间复杂度：最好 / 最坏 / 平均 O (nlogn)（稳定）
- 空间复杂度：O (n)（需要辅助数组，非原地排序）
- 稳定性：稳定（合并时相等元素优先取左半区）
- 适用场景：大规模数据、对稳定性有要求的场景
七、堆排序（Heap Sort）
7.1 算法原理
- 核心思想：利用「堆」这种数据结构（完全二叉树），先构建大顶堆（升序），再依次将堆顶（最大值）交换到数组末尾，调整剩余元素为大顶堆，直到排序完成。
- 堆的性质：大顶堆 - 父节点值 ≥ 子节点值；小顶堆 - 父节点值 ≤ 子节点值。
7.2 核心代码
public class HeapSort {
public static void heapSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 1. 构建大顶堆（从最后一个非叶子节点开始调整）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 2. 依次取出堆顶元素（最大值）放到数组末尾
for (int i = n - 1; i > 0; i--) {
// 交换堆顶（arr[0]）和当前未排序区末尾（arr[i]）
swap(arr, 0, i);
// 调整剩余元素为大顶堆（堆大小变为 i）
heapify(arr, i, 0);
}
}
// 调整以 i 为根的子树为大顶堆（堆大小为 heapSize）
private static void heapify(int[] arr, int heapSize, int i) {
int largest = i; // 最大值索引（初始为根）
int left = 2 * i + 1; // 左子节点索引
int right = 2 * i + 2; // 右子节点索引
// 比较左子节点
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
// 比较右子节点
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
// 最大值不是根节点，交换并递归调整
if (largest != i) {
swap(arr, i, largest);
heapify(arr, heapSize, largest);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
heapSort(arr);
System.out.println(Arrays.toString(arr)); // 输出：[1, 1, 2, 3, 4, 5, 6, 9]
}
}7.3 性能分析
- 时间复杂度：最好 / 最坏 / 平均 O (nlogn)（建堆 O (n)，调整堆 O (nlogn)）
- 空间复杂度：O (1)（原地排序）
- 稳定性：不稳定（堆调整会打乱相等元素位置）
- 适用场景：大规模数据、需要原地排序的场景
八、计数排序（Counting Sort）
8.1 算法原理
- 核心思想：非比较排序，利用数组下标作为「计数器」，统计每个值出现的次数，再根据计数器重构有序数组。
- 前提：数据范围已知且较小（如 0~100、-50~50）。
8.2 核心代码
public class CountingSort {
public static void countingSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
// 1. 找数组的最大值和最小值（确定计数器范围）
int min = arr[0], max = arr[0];
for (int num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
// 2. 创建计数器数组（偏移量：min，避免负数下标）
int[] count = new int[max - min + 1];
// 统计每个数出现的次数
for (int num : arr) {
count[num - min]++;
}
// 3. 重构有序数组
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i + min;
count[i]--;
}
}
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
countingSort(arr);
System.out.println(Arrays.toString(arr)); // 输出：[1, 1, 2, 3, 4, 5, 6, 9]
}
}
8.3 性能分析
- 时间复杂度：O (n + k)（n 是数据量，k 是数据范围）
- 空间复杂度：O (k)（计数器数组）
- 稳定性：可实现稳定（优化计数器为前缀和）
- 适用场景：数据范围小、整数类型的大规模数据（如成绩排序、年龄排序）
九、所有排序算法对比总结
| 算法 | 时间复杂度（平均） | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 稳定 | 小规模、基本有序数据 |
| 选择排序 | O(n²) | O(1) | 不稳定 | 小规模、对稳定性无要求 |
| 插入排序 | O(n²) | O(1) | 稳定 | 小规模、基本有序数据（推荐） |
| 希尔排序 | O(n^1.3) | O(1) | 不稳定 | 中等规模数据 |
| 快速排序 | O(nlogn) | O(logn) | 不稳定 | 大规模数据（工业界首选） |
| 归并排序 | O(nlogn) | O(n) | 稳定 | 大规模、要求稳定的场景 |
| 堆排序 | O(nlogn) | O(1) | 不稳定 | 大规模、原地排序的场景 |
| 计数排序 | O(n + k) | O(k) | 稳定 | 数据范围小的整数排序 |
总结
- 复杂度优先级：小规模数据选 O (n²) 算法（插入排序最优），大规模数据选 O (nlogn) 算法（快速排序最优，需稳定选归并排序），整数且范围小选计数排序。
- 稳定性：冒泡、插入、归并、计数排序是稳定的；选择、希尔、快速、堆排序是不稳定的。
- 核心思想：
- 简单排序（冒泡 / 选择 / 插入）：分已排序 / 未排序区，逐轮处理；
- 高级排序（快排 / 归并）：分治思想，拆分后处理再合并；
- 堆排序：利用堆的特性选最值；
- 计数排序：非比较排序，利用下标统计。
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
2
0- 0
已为社区贡献5条内容
所有评论(0)