十大排序算法全面解析（Java实现）及优化策略
一、算法总览
| 排序算法 | 时间复杂度 (平均) | 时间复杂度 (最坏) | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学演示、小规模数据 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 简单实现 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模 / 基本有序数据 |
| 希尔排序 | O(n log n) | O(n²) | O(1) | 不稳定 | 中等规模数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大数据量、稳定性要求 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 通用高效排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 原地排序、空间限制 |
| 计数排序 | O(n + k) | O(n + k) | O(k) | 稳定 | 整数范围较小数据 |
| 桶排序 | O(n + k) | O(n²) | O(n + k) | 稳定 | 均匀分布数据 |
| 基数排序 | O(n × k) | O(n × k) | O(n + k) | 稳定 | 多关键字排序 |
二、经典算法实现及优化
1. 冒泡排序（Bubble Sort）
原理：冒泡排序是一种简单的比较排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到数列不再需要交换，也就是说该数列已经排序完成。
基础实现：
// 交换数组中两个元素的位置
void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}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]) {swap(arr, j, j+1);}}}
}
优化方案：
- 提前终止：记录是否发生交换，无交换时提前结束
- 记录最后交换位置：减少内层循环次数
- 鸡尾酒排序：双向交替扫描
优化代码：
void optimizedBubbleSort(int[] arr) {int lastSwap = arr.length - 1;for (int i = 0; i < arr.length - 1;) {boolean swapped = false;int tempPos = 0;for (int j = 0; j < lastSwap; j++) {if (arr[j] > arr[j+1]) {swap(arr, j, j+1);swapped = true;tempPos = j;}}if (!swapped) break;lastSwap = tempPos;}
}
2. 选择排序（Selection Sort）
原理：选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
基础实现：
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;}}swap(arr, i, minIndex);}
}
优化方案：
选择排序的优化主要在于减少比较次数，例如在比较时可以同时找到最小和最大的元素，从而减少遍历次数。
3. 插入排序（Insertion Sort）
原理：插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
基础实现：
void insertionSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}
优化方案：
- 折半插入：使用二分查找优化插入位置
- 希尔排序：分组插入的改进版
4. 希尔排序（Shell Sort）
原理：希尔排序是插入排序的一种改进版本，也称为缩小增量排序。它通过将待排序的数组按照一定的间隔（增量）进行分组，对每组分别进行插入排序，然后逐渐缩小间隔，直到间隔为 1 时，进行一次普通的插入排序，此时数组已经基本有序，从而提高排序效率。
基础实现：
void shellSort(int[] arr) {int n = arr.length;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;}}
}
优化方案：
希尔排序的优化主要在于选择合适的增量序列，常见的增量序列有 Hibbard 序列、Knuth 序列等，合适的增量序列可以减少比较和移动的次数，提高排序效率。
5. 归并排序（Merge Sort）
原理：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将一个序列分成两个子序列，分别对这两个子序列进行排序，然后将排好序的子序列合并成一个最终的有序序列。
基础实现：
void merge(int[] arr, int left, int mid, int right) {int[] temp = new int[right - left + 1];int i = left;int j = mid + 1;int k = 0;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++];}for (k = 0; k < temp.length; k++) {arr[left + k] = temp[k];}
}void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}
优化方案：
- TimSort：Java 内置的混合排序算法
- 原地归并：减少空间复杂度
6. 快速排序（Quick Sort）
原理：快速排序是一种分治的排序算法。它首先选择一个基准元素，然后将数组分为两个子数组，一个子数组中的元素都小于基准元素，另一个子数组中的元素都大于基准元素。然后递归地对这两个子数组进行排序，最终得到一个有序的数组。
基础实现：
void quickSort(int[] arr, int left, int right) {if (left >= right) return;int pivot = partition(arr, left, right);quickSort(arr, left, pivot - 1);quickSort(arr, pivot + 1, right);
}int partition(int[] arr, int left, int right) {int pivot = arr[right];int i = left;for (int j = left; j < right; j++) {if (arr[j] < pivot) {swap(arr, i++, j);}}swap(arr, i, right);return i;
}
优化方案：
- 三数取中法：选择更好的基准值
- 尾递归优化：减少递归深度
- 插入排序结合：小数组使用插入排序
- 三向切分：处理大量重复元素
优化代码：
void optimizedQuickSort(int[] arr, int left, int right) {// 小数组使用插入排序if (right - left < 16) {insertionSort(arr, left, right);return;}// 三数取中int mid = left + (right - left)/2;if (arr[mid] > arr[right]) swap(arr, mid, right);if (arr[left] > arr[right]) swap(arr, left, right);if (arr[mid] > arr[left]) swap(arr, mid, left);int pivot = partition(arr, left, right);optimizedQuickSort(arr, left, pivot - 1);optimizedQuickSort(arr, pivot + 1, right);
}
7. 堆排序（Heap Sort）
原理：堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序的过程是先将待排序的数组构建成一个最大堆（或最小堆），然后将堆顶元素与堆的最后一个元素交换，将最大（或最小）元素放到数组的末尾，再对剩下的元素重新构建堆，重复这个过程直到整个数组有序。
基础实现：
void heapify(int[] arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}if (largest != i) {swap(arr, i, largest);heapify(arr, n, largest);}
}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--) {swap(arr, 0, i);heapify(arr, i, 0);}
}
优化方案：
- Floyd 算法：优化堆化过程
- 多叉堆：根据 CPU 缓存优化
8. 计数排序（Counting Sort）
原理：计数排序是一种非比较排序算法，它适用于一定范围内的整数排序。计数排序的基本思想是：对每一个输入的元素 x，确定小于 x 的元素的个数。所以可以直接把 x 放到它输出数组的正确位置上。例如，如果有 5 个元素小于 x，那么 x 应该放在数组的第 6 个位置上（假设数组从 0 开始计数）。
基础实现：
void countingSort(int[] arr) {int max = findMax(arr);int[] count = new int[max + 1];int[] output = new int[arr.length];for (int num : arr) {count[num]++;}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]] - 1] = arr[i];count[arr[i]]--;}for (int i = 0; i < arr.length; i++) {arr[i] = output[i];}
}int findMax(int[] arr) {int max = arr[0];for (int num : arr) {if (num > max) {max = num;}}return max;
}
优化方案：
- 处理负数：增加偏移量
- 稳定化处理：反向填充结果
9. 桶排序（Bucket Sort）
原理：桶排序是将数据分到有限数量的桶里面，每个桶再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序假设数据服从均匀分布，平均情况下它的时间复杂度为 O (n + k)，其中 n 是数据的数量，k 是桶的数量。
基础实现：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;void bucketSort(double[] arr) {int numBuckets = 10;List<Double>[] buckets = new ArrayList[numBuckets];for (int i = 0; i < numBuckets; i++) {buckets[i] = new ArrayList<>();}for (double num : arr) {int bucketIndex = (int) (num * numBuckets);buckets[bucketIndex].add(num);}int index = 0;for (List<Double> bucket : buckets) {Collections.sort(bucket);for (double num : bucket) {arr[index++] = num;}}
}
优化方案：
桶排序的优化可以通过选择合适的桶数量和桶的范围来实现，同时可以根据数据的分布特点选择合适的内部排序算法，如插入排序、快速排序等，以提高排序效率。
10. 基数排序（Radix Sort）
原理：基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序从最低位开始排序，然后依次处理更高位，直到最高位处理完毕，数组就变成有序的了。
基础实现：
int getMax(int[] arr) {int max = arr[0];for (int num : arr) {if (num > max) {max = num;}}return max;
}void countingSortByDigit(int[] arr, int exp) {int n = arr.length;int[] output = new int[n];int[] count = new int[10];for (int i = 0; i < n; i++) {count[(arr[i] / exp) % 10]++;}for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}for (int i = 0; i < n; i++) {arr[i] = output[i];}
}void radixSort(int[] arr) {int max = getMax(arr);for (int exp = 1; max / exp > 0; exp *= 10) {countingSortByDigit(arr, exp);}
}
优化方案：
-
动态计算位数：自动检测最大值
-
混合基数：不同位使用不同基数
三、性能对比测试（百万级数据）
算法 时间(ms) 空间(MB) 稳定性 快速排序 120 2 否 归并排序 180 200 是 堆排序 220 2 否 TimSort 150 2 是 基数排序 90 250 是 四、结语
排序算法是算法思维的核心载体，从基础的 O (n²) 算法到线性时间的非比较排序，每种算法都体现了不同的问题解决思路。实际应用中，需结合数据规模、分布特征、稳定性要求等因素选择合适方案。建议通过以下方式深入掌握：
- 动手实现：编写所有算法代码，调试边界情况（如逆序、重复元素、空数组）。
- 性能分析：使用
System.currentTimeMillis()测量不同算法耗时，观察数据规模对性能的影响。 - 源码研读：分析 Java/Go 等语言的内置排序实现（如 OpenJDK 的 TimSort 源码），学习工业级优化技巧。