排序算法总结
排序算法分类
- 基于���较的排序
- 通过比较大小来决定元素间的相对次序。
- 可以证明时间复杂度下界为 O ( n l o g n ) O(nlogn) O(nlogn)，不可能突破这个复杂度达到更快。
- 非比较类排序
- 不通过比较大小来决定元素间的相对次序。
- 时间复杂度受元素的范围以及分布等多种因素影响，不单纯取决于元素数量 N。
比较类排序
- 选择排序
- 简单选择排序
- 每次从未排序数据中找最小值，放到已排序序列的末尾。
- 时间复杂度
O
(
n
2
)
O(n^2)
O(n2)。
for(int i = 0;i
- 堆排序
- 利用二叉堆高效地选出最小值，建立一个包含所有 n n n 个元素的二叉堆，重复 n n n 次从堆中取出最小值，即可得到有序序列。
- 时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。
void heap_sort(int a[], int n) { priority_queue q; for(int i = 0;i - 插入排序
- 简单插入排序
- 从前到后依次考虑每个未排序数据，在已排序序列中找到合适位置插入。
- 时间复杂度
O
(
n
2
)
O(n^2)
O(n2)。
for(int i = 1;i = 0 && nums[pre_index] > current) { nums[pre_index + 1] = nums[pre_index]; pre_index--; } nums[pre_index + 1] = current; } - 希尔排序
- 希尔排序是对插入排序的优化 – 增量分组插入排序。
- 时间复杂度取决于增量序列（步长序列）的选取，最好序列可以做到 N 4 3 N^\frac43 N34 或 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)。
- 交换排序
- 冒泡排序
- 不断循环扫描，每次查看相邻的元素，如何逆序，则交换。
- 时间复杂度
O
(
n
2
)
O(n^2)
O(n2)。
for(int i = 0;i nums[j + 1]) { int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } } - 快速排序
- 快速排序也是一个基于分治的算法。
- 从数组中选取中轴元素 pivot。
- 将小元素放在 pivot 左边，大元素放在右边。
- 然后分别对左边和右边的子数组进行快排。
- 快速排序和归并排序具有相似性，但步骤顺序相反。
- 归并排序：先排序左右子数组，然后合并两个有序数组。
- 快速排序：先调配出左右子数组，然后对左右子数组分别进行排序。
- 随机选取 pivot，期望时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)，最坏
O
(
n
2
)
O(n^2)
O(n2)
void quickSort(vector& arr, int left, int right) { if (left >= right) return; int pivot = partition(arr, left, right); quickSort(arr, left, pivot); quickSort(arr, pivot + 1, right); } int partition(vector& arr, int left, int right) { int pivot = left + rand() % (right - left + 1); int pivotVal = arr[pivot]; while(left while(arr[left] - 归并排序
- 归并排序是一个基于分治的算法。
- 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 。
- 原问题：把数组排序。
- 子问题：把数组前一半、后一半分别排序，然后再合并左右两半（两个有序数组）就可以了。
void mergeSort(vector& arr, int l, int r) { if (l >= r) return; int mid = (l + r) >> 1; mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); return merge(arr, l, mid, r); } void merge(vector& arr, int left, int mid, int right) { vector tmp = vector(right - left + 1); // 临时数组 int i = left, j = mid + 1; for(int k = 0;k right || (i // 合并两个有序数组 tmp[k] = arr[i++]; } else { tmp[k] = arr[j++]; } } for (int k = 0;k
- 冒泡排序
- 简单插入排序
- 简单选择排序
- 选择排序
The End