姓名： 李明基
赛道： 基础组
类型： 算法技能
排序
关键词： 排序
冒泡排序
它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
经过 i 次扫描后，数列的末尾 i 项必然是最大的 i 项，因此冒泡排序最多需要扫描 n-1 遍数组就能完成排序。
冒泡排序是一种稳定的算法，平均时间复杂度为 O(n^2) 。
代码：
void bubble_sort(int *a, int n) {
bool flag = true;
while (flag) {
flag = false;
for (int i = 1; i < n; ++i) {
if (a[i] > a[i + 1]) {
flag = true;
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
}
选择排序
它的工作原理是每次找出第 i 小的元素（也就是 A[i]…A[n] 中最小的元素），然后将这个元素与数组第 i 个位置上的元素交换。
选择排序是一种不稳定的排序，不过最优、最差复杂度均为 O(n^2) 。
代码：
void selection_sort(int* a, int n) {
for (int i = 1; i < n; ++i) {
int ith = i;
for (int j = i + 1; j <= n; ++j) {
if (a[j] < a[ith]) {
ith = j;
}
}
swap(a[i], a[ith]);
}
}
桶排序
这是一种较简便的排序。
它的工作原理如下：
- 设置一个定量的数组当作空桶；
- 遍历序列，并将元素一个个放到对应的桶中；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把元素再放回原来的序列中。
如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法，最坏时间复杂度为 O(n^2) 。
代码：
const int N = 100010;
int n, w, a[N];
vector<int> bucket[N];
void insertion_sort(vector<int>& A) {
for (int i = 1; i < A.size(); ++i) {
int key = A[i];
int j = i - 1;
while (j >= 0 && A[j] > key) {
A[j + 1] = A[j];
--j;
}
A[j + 1] = key;
}
}
void bucket_sort() {
int bucket_size = w / n + 1;
for (int i = 0; i < n; ++i) {
bucket[i].clear();
}
for (int i = 1; i <= n; ++i) {
bucket[a[i] / bucket_size].push_back(a[i]);
}
int p = 0;
for (int i = 0; i < n; ++i) {
insertion_sort(bucket[i]);
for (int j = 0; j < bucket[i].size(); ++j) {
a[++p] = bucket[i][j];
}
}
}
归并排序
归并排序最核心的部分是合并（merge）过程：将两个有序的数组 a[i] 和 b[j] 合并为一个有序数组 c[k]。
从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复上述过程直到 a[i] 和 b[j] 有一个为空时，将另一个数组剩下的元素放入 c[k]。
为保证排序的稳定性，前段首元素小于或等于后段首元素时（a[i] <= b[j]）而非小于时（a[i] < b[j]）就要作为最小值放入 c[k]。
归并排序使用了分治思想，时间复杂度为 O(n log n) 。
代码：
void merge(const int *a, size_t aLen, const int *b, size_t bLen, int *c) {
size_t i = 0, j = 0, k = 0;
while (i < aLen && j < bLen) {
if (b[j] < a[i]) { // <!> 先判断 b[j] < a[i]，保证稳定性
c[k] = b[j];
++j;
} else {
c[k] = a[i];
++i;
}
++k;
}
// 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中
for (; i < aLen; ++i, ++k) c[k] = a[i];
for (; j < bLen; ++j, ++k) c[k] = b[j];
}
如果使用分治法实现，代码如下：
void merge_sort(int *a, int l, int r) {
if (r - l <= 1) return;
// 分解
int mid = l + ((r - l) >> 1);
merge_sort(a, l, mid), merge_sort(a, mid, r);
// 合并
int tmp[1024] = {}; // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用
// vector；先将合并的结果放在 tmp 里，再返回到数组 a
merge(a + l, a + mid, a + mid, a + r, tmp + l); // pointer-style merge
for (int i = l; i < r; ++i) a[i] = tmp[i];
}
如果使用倍增法实现，代码如下：
void merge_sort(int *a, size_t n) {
int tmp[1024] = {}; // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用
// vector；先将合并的结果放在 tmp 里，再返回到数组 a
for (size_t seg = 1; seg < n; seg <<= 1) {
for (size_t left1 = 0; left1 < n - seg;
left1 += seg + seg) { // n - seg: 如果最后只有一个段就不用合并
size_t right1 = left1 + seg;
size_t left2 = right1;
size_t right2 = std::min(left2 + seg, n); // <!> 注意最后一个段的边界
merge(a + left1, a + right1, a + left2, a + right2,
tmp + left1); // pointer-style merge
for (size_t i = left1; i < right2; ++i) a[i] = tmp[i];
}
}
}
快速排序
手写快速排序
快速排序的工作原理是通过 分治 的方式来将一个数组排序。
快速排序分为三个过程：
- 将数列划分为两部分（要求保证相对大小关系）；
- 递归到两个子序列中分别进行快速排序；
- 不用合并，因为此时数列已经完全有序。
和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择一个数 m 来当做两个子数列的分界。
快速排序是一种不稳定的排序算法。
代码：
template <typename T>
int Paritition(T A[], int low, int high) {
int pivot = A[low];
while (low < high) {
while (low < high && pivot <= A[high]) --high;
A[low] = A[high];
while (low < high && A[low] <= pivot) ++low;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
template <typename T>
void QuickSort(T A[], int low, int high) {
if (low < high) {
int pivot = Paritition(A, low, high);
QuickSort(A, low, pivot - 1);
QuickSort(A, pivot + 1, high);
}
}
template <typename T>
void QuickSort(T A[], int len) {
QuickSort(A, 0, len - 1);
}
直接写快速排序
sort(a+1,a+n+1);
排序a数组从下标1到n的数。
参考文献：OI-Wiki
参考代码：OI-Wiki
你这是参考？？？