Java底子——排序算法

排序算法不管是考试、口试、还是一样寻常开辟中都是一个特别高频的点。下面对八种排序算法做简朴的介绍。

---

1. 冒泡排序（Bubble Sort）

原理：相邻元素比较，每一轮将最大元素“冒泡”到末端。
示例数组：[5, 3, 8, 1, 2]

1. public static void bubbleSort(int[] arr) {
2.     for (int i = 0; i < arr.length - 1; i++) {
3.         boolean swapped = false;
4.         for (int j = 0; j < arr.length - i - 1; j++) {
5.             if (arr[j] > arr[j + 1]) {
6.                 int temp = arr[j];
7.                 arr[j] = arr[j + 1];
8.                 arr[j + 1] = temp;
9.                 swapped = true;
10.             }
11.         }
12.         System.out.println("第 " + (i + 1) + " 轮后: " + Arrays.toString(arr));
13.         if (!swapped) break;
14.     }
15. }

复制代码

输出：

1. 第 1 轮后: [3, 5, 1, 2, 8]  
2. 第 2 轮后: [3, 1, 2, 5, 8]  
3. 第 3 轮后: [1, 2, 3, 5, 8]  
4. 第 4 轮后: [1, 2, 3, 5, 8]  

复制代码

时间复杂度：

• 最好情况：O(n)（已有序时一轮扫描结束）
  
• 最坏/均匀：O(n²)（双重循环嵌套）
  

空间复杂度：O(1)（原地排序，仅需常数空间）
盘算原理：

• 外层循环最多实验 n-1 次，内层循环每次实验 n-i-1 次
  
• 总比较次数 ≈ (n-1) + (n-2) + … + 1 = n(n-1)/2 → O(n²)
  

---

2. 选择排序（Selection Sort）

原理：每轮选择最小的元素，放到已排序部分的末端。
示例数组：[5, 3, 8, 1, 2]

1. public static void selectionSort(int[] arr) {
2.     for (int i = 0; i < arr.length - 1; i++) {
3.         int minIndex = i;
4.         for (int j = i + 1; j < arr.length; j++) {
5.             if (arr[j] < arr[minIndex]) minIndex = j;
6.         }
7.         int temp = arr[i];
8.         arr[i] = arr[minIndex];
9.         arr[minIndex] = temp;
10.         System.out.println("第 " + (i + 1) + " 轮后: " + Arrays.toString(arr));
11.     }
12. }

复制代码

输出：

1. 第 1 轮后: [1, 3, 8, 5, 2]  
2. 第 2 轮后: [1, 2, 8, 5, 3]  
3. 第 3 轮后: [1, 2, 3, 5, 8]  
4. 第 4 轮后: [1, 2, 3, 5, 8]  

复制代码

时间复杂度：

• 所有情况：O(n²)（必须完备实验双重循环）
  

空间复杂度：O(1)（原地互换）
盘算原理：

• 外层循环 n-1 次，内层循环每次实验 n-i-1 次
  
• 总比较次数 = (n-1) + (n-2) + … + 1 = n(n-1)/2 → O(n²)
  

---

3. 插入排序（Insertion Sort）

原理：将未排序元素插入已排序部分的精确位置。
示例数组：[5, 3, 8, 1, 2]

1. public static void insertionSort(int[] arr) {
2.     for (int i = 1; i < arr.length; i++) {
3.         int key = arr[i];
4.         int j = i - 1;
5.         while (j >= 0 && arr[j] > key) {
6.             arr[j + 1] = arr[j];
7.             j--;
8.         }
9.         arr[j + 1] = key;
10.         System.out.println("插入 " + key + " 后: " + Arrays.toString(arr));
11.     }
12. }

复制代码

输出：

1. 插入 3 后: [3, 5, 8, 1, 2]  
2. 插入 8 后: [3, 5, 8, 1, 2]  
3. 插入 1 后: [1, 3, 5, 8, 2]  
4. 插入 2 后: [1, 2, 3, 5, 8]  

复制代码

时间复杂度：

• 最好：O(n)（已有序时仅需线性扫描）
  
• 最坏/均匀：O(n²)（每次插入需移动大量元素）
  

空间复杂度：O(1)
盘算原理：

• 外层循环 n-1 次，内层循环均匀移动 i/2 次
  
• 总操作次数 ≈ 1 + 2 + … + (n-1) = n(n-1)/2 → O(n²)
  

---

4. 快速排序（Quick Sort）

原理：通过基准分区，递归排序左右子数组。
示例数组：[5, 3, 8, 1, 2]

1. public static void quickSort(int[] arr, int low, int high) {
2.     if (low < high) {
3.         int pi = partition(arr, low, high);
4.         System.out.println("基准 " + arr[pi] + " 分区后: " + Arrays.toString(arr));
5.         quickSort(arr, low, pi - 1);
6.         quickSort(arr, pi + 1, high);
7.     }
8. }
10. private static int partition(int[] arr, int low, int high) {
11.     int pivot = arr[high];
12.     int i = low - 1;
13.     for (int j = low; j < high; j++) {
14.         if (arr[j] < pivot) {
15.             i++;
16.             int temp = arr[i];
17.             arr[i] = arr[j];
18.             arr[j] = temp;
19.         }
20.     }
21.     int temp = arr[i + 1];
22.     arr[i + 1] = arr[high];
23.     arr[high] = temp;
24.     return i + 1;
25. }

复制代码

输出：

1. 基准 2 分区后: [1, 2, 8, 5, 3]  
2. 基准 1 分区后: [1, 2, 8, 5, 3]  
3. 基准 3 分区后: [1, 2, 3, 5, 8]  
4. 基准 8 分区后: [1, 2, 3, 5, 8]  

复制代码

时间复杂度：

• 最好/均匀：O(n log n)（每次分区将数组分成两半）
  
• 最坏：O(n²)（每次分区极不均衡，如已有序数组）
  

空间复杂度：O(log n)（递归调用栈的深度）
盘算原理：

• 理想情况：每次分区后左右子数组巨细相称，递归深度 log n，每层处理处罚 O(n) → O(n log n)
  
• 最坏情况：每次分区后一个子数组为空，递归深度 n → O(n²)
  

---

5. 归并排序（Merge Sort）

原理：分治法，将数组拆分为两半，归并有序子数组。
示例数组：[5, 3, 8, 1, 2]

1. public static void mergeSort(int[] arr, int left, int right) {
2.     if (left < right) {
3.         int mid = (left + right) / 2;
4.         mergeSort(arr, left, mid);
5.         mergeSort(arr, mid + 1, right);
6.         merge(arr, left, mid, right);
7.         System.out.println("合并后: " + Arrays.toString(arr));
8.     }
9. }
11. private static void merge(int[] arr, int left, int mid, int right) {
12.     int[] temp = new int[right - left + 1];
13.     int i = left, j = mid + 1, k = 0;
14.     while (i <= mid && j <= right) {
15.         if (arr[i] <= arr[j]) temp[k++] = arr[i++];
16.         else temp[k++] = arr[j++];
17.     }
18.     while (i <= mid) temp[k++] = arr[i++];
19.     while (j <= right) temp[k++] = arr[j++];
20.     System.arraycopy(temp, 0, arr, left, temp.length);
21. }

复制代码

输出：

1. 合并后: [3, 5, 8, 1, 2]  
2. 合并后: [3, 5, 1, 8, 2]  
3. 合并后: [1, 2, 3, 5, 8]  

复制代码

时间复杂度：

• 所有情况：O(n log n)（稳固分治战略）
  

空间复杂度：O(n)（归并时需要暂时数组）
盘算原理：

• 递归树深度为 log n，每层归并总时间 O(n) → O(n log n)
  
• 归并操作需要额外空间存储暂时数组
  

---

6. 堆排序（Heap Sort）

原理：构建最大堆，依次将堆顶元素与末端互换。
示例数组：[5, 3, 8, 1, 2]

1. public static void heapSort(int[] arr) {
2.     int n = arr.length;
3.     for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
4.     for (int i = n - 1; i > 0; i--) {
5.         int temp = arr[0];
6.         arr[0] = arr[i];
7.         arr[i] = temp;
8.         System.out.println("交换堆顶后: " + Arrays.toString(arr));
9.         heapify(arr, i, 0);
10.     }
11. }
13. private static void heapify(int[] arr, int n, int i) {
14.     int largest = i, left = 2 * i + 1, right = 2 * i + 2;
15.     if (left < n && arr[left] > arr[largest]) largest = left;
16.     if (right < n && arr[right] > arr[largest]) largest = right;
17.     if (largest != i) {
18.         int swap = arr[i];
19.         arr[i] = arr[largest];
20.         arr[largest] = swap;
21.         heapify(arr, n, largest);
22.     }
23. }

复制代码

输出：

1. 交换堆顶后: [5, 3, 2, 1, 8]  
2. 交换堆顶后: [1, 3, 2, 5, 8]  
3. 交换堆顶后: [2, 1, 3, 5, 8]  
4. 交换堆顶后: [1, 2, 3, 5, 8]  

复制代码

时间复杂度：

• 所有情况：O(n log n)（建堆 O(n)，每次调解堆 O(log n)）
  

空间复杂度：O(1)（原地排序）
盘算原理：

• 建堆时间复杂度为 O(n)（非叶子节点下沉操作）
  
• 每次互换堆顶后调解堆需要 O(log n) 时间，共 n-1 次 → O(n log n)
  

---

7. 希尔排序（Shell Sort）

原理：按间隔分组，渐渐缩小间隔举行插入排序。
示例数组：[5, 3, 8, 1, 2]

1. public static void shellSort(int[] arr) {
2.     int n = arr.length;
3.     for (int gap = n / 2; gap > 0; gap /= 2) {
4.         for (int i = gap; i < n; i++) {
5.             int temp = arr[i], j;
6.             for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
7.                 arr[j] = arr[j - gap];
8.             }
9.             arr[j] = temp;
10.         }
11.         System.out.println("间隔 " + gap + " 排序后: " + Arrays.toString(arr));
12.     }
13. }

复制代码

输出：

1. 间隔 2 排序后: [5, 1, 2, 3, 8]  
2. 间隔 1 排序后: [1, 2, 3, 5, 8]  

复制代码

时间复杂度：

• 取决于间隔序列：
  
  
  
  • 最坏 O(n²)（如使用原始希尔序列）
    
  • 均匀 O(n log n)（如使用Knuth序列）
    
  
  

空间复杂度：O(1)
盘算原理：

• 通过分组淘汰数据移动间隔
  
• 差别间隔序列的时间复杂度差别，例如：
  
  
  
  • 希尔原始序列（n/2^k）：O(n²)
    
  • Knuth序列（3k-1）：O(n1.5)
    
  
  

---

8. 基数排序（Radix Sort）

原理：按位数从低到高排序（需稳固排序辅助）。
示例数组：[170, 45, 75, 90, 802, 24, 2, 66]

1. public static void radixSort(int[] arr) {
2.     int max = Arrays.stream(arr).max().getAsInt();
3.     for (int exp = 1; max / exp > 0; exp *= 10) {
4.         countingSort(arr, exp);
5.         System.out.println("按第 " + exp + " 位排序后: " + Arrays.toString(arr));
6.     }
7. }
9. private static void countingSort(int[] arr, int exp) {
10.     int[] output = new int[arr.length];
11.     int[] count = new int[10];
12.     for (int num : arr) count[(num / exp) % 10]++;
13.     for (int i = 1; i < 10; i++) count[i] += count[i - 1];
14.     for (int i = arr.length - 1; i >= 0; i--) {
15.         output[count[(arr[i] / exp) % 10] - 1] = arr[i];
16.         count[(arr[i] / exp) % 10]--;
17.     }
18.     System.arraycopy(output, 0, arr, 0, arr.length);
19. }

复制代码

输出：

1. 按第 1 位排序后: [170, 90, 802, 2, 24, 45, 75, 66]  
2. 按第 10 位排序后: [802, 2, 24, 45, 66, 170, 75, 90]  
3. 按第 100 位排序后: [2, 24, 45, 66, 75, 90, 170, 802]  

复制代码

时间复杂度：O(nk)（k为最大数字位数）
空间复杂度：O(n + k)（计数排序的额外空间）
盘算原理：

• 对每个位数举行稳固排序（如计数排序）
  
• 若最大数为 d 位，则举行 d 轮排序，每轮 O(n) → 总时间 O(dn)
  

---

总结表格

排序算法最好时间均匀时间最坏时间空间复杂度稳固性冒泡排序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 log n)O(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)不稳固希尔排序O(n log n)取决于间隔O(n²)O(1)不稳固基数排序O(nk)O(nk)O(nk)O(n + k)稳固复杂度盘算核心头脑

• 循环嵌套次数：
  
  
  
  • 双重循环（如冒泡、选择、插入）→ O(n²)
    
  • 分治法（快速、归并）→ 递归深度 log n × 每层 O(n) → O(n log n)
    
  
  
• 数据移动代价：
  
  
  
  • 插入排序的移动次数与逆序对数量相关
    
  • 堆排序的调解代价与树高度 log n 相关
    
  
  
• 额外空间使用：
  
  
  
  • 递归算法的栈空间（快速排序 O(log n)）
    
  • 归并排序的暂时数组（O(n)）
    
  • 基数排序的计数数组（O(n + k)）