排序算法是计算机科学中最基础也是最重要的算法之一。本文将详细介绍九种常见的排序算法，包括它们的原理、Java实现、时间复杂度和适用场景，帮助您全面理解排序算法的核心思想。
原理：重复遍历数组，比较相邻元素，如果顺序错误就交换它们，直到没有需要交换的元素为止。
Java实现：
javapublic void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// 交换arr[j]和arr[j+1]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
特点：
原理：每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。
Java实现：
javapublic void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
int minIdx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// 交换找到的最小元素和第一个元素
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
特点：
原理：将未排序部分的第一个元素插入到已排序部分的适当位置。
Java实现：
javapublic 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;
}
}
特点：
原理：改进的插入排序，通过将数组分成若干子序列进行插入排序，最后对整个数组进行插入排序。
Java实现：
javapublic void shellSort(int[] arr) {
int n = arr.length;
// 初始间隔为n/2，逐步缩小
for (int gap = n/2; gap > 0; gap /= 2) {
// 对每个子数组进行插入排序
for (int i = gap; i < n; 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;
}
}
}
特点：
原理：分治法，将数组分成两半分别排序，然后合并两个有序数组。
Java实现：
javapublic void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l+r)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
private void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l+i];
for (int j = 0; j < n2; j++) R[j] = arr[m+1+j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
特点：
原理：分治法，选择一个基准元素，将数组分成两部分，左边小于基准，右边大于基准，然后递归排序两部分。
Java实现：
javapublic 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;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// 交换arr[i]和arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换arr[i+1]和arr[high]
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
特点：
原理：利用堆数据结构设计的排序算法，首先构建最大堆，然后反复取出堆顶元素。
Java实现：
javapublic void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆
for (int i = n/2-1; i >= 0; i--) {
heapify(arr, n, i);
}
// 逐个提取元素
for (int i = n-1; i > 0; i--) {
// 移动当前根到末尾
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 对剩余堆进行堆化
heapify(arr, i, 0);
}
}
private void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大值为根
int l = 2*i + 1; // 左子节点
int r = 2*i + 2; // 右子节点
// 如果左子节点大于根
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
// 如果右子节点大于当前最大值
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
// 如果最大值不是根
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归堆化受影响的子树
heapify(arr, n, largest);
}
}
特点：
原理：非比较排序，统计每个元素的出现次数，然后计算每个元素在输出数组中的位置。
Java实现：
javapublic void countingSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1;
int[] count = new int[range];
int[] output = new int[arr.length];
// 统计每个元素的出现次数
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
// 计算累计次数
for (int i = 1; i < count.length; i++) {
count[i] += count[i-1];
}
// 构建输出数组
for (int i = arr.length-1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
// 拷贝回原数组
System.arraycopy(output, 0, arr, 0, arr.length);
}
特点：
原理：非比较排序，按位进行排序，从最低位到最高位依次排序。
Java实现：
javapublic void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
// 对每个位数进行计数排序
for (int exp = 1; max/exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
private void countingSortByDigit(int[] arr, int exp) {
int[] output = new int[arr.length];
int[] count = new int[10];
Arrays.fill(count, 0);
// 统计出现次数
for (int j : arr) {
count[(j/exp)%10]++;
}
// 计算累计次数
for (int i = 1; i < 10; i++) {
count[i] += count[i-1];
}
// 构建输出数组
for (int i = arr.length-1; i >= 0; i--) {
output[count[(arr[i]/exp)%10] - 1] = arr[i];
count[(arr[i]/exp)%10]--;
}
// 拷贝回原数组
System.arraycopy(output, 0, arr, 0, arr.length);
}
特点：
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|---|
| 冒泡排序 | 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+k) | O(n+k) | 稳定 | 整数，范围小 |
| 基数排序 | O(nk) | O(nk) | O(nk) | O(n+k) | 稳定 | 非负整数，位数少 |
Java标准库中的Arrays.sort()方法根据数据类型和大小自动选择最合适的排序算法：
理解这些排序算法的原理和特点，能够帮助我们在实际开发中选择最合适的排序策略，提高程序性能。