阅读量:0
目录
7种排序算法的时间复杂度和稳定性及其稳定性
| 排序算法 | 时间复杂度（最差） | 时间复杂度（平均） | 时间复杂度（最优） | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | 不稳定 |
| 插入排序 | O(n^2) | O(n^2) | O(n) | 稳定 |
| 希尔排序 | O(n log n) | O(n log^2 n) | O(n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | 稳定 |
| 快速排序 | O(n^2) | O(n log n) | O(n log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | 不稳定 |
不稳定排序算法巧妙记法
一堆希尔快选择！
一堆（堆排序）希尔（希尔排序）快（快速排序）选择（选择排序）
不稳定排序算法的定义
在排序过程中，相等的元素在最终排序完成后可能会改变它们原始的相对顺序。换句话说，如果两个元素在原始数组中是相邻的，并且它们的值相同，但在排序后的数组中它们的相对顺序发生了变化，那么这个排序算法就是不稳定的。
举个例子来说明不稳定排序算法：
假设我们有一个数组
[5, 3, 4, 5, 5]
并且我们使用快速排序算法对其进行排序。
在快速排序的过程中，我们选择第一个元素 5 作为基准。
然后我们对数组进行分区，使得所有小于 5 的元素都在 5 的左边，所有大于 5 的元素都在 5 的右边。
分区后，数组变为
[ 3, 5, 4, 5, 5]
此时两个 5 的相对位置发生了变化。
7种排序算法的C++实现（以数组为例）
1. 冒泡排序（Bubble Sort）
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）
void selectionSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { int min_idx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; swap(arr[i], arr[min_idx]); } } 3. 插入排序（Insertion Sort）
void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } 4. 希尔排序（Shell Sort）
void shellSort(int arr[], int n) { 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; } } } 5. 归并排序（Merge Sort）
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]; 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++; } } 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); } } 6. 快速排序（Quick Sort）
int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high - 1; 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); } } 7. 堆排序（Heap Sort）
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) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i = n - 1; i >= 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } } 