基础排序算法讲解
排序算法是计算机科学中最基础的算法之一，用于将一组数据按照某种规则（如升序或降序）重新排列。以下是几种常见的基础排序算法及其特点：
1. 冒泡排序 (Bubble Sort)
基本思想：
比较相邻的两个元素，如果顺序错误就交换它们。
每一轮遍历都会将最大的元素“冒泡”到最后。
重复这个过程，直到所有元素有序。
时间复杂度：
最好情况（已有序）：O(n)
最坏情况（逆序）：O(n²)
平均情况：O(n²)
稳定性：
稳定（相同元素的相对顺序不会改变）
代码示例（C++）：
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
适用场景：
小规模数据或基本有序的数据。
2. 选择排序 (Selection Sort)
基本思想：
每次从未排序部分选择最小的元素，放到已排序部分的末尾。
重复这个过程，直到所有元素有序。
时间复杂度：
最好/最坏/平均情况：O(n²)
稳定性：
不稳定（交换可能破坏相同元素的相对顺序）
代码示例（C++）：
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
适用场景：
适用于小规模数据，但比冒泡排序稍快。
3. 插入排序 (Insertion Sort)
基本思想：
将数组分为已排序和未排序两部分。
每次从未排序部分取出一个元素，插入到已排序部分的正确位置。
时间复杂度：
最好情况（已有序）：O(n)
最坏情况（逆序）：O(n²)
平均情况：O(n²)
稳定性：
稳定
代码示例（C++）：
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; 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. 快速排序 (Quick Sort)
基本思想：
分治法（Divide & Conquer）：
选择一个基准（pivot），将数组分为两部分：
左边部分 ≤ pivot
右边部分 > pivot
递归地对左右两部分排序。
时间复杂度：
最好/平均情况：O(n log n)
最坏情况（已有序或逆序）：O(n²)（但可通过随机化pivot优化）
稳定性：
不稳定（交换可能改变相同元素的顺序）
代码示例（C++）：
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], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
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);
}
}
适用场景：
大规模数据排序（最快的通用排序算法之一）。
5. 归并排序 (Merge Sort)
基本思想：
分治法（Divide & Conquer）：
将数组分成两半，递归排序。
合并两个有序子数组。
时间复杂度：
最好/最坏/平均情况：O(n log n)
稳定性：
稳定
代码示例（C++）：
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[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++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
适用场景：
需要稳定排序的大规模数据（如数据库排序）。
总结对比
排序算法 时间复杂度（平均） 稳定性 适用场景
冒泡排序 O(n²) 稳定 小规模数据
选择排序 O(n²) 不稳定 小规模数据
插入排序 O(n²) 稳定 小规模或部分有序数据
快速排序 O(n log n) 不稳定 大规模数据
归并排序 O(n log n) 稳定 大规模数据（稳定排序）
如何选择排序算法？
小数据（n < 100）：插入排序 / 冒泡排序
大数据（n ≥ 1000）：快速排序（最快） / 归并排序（稳定）
需要稳定排序：归并排序 / 插入排序
希望这个讲解对你有帮助！
