1. 排序算法基础认知
排序算法是计算机科学中最基础也最重要的算法类别之一。作为数据处理的核心操作，排序直接影响着数据检索、统计分析、图形处理等众多领域的效率。在Java开发中，掌握各种排序算法的实现原理和适用场景，是每个合格程序员的基本功。
排序算法主要分为两大类：比较排序和非比较排序。比较排序通过比较元素间的大小关系来确定顺序，时间复杂度下限为O(nlogn)；而非比较排序（如计数排序、桶排序等）则利用元素的特殊属性进行排序，可以突破这个下限。在实际开发中，我们需要根据数据规模、数据特征和性能需求来选择合适的算法。
提示：算法选择时不仅要考虑时间复杂度，还要关注空间复杂度、稳定性和实现难度。稳定性指的是相等元素的相对顺序在排序前后是否保持不变，这在某些业务场景中非常重要。
2. 常见排序算法详解
2.1 冒泡排序（Bubble Sort）
冒泡排序是最简单的排序算法之一，其基本思想是通过相邻元素的比较和交换，将较大的元素逐步"冒泡"到数组的末端。Java实现如下：
public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n-1; i++) { boolean swapped = false; for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { // 交换相邻元素 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; swapped = true; } } // 如果没有发生交换，说明数组已经有序 if (!swapped) break; } }冒泡排序的时间复杂度为O(n²)，在最好情况下（数组已经有序）为O(n)。空间复杂度为O(1)，是一种稳定的排序算法。
注意：实际开发中冒泡排序很少使用，因为其性能较差。但在小规模数据或近乎有序的数据上，它可能比其他复杂算法更快。
2.2 选择排序（Selection Sort）
选择排序的工作原理是每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。Java实现：
public static 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; } }选择排序的时间复杂度始终为O(n²)，空间复杂度为O(1)，是一种不稳定的排序算法（因为交换可能改变相等元素的相对顺序）。
2.3 插入排序（Insertion Sort）
插入排序的工作方式类似于整理扑克牌，将每个元素插入到已排序部分的适当位置。Java实现：
public static 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; } }插入排序在最好情况下（数组已经有序）时间复杂度为O(n)，最坏和平均情况下为O(n²)。空间复杂度为O(1)，是一种稳定的排序算法。对于小规模或基本有序的数据，插入排序非常高效。
2.4 希尔排序（Shell Sort）
希尔排序是插入排序的改进版，通过将数组分成若干子序列进行插入排序，逐步缩小子序列的间隔。Java实现：
public static 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; } } }希尔排序的时间复杂度取决于间隔序列的选择，最好情况下可以达到O(nlogn)，空间复杂度为O(1)。它是一种不稳定的排序算法。
2.5 归并排序（Merge Sort）
归并排序采用分治策略，将数组分成两半分别排序，然后合并结果。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); } } private static void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left, j = mid + 1, 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++]; System.arraycopy(temp, 0, arr, left, temp.length); }归并排序的时间复杂度始终为O(nlogn)，空间复杂度为O(n)，是一种稳定的排序算法。它特别适合处理大规模数据和外排序。
2.6 快速排序（Quick Sort）
快速排序也是基于分治思想，通过选择一个基准元素将数组分成两部分，一部分小于基准，一部分大于基准。Java实现：
public static 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 static 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++; swap(arr, i, j); } } swap(arr, i + 1, high); return i + 1; } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }快速排序的平均时间复杂度为O(nlogn)，最坏情况下（数组已经有序或逆序）为O(n²)。通过合理选择基准元素（如三数取中法）可以避免最坏情况。空间复杂度为O(logn)（递归栈空间），是一种不稳定的排序算法。
2.7 堆排序（Heap Sort）
堆排序利用堆这种数据结构进行排序。Java实现：
public static 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); } } private static 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); } }堆排序的时间复杂度始终为O(nlogn)，空间复杂度为O(1)，是一种不稳定的排序算法。它适合需要原地排序且对最坏情况时间复杂度有要求的场景。
2.8 计数排序（Counting Sort）
计数排序是一种非比较排序，适用于元素范围不大的整数排序。Java实现：
public static 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 num : arr) { count[num - 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); }计数排序的时间复杂度为O(n+k)，其中k是元素的范围大小。空间复杂度为O(n+k)，是一种稳定的排序算法。当k远小于n时，效率非常高。
2.9 桶排序（Bucket Sort）
桶排序将元素分配到不同的桶中，对每个桶单独排序，然后合并结果。Java实现：
public static void bucketSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); int min = Arrays.stream(arr).min().getAsInt(); int bucketCount = 10; // 桶的数量 double bucketSize = (double)(max - min + 1) / bucketCount; List<List<Integer>> buckets = new ArrayList<>(bucketCount); for (int i = 0; i < bucketCount; i++) { buckets.add(new ArrayList<>()); } // 将元素分配到桶中 for (int num : arr) { int index = (int)((num - min) / bucketSize); if (index >= bucketCount) index = bucketCount - 1; buckets.get(index).add(num); } // 对每个桶排序 int index = 0; for (List<Integer> bucket : buckets) { Collections.sort(bucket); for (int num : bucket) { arr[index++] = num; } } }桶排序的时间复杂度取决于桶的数量和每个桶内使用的排序算法，平均情况下为O(n+k)，空间复杂度为O(n+k)，是一种稳定的排序算法。
2.10 基数排序（Radix Sort）
基数排序按照数字的位数从低到高依次排序。Java实现：
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) { int[] output = new int[arr.length]; int[] count = new int[10]; for (int num : arr) { count[(num / 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(d(n+k))，其中d是最大数字的位数，k是基数（这里是10）。空间复杂度为O(n+k)，是一种稳定的排序算法。
3. 排序算法性能对比
3.1 时间复杂度比较
| 排序算法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | 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(nlogn) | O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | O(n²) | O(n+k) | 稳定 |
| 基数排序 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | 稳定 |
3.2 适用场景分析
- 小规模数据：插入排序、冒泡排序、选择排序简单高效
- 中等规模数据：希尔排序、快速排序、归并排序表现良好
- 大规模数据：归并排序、堆排序、快速排序（优化后）更合适
- 特定条件数据：
- 数据范围不大：计数排序、桶排序、基数排序
- 数据基本有序：插入排序、冒泡排序
- 需要稳定性：归并排序、计数排序、桶排序、基数排序
- 内存有限：堆排序、希尔排序
4. Java中的排序实现
4.1 Arrays.sort()方法
Java标准库提供了高效的排序实现。对于基本类型数组，使用双轴快速排序（Dual-Pivot Quicksort）：
int[] arr = {5, 2, 9, 1, 5, 6}; Arrays.sort(arr); // 排序基本类型数组对于对象数组，使用TimSort（归并排序的优化版本）：
String[] strArr = {"banana", "apple", "pear", "orange"}; Arrays.sort(strArr); // 排序对象数组4.2 Collections.sort()方法
对List集合进行排序，同样使用TimSort：
List<Integer> list = new ArrayList<>(Arrays.asList(5, 2, 9, 1, 5, 6)); Collections.sort(list); // 排序List集合4.3 自定义排序顺序
可以通过Comparator接口实现自定义排序：
// 按字符串长度排序 Arrays.sort(strArr, (s1, s2) -> s1.length() - s2.length()); // 按年龄降序排序 List<Person> people = ...; Collections.sort(people, Comparator.comparingInt(Person::getAge).reversed());5. 排序算法常见面试题
5.1 如何选择排序算法？
选择排序算法需要考虑以下因素：
- 数据规模
- 数据特征（是否基本有序、是否有重复元素等）
- 内存限制
- 稳定性要求
- 实现复杂度
5.2 快速排序的优化方法
- 小数组切换到插入排序（当子数组长度小于某个阈值时）
- 三数取中法选择基准元素
- 三向切分快速排序（处理大量重复元素）
- 尾递归优化
5.3 如何实现稳定版本的快速排序？
可以通过在比较时同时考虑元素值和原始位置来实现：
class Element { int value; int originalIndex; // 比较时先比较value，value相同则比较originalIndex }5.4 外部排序如何处理大数据？
外部排序通常使用多路归并排序：
- 将大数据分成多个小块，每块单独排序后写入临时文件
- 使用最小堆进行多路归并
- 考虑磁盘I/O优化和内存管理
6. 排序算法实战技巧
6.1 避免常见错误
- 数组越界：特别是在实现快速排序和归并排序时
- 无限递归：确保递归终止条件正确
- 性能陷阱：如在小数组上使用复杂排序算法
6.2 调试技巧
- 打印中间结果：在递归或循环中打印关键变量
- 单元测试：为边界情况编写测试用例（空数组、单元素数组、已排序数组等）
- 可视化工具：使用排序可视化工具理解算法执行过程
6.3 性能优化经验
- 对于Java对象排序，考虑使用原始类型数组代替包装类数组
- 对于频繁排序的场景，考虑预分配临时数组空间
- 在排序前检查数组是否已经有序（可以显著提升某些场景的性能）
在实际项目中，我通常会先使用标准库的排序方法，只有在性能分析表明排序是瓶颈时，才会考虑实现特定优化的排序算法。大多数情况下，Java内置的排序实现已经足够高效。
