一、八大排序算法总览
| 排序算法 | 类型 | 稳定性 | 平均时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | 交换 | 稳定 | O(n²) | O(1) |
| 选择排序 | 选择 | 不稳定 | O(n²) | O(1) |
| 插入排序 | 插入 | 稳定 | O(n²) | O(1) |
| 希尔排序 | 插入 | 不稳定 | O(n^1.3) | O(1) |
| 归并排序 | 归并 | 稳定 | O(n log n) | O(n) |
| 快速排序 | 交换 | 不稳定 | O(n log n) | O(log n) |
| 堆排序 | 选择 | 不稳定 | O(n log n) | O(1) |
| 基数排序 | 分配 | 稳定 | O(n·k) | O(n+k) |
二、冒泡排序（Bubble Sort）
1. 思想
像水中的气泡一样，大的数不断“浮”到后面。
每一趟比较相邻元素
大的往后放
一趟结束，最大值到末尾
2. Java 实现
public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { boolean flag = false; 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; flag = true; } } if (!flag) break; // 优化：已排好序 } }3. 特点
✅ 稳定
❌ 慢，只适合理解思想
三、选择排序（Selection Sort）
1. 思想
每一轮选择一个最小值，放到前面。
2. Java 实现
public static void selectionSort(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[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }3. 特点
❌ 不稳定
❌ 比较次数固定
四、插入排序（Insertion Sort）
1. 思想
像打牌一样，把当前数插入到已排好序的部分。
2. Java 实现
public static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int current = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > current) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = current; } }3. 特点
✅ 稳定
✅ 小规模 / 基本有序非常快
五、希尔排序（Shell Sort）
1. 思想
插入排序的升级版，先分组，再插入。
2. Java 实现
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 temp = arr[i]; int j = i; while (j - gap >= 0 && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }六、归并排序（Merge Sort）
1. 思想
分而治之：
拆分数组
排序子数组
合并有序数组
2. Java 实现（核心）
public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } }七、快速排序（Quick Sort）⭐
1. 思想
选一个基准值，比它小的放左边，大的放右边。
2. Java 实现
public static void quickSort(int[] arr, int left, int right) { if (left >= right) return; int pivot = arr[left]; int l = left, r = right; while (l < r) { while (l < r && arr[r] >= pivot) r--; arr[l] = arr[r]; while (l < r && arr[l] <= pivot) l++; arr[r] = arr[l]; } arr[l] = pivot; quickSort(arr, left, l - 1); quickSort(arr, l + 1, right); }3. 特点
🚀 实际中最快
❗ 最坏 O(n²)
八、堆排序（Heap Sort）
1. 思想
利用大顶堆/小顶堆的结构。
2.代码实现
package com.qcby; import java.lang.reflect.Array; import java.util.Arrays; public class duiSort { public static void main(String[] args) { int arr[] = {5,7,4,2,0,3,1,6}; for(int p = arr.length-1;p>=0;p--){ sort(arr,p,arr.length); } for(int i = arr.length-1;i>=0;i--){ int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; sort(arr,0,i); } System.out.println(Arrays.toString(arr)); } public static void sort(int arr[], int parent, int length){ int child = parent*2+1; while (child<length){ int rchild = child + 1; if(rchild<length && arr[rchild]>arr[child] ){ child++; } if(arr[parent]<arr[child] ){ int temp = arr[parent]; arr[parent] = arr[child]; arr[child] = temp; parent = child; child = parent*2+1; }else { break; } } } }3.特点
不稳定
不需要额外空间
九、基数排序（Radix Sort）
1. 思想
按位排序（个位 → 十位 → 百位）
2. 特点
非比较排序
适合整数 / 字符串
)
