排序题目主要有以下两种考察形式
1. 手撕经典排序算法
判断时什么排序， 运用排序算法进行下一轮排序
直接插入排序（insertion sort）
特点：前n个有序，后半部分与原序列相同
-
代码（用sort函数模拟）
void insert() { for (int i = 1; i <= len; i++) { sort(a, a + i); } }
希尔排序（shell sort）
模拟每一轮去判断
-
代码
void shell() { for (int d = len / 2; d >= 1; d /= 2) { // d为步长 for (int i = d; i < len; i++) { if (a[i] < a[i - d]) { int num = a[i]; int j; for (j = i - d; j >= 0 && a[j] > num; j -= d) { a[j + d] = a[j]; } a[j + d] = num; } } } }
简单选择排序（select sort）
- 代码
void select() {
for (int i = 0; i < len - 1; i++) {
int k = i;
for (int j = i; j < len; j++) {
if (a[j] < a[k]) {
k = j;
}
}
swap(a[k], a[i]);
}
}
堆排序
- 数组从0开始编号和从1开始编号会影响代码，此处为从1开始编号：堆中，父节点为i， 左儿子为2 * i+1, 右儿子为2* i+2；堆的最后一个节点编号为len - 1, 最后一个节点的父节点为len/2 - 1;
- 代码
void maxheap(int l, int r) {
int father = l;
int son = 2 * l + 1;
while (son <= r) {
if (son + 1 <= r && a[son] < a[son + 1]) son++;
if (a[father] > a[son]) return;
else {
swap(a[son], a[father]);
father = son;
son = father * 2 + 1;
}
}
}
void heapsort() {
for (int i = len / 2 - 1; i >= 0; i--) maxheap(i, len - 1);
for (int i = len - 1; i > 0; i--) {
swap(a[i], a[0]);
maxheap(0, i - 1);
}
}
快速排序
- 代码
int partition(int l, int r) {
int k = a[l];
while (l < r) {
while (l < r && a[r] >= k) r--;
a[l] = a[r];
while (l < r && a[l] <= k) l++;
a[r] = a[l];
}
a[l] = k;
return l;
}
void quicksort(int l, int r) {
if (l < r) {
int pivot = partition(l, r);
cout<<endl;
quicksort(l, pivot - 1);
quicksort(pivot + 1, r);
}
}
归并排序
- 代码： 用sort模拟
void mergesort() {
for (int i = 2; i <= len;) {
for (int j = 0; j < len; j += i) {
int t = min(j + i, len);
sort(a + j, a + t);
}
if (i < len) i = min(2 * i, len);
else break;
}
}
2. 结构体排序
结构体数组，结构体向量排序
对sort的使用
该考点比较简单，是题目的考察点之一， 但往往不是解题的难点和关键点
