PAT 排序算法
...约 550 字大约 2 分钟
PAT 排序算法
PAT甲级题目整理
交换排序
冒泡排序
void bubble_sort() {
for (int i = 1; i < n; ++i) {
bool did_swap = false;
for (int j = 0; j < n - i; ++j) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j+1]);
did_swap = true;
}
}
if (!did_swap) return;
}
}
快速排序
void quick_sort(int left, int right) {
if (left >= right) return;
int i = left - 1, j = right + 1, x = a[left + right >> 1];
while (i < j) {
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
}
quick_sort(left, j);
quick_sort(j + 1, right);
}
选择排序
直接选择排序
void select_sort() {
for (int i = 0; i < n; ++i) {
int min = i;
for (int j = i + 1; j < n; ++j) {
if (a[j] < a[min]) min = j;
}
swap(a[i], a[min]);
}
}
堆排序
void down_adjust(int low, int high) {
int i = low, j = 2 * low;
while (j <= high) {
if (j + 1 <= hgih && a[j + 1] > a[j]) j++;
if (a[i] < a[j]) {
swap(a[i], a[j]);
i = j;
j = 2 * i;
} else break;
}
}
//插入时需要向上调整,数组从1开始
void up_adjust(int low, int high) {
int i = high, j = high / 2;
while (j >= low) {
if (a[i] > a[j]) {
swap(a[i], a[j]);
i = j;
j = i / 2;
} else break;
}
}
void create() {
for (int i = n / 2; i > 0; --i) {
down_adjust(i, n);
}
}
void heap_sort() {
for (int i = n; i > 0; --i) {
swap(a[i], a[1]);
down_adjust(1, i - 1);
}
}
插入排序
直接插入排序
void insert_sort() {
for (int i = 1; i < n; ++i) {
int j = i, temp = a[i];
while (j && a[j - 1] > temp) {
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}
}
希尔排序
void shell_sort() {
for (int gap = n / 2; gap >= 1; gap /= 2) {
for (int i = gap; i < n; ++i) {
int j = i, temp = a[i];
while (j - gap >= 0 && a[j - gap] > temp) {
a[j] = a[j - gap];
j -= gap;
}
a[j] = temp;
}
}
}
归并排序
void merge_sort(int left, int right) {
if (left >= right) return;
int mid = left + right >> 1;
merge_sort(left, mid);
merge_sort(mid + 1, right);
int k = 0, i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (a[i] < a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= right) tmp[k++] = a[j++];
for (i = 0; i < k; ++i) a[left + i] = tmp[i];
}
基数排序(不是基于比较的排序)
拓扑排序
vector<int> adj[MAX];
int n, indegree[MAX];
int topological_sort() {
queue<int> q;
for (int i = 0; i < n; ++i) {
if (indegree[i] == 0) {
q.push(i);
}
}
int num = 0;
while (q.size()) {
int u = q.front();
q.pop();
num++;
for (int v = 0; v < adj[u].size(); ++v) {
if (--indegree[v] == 0) q.push(v);
}
}
if (num == n) return 1;
else return -1;
}
Powered by Waline v2.15.5