| 排序算法 | 平均时间复杂度 | 最好 | 最差 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 快速排序 | O(n*log2n) | O(n*log2n) | O(n2) | O(log2n) | 不稳定 |
| 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(n*log2n) | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |
| 归并排序 | O(n*log2n) | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |
插入排序
直接插入排序(straight insertion sert)
交换排序
冒泡排序(bubble sort)
void bubbleSort(vector<int> &a) {
int exchange = a.size() - 1;// 第一趟冒泡排序的区间是[0,n-1]
while (exchange > 0) {// 当上一趟排序有记录交换时
int bound = exchange;
exchange = 0;
for (int i = 0; i < bound; i++) {// 一趟冒泡排序,排序区间是[0,bound-1]
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
exchange = i;// 记载每一次记录交换的位置
}
}
}
}
快速排序(quick sort)
int partition(vector<int> &a, int front, int end) {
while (front < end) {
while (front < end && a[front] <= a[end]) {// 右侧扫描
end--;
}
if (front < end) {
swap(a[front], a[end]);// 将较小记录交换到前面
front++;
}
while (front < end && a[front] <= a[end]) {// 左侧扫描
front++;
}
if (front < end) {
swap(a[front], a[end]);// 将较大记录交换到后面
end--;
}
}
return front;// 轴值记录的最终位置
}
void quickSort(vector<int> &a, int front, int end) {
if (front < end) {// 区间长度大于1,执行一次划分,否则递归结束
int pivot = partition(a, front, end);// 一次划分
quickSort(a, front, pivot - 1);// 递归地对左侧子序列进行快速排序
quickSort(a, pivot + 1, end);// 递归地对右侧子序列进行快速排序
}
}
选择排序
简单选择排序(simple selction sort)
void selectSort(vector<int> &a) {
for (int i = 0; i < a.size() - 1; i++) {// 对n个记录进行n-1躺简单选择排序
int index = i;
for (int j = i + 1; j < a.size(); j++) {// 在无序区中选取最小记录
if (a[index] > a[j]) {
index = j;
}
}
if (index != i) {
swap(a[i], a[index]);
}
}
}
堆排序(heap sort)
堆(heap) 完全二叉树(数组)
- 小根堆(结点<=左结点 && 结点<=右结点)
- 大根堆(结点>=左结点 && 结点>=右结点)
void sift(vector<int> &a, int front, int end) {
int i = front, j = 2 * i + 1;// i指向被筛选结点,j指向结点i的左孩子
while (j <= end) {// 筛选还没有进行到叶子
if (j + 1 <= end && a[j + 1] > a[j]) {// 比较i的左右孩子,j指向较大者
j++;
}
if (a[i] >= a[j]) {// 根结点已经大于左右孩子中的较大者
break;
} else {
swap(a[i], a[j]);// 将根结点与结点j交换
i = j; // 被筛结点位于原来结点j的位置
j = 2 * i + 1;
}
}
}
void heapSort(vector<int> &a) {
for (int i = a.size() / 2 - 1; i >= 0; i--) {// 初始建堆,从最后一个分支结点至根结点
sift(a, i, a.size() - 1);
}
for (int i = 0; i < a.size(); i++) {// 重复执行移走堆顶及重建堆的操作
swap(a[0], a[a.size() - 1 - i]);
sift(a, 0, a.size() - 1 - i - 1);
}
}
归并排序
二路归并排序
void merge(vector<int> &a, int front, int middle, int end) {
int i = front, j = middle + 1;
vector<int> b(end - front + 1);
int k = 0;
while (i <= middle && j <= end) {// 取a[i]和a[j]中的较小者放入b[k]
if (a[i] <= a[j]) {
b[k++] = a[i++];
} else {
b[k++] = a[j++];
}
}
while (i <= middle) {// 若第一个子序列没处理完,则进行收尾处理
b[k++] = a[i++];
}
while (j <= end) {// 若第二个子序列没处理完,则进行收尾处理
b[k++] = a[j++];
}
for (int m = 0; m < k; m++) {
a[front + m] = b[m];
}
}
void mergeSort(vector<int> &a, int front, int end) {
if (front < end) {
int middle = (front + end) / 2;
mergeSort(a, front, middle);// 归并排序前半个子序列
mergeSort(a, middle + 1, end);// 归并排序后半个子序列
merge(a, front, middle, end);// 将两个已排序的子序列归并
}
}
排序
sort
对区间进行排序
bool cmp(int a, int b) {
return a > b;
}
sort(a.begin(), a.end());
sort(a.begin(), a.end(), cmp);
sort(a.begin(), a.end(), less<>());
sort(a.begin(), a.end(), less_equal<>());
sort(a.begin(), a.end(), greater<>());
sort(a.begin(), a.end(), greater_equal<>());
stable_sort
对区间进行排序,并保留相同元素的相对顺序
- 归并排序
partial_sort
对区间进行部分排序,提供完整排序的前n个元素
- 堆排序
partial_sort(a.begin(), a.begin() + 5, a.end());
网友评论