目录
- 7种排序算法的时间复杂度和稳定性及其稳定性
- 不稳定排序算法巧妙记法
- 不稳定排序算法的定义
- 7种排序算法的C++实现（以数组为例）
- 1. **冒泡排序**（Bubble Sort）
- 2. **选择排序**（Selection Sort）
- 3. **插入排序**（Insertion Sort）
- 4. **希尔排序**（Shell Sort）
- 5. **归并排序**（Merge Sort）
- 6. **快速排序**（Quick Sort）
- 7. **堆排序**（Heap Sort）
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);}
}
)
