常见排序算法
目录
警告
本文最后更新于 2023-04-03，文中内容可能已过时，请谨慎使用。
快速排序
算法流程:
- 确定分界点x，一般取中间点
- 调整区间，第一个区间小于等于分界点，第二个区间大于等于分界点
- 递归处理两个区间使其有序
重点在于第2步：
设置两个指针i和j，如果当前值小于分界点x，则指针i往右移动，否则停止换j移动；
如果j指向的位置的值大于分界点x，则往左移动，否则停止移动；
如果i<j,交换两个指针指向的数据，同时i往右移动一格，j往左移动一格；
重复上述流程，直到i>=j
快速排序是不稳定的
时间复杂度: $O(nlogn)$
// 使用j来划分区间
void quick_sort(int q[], int l, int r) {
if ( l >= r ) return;
// 这里i，j不等于l,r是因为下面i和j最开始都会先移动一格
int i = l - 1, j = r + 1, x = q[(l+r) >> 1];
while (i < j) {
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i<j) swap(q[i],q[j]);
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
或者
// 使用i来划分区间
void quick_sort_i(int q[], int l, int r) {
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[(l+r+1) >> 1]; // x取值也要改
while (i < j) {
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) {
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
quick_sort(q,l,i-1); // 使用i来分割区间
quick_sort(q,i,r);
}
归并排序
时间复杂度: $O(nlogn)$
- 确定分界点：
mid = (l+r) / 2; - 递归排序划分后的子数组
- 归并子数组(双指针)
void merge_sort(int q[], int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1; // 取分界点
merge_sort(q,l,mid); // 递归排序左边
merge_sort(q,mid + 1,r); // 递归排序右边
// 归并上面的两个子数组
int k = 0, i = l, j = mid + 1; // k表示排序好的元素个数,i,j分别指向两个子数组的开始下标
while (i <= mid && j <= r) {
if (q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
// 哪个子数组没走完，将剩余数据加入中间数组
while (i <= mid) {
tmp[k++] = q[i++];
}
while (j <= r) {
tmp[k++] = q[j++];
}
// 将temp[]中的数,依次赋值回原来的数组q[]
for (int i = l, j = 0; i <= r; i++, j++){
q[i] = tmp[j];
}
}
冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
void bubble_sort(int q[], int l, int r) {
for (int i = l; i <= r; i++) {
for (int j = i + 1; j <= r; j++) {
if (q[i] > q[j]) {
int tmp = q[i];
q[i] = q[j];
q[j] = tmp;
}
}
}
}
