排序題目主要有以下兩種考察形式
1. 手撕經(jīng)典排序算法
判斷時什么排序年柠， 運(yùn)用排序算法進(jìn)行下一輪排序
直接插入排序（insertion sort）
特點：前n個有序，后半部分與原序列相同
-
代碼（用sort函數(shù)模擬）
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]);
}
}
堆排序
- 數(shù)組從0開始編號和從1開始編號會影響代碼，此處為從1開始編號：堆中，父節(jié)點為i， 左兒子為2 * i+1, 右兒子為2* i+2誊薄；堆的最后一個節(jié)點編號為len - 1, 最后一個節(jié)點的父節(jié)點為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. 結(jié)構(gòu)體排序
結(jié)構(gòu)體數(shù)組，結(jié)構(gòu)體向量排序
對sort的使用
該考點比較簡單锰茉，是題目的考察點之一呢蔫， 但往往不是解題的難點和關(guān)鍵點
