目录
排序算法是编程世界的基础，也是面试中的常客。但你真的搞清楚了哪些算法是稳定的，哪些是不稳定的吗？别担心，这篇文章将带你轻松搞懂常见排序算法，并彻底掌握“稳定”和“不稳定”排序的核心区别。无论你是新手还是想加深理解，本文都将是你不可错过的宝藏。
1. 排序算法的稳定性是什么？
举个例子：
2. 常见的稳定排序算法
1. 冒泡排序（Bubble Sort）
2. 插入排序（Insertion Sort）
3. 归并排序（Merge Sort）
4. 计数排序（Counting Sort）
3. 常见的不稳定排序算法
1. 选择排序（Selection Sort）
2. 快速排序（Quick Sort）
3. 堆排序（Heap Sort）
4. 稳定排序 VS 不稳定排序：如何选择？
稳定排序适合的场景：
不稳定排序适合的场景：
结论
排序算法是编程世界的基础，也是面试中的常客。但你真的搞清楚了哪些算法是稳定的，哪些是不稳定的吗？别担心，这篇文章将带你轻松搞懂常见排序算法，并彻底掌握“稳定”和“不稳定”排序的核心区别。无论你是新手还是想加深理解，本文都将是你不可错过的宝藏。
1. 排序算法的稳定性是什么？
在排序算法中，稳定性指的是相等元素的相对顺序是否在排序后保持不变。简单来说，如果排序前两个相等的元素在数组中的相对位置是固定的，排序后它们的位置依然不变，那么这种算法就是稳定排序；如果排序后位置可能会变化，那就是不稳定排序。
举个例子：
假设你要排序一组学生信息，他们的成绩相同，但你希望保持先录入的顺序。这时候你就需要一个稳定的排序算法。如果你用的是不稳定排序算法，虽然成绩排好了，但录入顺序可能会被打乱。
2. 常见的稳定排序算法
1. 冒泡排序（Bubble Sort）
原理：每次比较相邻两个元素，发现顺序不对就交换，直到没有需要交换的元素为止。
特点：因为相等的元素不会互相交换，所以是稳定排序。
适用场景：小数据集或已经基本排好序的数组。
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
2. 插入排序（Insertion Sort）
原理：将元素插入到已排序部分的正确位置，向左移动比它大的元素。
特点：不会改变相等元素的顺序，因此是稳定的。
适用场景：小数据集或几乎已排好序的数据。
public class InsertionSort {
public static 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;
}
}
}
3. 归并排序（Merge Sort）
原理：采用分治法，将数组分成两半，分别排序后再合并。
特点：在合并时，优先合并左边的相等元素，保持相对顺序，稳定排序。
适用场景：大规模数据，追求稳定性的场景。
public class MergeSort {
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);
}
}
}
4. 计数排序（Counting Sort）
原理：通过统计每个值的出现次数，按顺序排列。
特点：计数过程不会改变相同元素的相对顺序，所以是稳定的。
适用场景：数据范围有限的整数排序。
3. 常见的不稳定排序算法
1. 选择排序（Selection Sort）
原理：每次遍历数组，找到未排序部分的最小元素，放到前面。
特点：在找到最小值后进行交换时，可能会打乱相等元素的顺序，所以是不稳定的。
适用场景：需要减少交换次数的情况，但对稳定性要求不高。
public class SelectionSort {
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;
}
}
}
2. 快速排序（Quick Sort）
原理：选择一个基准元素，将数组分为两部分，左边比基准小，右边比基准大，递归排序。
特点：在划分过程中，相等的元素可能被分到不同的部分，导致相对顺序发生变化，不稳定。
适用场景：速度快，适用于大数据集，但对稳定性没有要求的场景。
public class QuickSort {
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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
3. 堆排序（Heap Sort）
原理：利用堆这种数据结构，首先构建最大堆，然后逐步将堆顶元素与末尾元素交换，并重新调整堆。
特点：在构建堆和调整堆的过程中，可能会改变相等元素的相对顺序，不稳定。
适用场景：数据量较大，且对稳定性要求不高的场景。
4. 稳定排序 VS 不稳定排序：如何选择？
什么时候选择稳定排序？
当排序的元素有多个关键字，且你希望在一个关键字上排序后，再根据另一个关键字进行排序时，稳定性非常重要。
例如，排序一组学生成绩时，成绩相同的情况下，还希望保持他们的录入顺序。
什么时候选择不稳定排序？
当你不关心相等元素的相对顺序，或者排序效率更重要时（比如快速排序通常速度很快），可以选择不稳定排序。
稳定排序适合的场景：
数据相对较小或需要多次排序时。
需要保持数据原有顺序时，例如数据库的二次排序。
不稳定排序适合的场景：
大数据集，追求更高的性能时。
不关心相等元素的相对顺序时。
结论
不同排序算法的稳定性特性，使得它们在不同场景下表现各异。对于需要保持数据相对顺序的情况，可以选择稳定排序算法。而在追求速度的场景下，不稳定排序算法可能更具优势。
掌握这些排序算法的稳定性，将帮助你在实际开发中更有针对性地选择合适的算法，写出更高效的代码！