---

本文全面讲解十大经典排序算法的实现原理，并提供完整的Java代码实现。每种算法的时间复杂度、空间复杂度和稳定性分析见文末总结表格。

---

一、冒泡排序（Bubble Sort）

算法逻辑：

1. 依次比较相邻元素，前大后小则交换
2. 每轮遍历将最大值冒泡到末尾
3. 重复n-1轮完成排序

public static void bubbleSort(int[] arr) {for(int i=0; i<arr.length-1; i++) {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;}}}
}

---

二、选择排序（Selection Sort）

算法逻辑：

1. 在未排序序列中找到最小元素
2. 与序列起始位置元素交换
3. 重复上述过程直到排序完成

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;}
}

---

三、插入排序（Insertion Sort）

算法逻辑：

1. 将第一个元素视为已排序序列
2. 取出下一个元素，在已排序序列中从后向前扫描
3. 找到相应位置插入元素
4. 重复步骤2-3

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;}
}

---

四、希尔排序（Shell Sort）

算法逻辑：

1. 定义增量序列（本文使用gap/2）
2. 按增量分组进行插入排序
3. 逐步缩小增量直至1

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;for(j=i; j>=gap && arr[j-gap]>temp; j-=gap) {arr[j] = arr[j-gap];}arr[j] = temp;}}
}

---

五、归并排序（Merge Sort）

算法逻辑：

1. 将数组递归分成两半
2. 对子数组进行排序
3. 合并两个有序子数组

import java.util.Arrays;public class MergeSort {public static void mergeSort(int[] arr) {if (arr == null || arr.length <= 1) return;int[] temp = new int[arr.length]; // 临时数组用于合并操作sort(arr, 0, arr.length - 1, temp);}private static void sort(int[] arr, int low, int high, int[] temp) {if (low >= high) return; // 递归终止条件int mid = low + (high - low) / 2; // 防止整数溢出sort(arr, low, mid, temp);      // 递归排序左半部分sort(arr, mid + 1, high, temp); // 递归排序右半部分merge(arr, low, mid, high, temp); // 合并两个有序区间}private static void merge(int[] arr, int low, int mid, int high, int[] temp) {int i = low;    // 左区间起始指针int j = mid + 1; // 右区间起始指针int t = 0;      // 临时数组指针// 合并两个有序区间到临时数组while (i <= mid && j <= high) {if (arr[i] <= arr[j]) {temp[t++] = arr[i++];} else {temp[t++] = arr[j++];}}// 处理剩余元素while (i <= mid) temp[t++] = arr[i++];while (j <= high) temp[t++] = arr[j++];// 将临时数组数据拷贝回原数组t = 0;while (low <= high) {arr[low++] = temp[t++];}}public static void main(String[] args) {// 测试用例int[] arr1 = {8, 4, 5, 7, 1, 3, 6, 2};mergeSort(arr1);System.out.println("排序结果 1: " + Arrays.toString(arr1)); // [1,2,3,4,5,6,7,8]int[] arr2 = {5};mergeSort(arr2);System.out.println("排序结果 2: " + Arrays.toString(arr2)); // [5]int[] arr3 = {};mergeSort(arr3);System.out.println("排序结果 3: " + Arrays.toString(arr3)); // []int[] arr4 = {9, 9, 4, 4, 2};mergeSort(arr4);System.out.println("排序结果 4: " + Arrays.toString(arr4)); // [2,4,4,9,9]int[] arr5 = {1, 2, 3, 4, 5};mergeSort(arr5);System.out.println("排序结果 5: " + Arrays.toString(arr5)); // [1,2,3,4,5]int[] arr6 = {5, 4, 3, 2, 1};mergeSort(arr6);System.out.println("排序结果 6: " + Arrays.toString(arr6)); // [1,2,3,4,5]}
}

---

六、快速排序（Quick Sort）

算法逻辑：

1. 选取基准元素（pivot）
2. 将数组分为小于和大于基准的两部分
3. 递归排序子数组

public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length-1);
}private static void quickSort(int[] arr, int low, int high) {if(low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot-1);quickSort(arr, pivot+1, high);}
}private static int partition(int[] arr, int low, int high) {// 分区实现代码（详见完整代码）
}

---

七、堆排序（Heap Sort）

算法逻辑：

1. 构建最大堆
2. 将堆顶元素与末尾元素交换
3. 调整堆结构
4. 重复步骤2-3

import java.util.Arrays;public class HeapSort {public static void heapSort(int[] arr) {if (arr == null || arr.length <= 1) return;// 1. 构建最大堆（从最后一个非叶子节点开始调整）int n = arr.length;for (int i = n/2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 2. 逐个提取堆顶元素（最大值）for (int i = n-1; i >= 0; i--) {// 将当前堆顶（最大值）移到数组末尾swap(arr, 0, i);// 调整剩余元素重建最大堆（堆大小减1）heapify(arr, i, 0);}}// 调整以节点i为根的子树为最大堆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[] arr1 = {4, 10, 3, 5, 1};heapSort(arr1);System.out.println("排序结果 1: " + Arrays.toString(arr1)); // [1,3,4,5,10]int[] arr2 = {12};heapSort(arr2);System.out.println("排序结果 2: " + Arrays.toString(arr2)); // [12]int[] arr3 = {};heapSort(arr3);System.out.println("排序结果 3: " + Arrays.toString(arr3)); // []int[] arr4 = {5, 5, 3, 3, 2};heapSort(arr4);System.out.println("排序结果 4: " + Arrays.toString(arr4)); // [2,3,3,5,5]int[] arr5 = {1, 2, 3, 4, 5};heapSort(arr5);System.out.println("排序结果 5: " + Arrays.toString(arr5)); // [1,2,3,4,5]int[] arr6 = {9, 7, 5, 3, 1};heapSort(arr6);System.out.println("排序结果 6: " + Arrays.toString(arr6)); // [1,3,5,7,9]}
}

---

八、桶排序（Bucket Sort）

算法逻辑：

1. 创建若干空桶
2. 将元素分配到对应区间桶中
3. 对每个非空桶排序
4. 合并所有桶元素

import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;public class BucketSort {public static void bucketSort(int[] arr) {if (arr == null || arr.length == 0) {return;}// 确定最大值和最小值int min = arr[0];int max = arr[0];for (int num : arr) {if (num < min) {min = num;} else if (num > max) {max = num;}}// 所有元素相等，无需排序if (max == min) {return;}// 初始化桶int bucketCount = arr.length;ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);for (int i = 0; i < bucketCount; i++) {buckets.add(new ArrayList<>());}// 将元素分配到桶中for (int num : arr) {// 计算桶的索引，确保均匀分布int bucketIndex = ((num - min) * (bucketCount - 1)) / (max - min);buckets.get(bucketIndex).add(num);}// 对每个桶进行排序并合并int index = 0;for (ArrayList<Integer> bucket : buckets) {Collections.sort(bucket); // 使用内置排序算法for (int num : bucket) {arr[index++] = num;}}}public static void main(String[] args) {int[] arr1 = {3, 1, 4, 2, 5};bucketSort(arr1);System.out.println("排序结果 1: " + Arrays.toString(arr1));int[] arr2 = {5, 3, 9, 1, 7};bucketSort(arr2);System.out.println("排序结果 2: " + Arrays.toString(arr2));int[] arr3 = {9, 5, 7, 3, 2, 1};bucketSort(arr3);System.out.println("排序结果 3: " + Arrays.toString(arr3));int[] arr4 = {1, 0, 100, 50};bucketSort(arr4);System.out.println("排序结果 4: " + Arrays.toString(arr4));}
}

---

九、计数排序（Counting Sort）

算法逻辑：

1. 统计元素出现次数
2. 计算元素正确位置
3. 反向填充目标数组

public static void countingSort(int[] arr) {int max = Arrays.stream(arr).max().getAsInt();int[] count = new int[max+1];// 统计频率for(int num : arr) count[num]++;// 计算位置for(int i=1; i<count.length; 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]]] = arr[i];}System.arraycopy(output, 0, arr, 0, arr.length);
}

---

十、基数排序（Radix Sort）

算法逻辑：

1. 从低位到高位依次排序
2. 使用稳定排序算法（通常为计数排序）
3. 逐位排序直到最高位

public static void radixSort(int[] arr) {int max = Arrays.stream(arr).max().getAsInt();for(int exp=1; max/exp>0; exp*=10) {countingSortByDigit(arr, exp);}
}private static void countingSortByDigit(int[] arr, int exp) {// 按指定位进行计数排序
}

---

总结对比表

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	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(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
快速排序	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(1)	不稳定
桶排序	O(n+k)	O(n+k)	O(n²)	O(n+k)	稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定

注：k为桶的数量或数值范围