快速排序
算法模板
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;//区间里元素个数为一个或没有时
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);
}
x = q[l + r >> 1]代码的作用是选择中间位置的元素作为pivot,用来对数组进行划分。其中 l + r >> 1 是为了找到中间位置的索引。在这里,l + r 是数组的起始位置和结束位置之和,>> 1 是右移一位操作,相当于除以2,所以 l + r >> 1 就是中间位置的索引。这样选择中间位置的元素作为pivot可以尽量保持左右两侧元素的平衡,有助于快速排序的效率。
注意:递归时如果用quick_sort(q, l, j), quick_sort(q, j + 1, r)的话x=q[r]不可用 用quick_sort(q, l, i-1), quick_sort(q, i, r)的话x=q[l]不可用 (这样会没边界 无限递归下去 陷入死循环)
问题1:结束条件能否写成l == r?
答案是可以的,这里是个人习惯问题,写成l==r或l>=r都是没问题的
问题2:while(q[i]<x)和while(q[i]>x)这里能否写成while(q[i]<=x)和while(q[i]>=x)?
答案:不能;我们来想一种很特殊的情况,假设数字全部相等,i会一直往右走,i会自增到r+1,继续执行q[i]<x就会造成下标越界.假设你数组开的足够长,这里不会报错,但是会一直循环下去,造成内存超限制
问题3:最后一句能否改用quick_sort(q, l, j-1), quick_sort(q, j, r)?
答案:不能;当mid不加1时,区间划分为:L~ mid和mid+1~ R,反之L~ mid-1和mid~ R。
换而言之,知道什么时候mid+1就能推算出区间划分。
+1时,向上取整,是为了mid不取到左边界,什么时候不能取左边界?用左边界划分时
同理用右边界划分时不能取到右边界,故此向下取整
根据上面的推论,当x = q[l + r >> 1]时即mid向下取整了,那么就不能选取i作为边界 因此边界为L~ j和j+1~R
注意quick_sort(q, l, j-1), quick_sort(q, j, r)可能会造成无线划分
这里的边界思想二分法也要用到,所以务必掌握
现在用 i 做划分写一下代码
void quick_sort(int q[], int l, int r)
{
if(l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r + 1 >> 1];//注意是向上取整,因为向下取整可能使得x取到q[l]
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, i - 1), quick_sort(q, i, r);//这里是向上取整,避免取到左边界,以左边界划分
}
模板题 快速排序
题目
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在 1∼10^9 范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
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);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
求第 k 小的数
题目描述
输入n ( n < 5000000 且 n 为 奇 数 ) 个 数 字 ai ( 0 < ai < 109 ),输出这些数字的第k小的数。最小的数是第0小。
请尽量不要使用 nth_element 来写本题,因为本题的重点在于练习分治算法。
输入样例
5 1
4 3 2 样例1 5
输出
2
易错:1.用常规的排序方法会因为数据量过大而超时 注意到只需要输出第k小的数,所以可以采用分治的思想
2.由于本题最小的数为第0个数,所以第k小的数为第k+1个数
#include <iostream>
using namespace std;
const int N=5001000;
int n,k;
int q[N];
int quick_sort(int l,int r,int k)
{
if(l==r)return q[l];//直接返回要找的数
int x=q[l+r>>1],i=l-1,j=r+1;
while(i<j)
{
while(q[++i]<x);
while(q[--j]>x);
if(i<j)swap(q[i],q[j]);
}
int sl=j-l+1;//快排每次将数组分为两块,左边为l到j,右边为j+1到r
if(k<=sl)return quick_sort(l,j,k);//要找的数在左边
else return quick_sort(j+1,r,k-sl);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//这行代码是用来提高输入输出效率的,去掉之后程序的输入输出效率会降低,不会影响程序的功能。所以即使去掉这行代码,程序仍然可以正常运行,只是可能在处理大量输入输出数据时会变得比较慢。
cin>> n>> k;
for(int i=0;i<n;i++)
{
cin>>q[i];
}
cout<<quick_sort(0,n-1,k+1)<<endl;//直接输出答案
//endl是用来在输出后添加一个换行符的操作符,使得输出结果后立即换行。没有加endl输出结果后不会换行,后续输出的内容将紧跟在后面。
return 0;
}
除了分治思想和排序模板以外,我们还可以学会:sort和nth_element。
sort(first,last,cmp)对[first,last)范围内的数据进行排序。
在头文件< algorithm >中,cmp表示排序规则,可省略,默认为升序排序
bool cmp(变量类型 a,变量类型 b)
{
if(xxx)return 1;//如果返回值为真,则为sort里面的“小于”(sort函数为非降序排序)
例:return a>b;(将较大的数据放在前面,因为如果a>b,则返回值为真,符合sort的“小于”)
}
nth_elment(first ,last)在头文件< algorithm >中,默认为升序排序。
当采用默认的排序规则时,该函数可以从某个序列中找到第 n 小的元素 K,并将 K 移动到序列中第 n 的位置处。除此之外,整个序列经过 nth_element() 函数处理后,所有位于 K 之前的元素都比 K 小,所有位于 K 之后的元素都比 K 大。
nth_element(x,x+k,x+n,cmp)
//在[x,x+n)中寻找第k小的数(最小为1)。cmp可省略。
法二代码
#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
int main()
{
int n;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&x[i]);
nth_element(x,x+k,x+n);
printf("%d",x[k]);
}
归并排序
何谓归并排序,先看下面一个例子:
设有数列{6,100,38,202,100,301,38,8,1}
初始状态:{6},{100},{38},{202},{100},{301},{38},{8},{1}
第一次归并后:{6,100},{38,202},{100,301},{8,38},{1};
第二次归并后:{6,38,100,202},{8,38,100,301},{1};
第三次归并后:{6,8,38,38,100,100,202,301},{1};
第四次归并后:{1,6,8,38,38,100,100,202,301}
最终结果得出:{1,6,8,38,38,100,100,202,301}
归并排序的关键在于合并两个有序序列的步骤,这一步需要线性时间复杂度。因此,整个归并排序算法的时间复杂度为O(n log n)。归并排序是一种稳定且高效的排序算法,它的最坏、最好、平均时间复杂度均为O(nlogn),是一种稳定排序的算法。一般按照三步走:
1.划分问题:把序列分成元素个数尽量相等的两个序列
2.递归求解:对两个序列分别排序
3.合并问题:把两个有序序列合并为一个序列
归并排序是一种稳定的排序方法:在合并两个有序序列时,若左边序列中有元素与右边序列中某个元素相等,这时只需将左边序列的元素填充至辅助数组并将指针后移,右边指针不动,即可保证排序的稳定性。
算法模板
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;
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 ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
为什么不用 mid - 1 作为分隔线呢?即 merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r)
因为 mid = l + r >> 1 是向下取整,mid 有可能取到 l (数组只有两个数时),造成无限划分
解决办法: mid 向上取整就可以了, 即 mid = l + r + 1 >> 1,如下所示:
void merge_sort(int q[], int l, int r)
{
if(l >= r) return;
int mid = l + r + 1>> 1;
merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r);
int k = 0, i = l, j = mid;
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++];
for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}
模板题 归并排序
题目
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在 1∼1091∼109 范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l,int r) {
if(l >= r)return ; //递归的终止情况
//第一步:分成子问题
int mid = l + r >> 1; //注意mid是向上取整
//第二步:递归处理子问题
merge_sort(nums, l, mid);
merge_sort(nums, mid + 1, r);
//第三步:合并子问题
int k = 0, i = l,j = mid + 1;
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 ++];
for (int i = 0, j = l;j <= r; i++, j++) q[j] = tmp[i];
}
int main(){
int n;
scanf("%d", &n);
while (int i = 0; i < n; i++) scanf("%d", &q[i]);
merge_sort(q, 0, n - 1);
while (int i = 0; i < n; i++) printf("%d", q[i]);
return 0;
}
逆序对
题目
给定一个长度为 n 的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i个和第 j个元素,如果满足 i<j 且 a[i]>a[j],则其为一个逆序对;否则不是。
输入格式
第一行包含整数 n,表示数列的长度。
第二行包含 n个整数,表示整个数列。
输出格式
输出一个整数,表示逆序对的个数。
数据范围
1≤n≤100000,
数列中的元素的取值范围 [1,1e9]。
输入样例
6
2 3 4 5 6 1
输出样例
5
求序列的逆序对,先看下面的例子:
设有数列{6,100,38,202,100,301,38,8,1}
初始状态:{6},{100},{38},{202},{100},{301},{38},{8},{1}
第一次归并后:{6,100},{38,202},{100,301},{8,38},{1};比较次数:4,逆序对数:1
第二次归并后:{6,38,100,202},{8,38,100,301},{1};比较次数:5,逆序对数:5
第三次归并后:{6,8,38,38,100,100,202,301},{1};比较次数:6,逆序对数:6
第四次归并后:{1,6,8,38,38,100,100,202,301}:比较次数:1,逆序对数:8
总的比较次数为:4+5+6+1=16 逆序对数目为:1+5+6+8 = 20
根据归并排序的特性(左右两部分的有序序列合并时,假设i在左边,j在右边,对于右边的j,统计左边比它大的元素个数f(j),则f(j) = mid-i+1 ,合并完所有的序列时即可得出答案,即f(j)之和便是答案),只需将上面的代码修改一处:把“else tmp[k++] = q[j++];”改成“ else {tmp[k++] = q[j++]; cnt += mid-p+1;}" ,注意在调用之前将cnt清零。
#include<iostream>
using namespace std;
#define N 500010
int q[N], tmp[N];
long long res;
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;
while (i <= mid && j <= r) {
if (q[i] <= q[j]) tmp[k++] = q[i++];
else {
tmp[k++] = q[j++];
res += mid - i + 1;
}
}
while (i <= mid)tmp[k++] = q[i++];
while (j <= r)tmp[k++] = q[j++];
for (int i = l, j = 0; i <= r; i++, j++)
q[i] = tmp[j];
}
int main()
{
int n;
cin >> n;
for(int i = 0 ; i<n; i ++)
cin >> q[i];
res = 0;
merge_sort(q,0,n-1);
cout << res <<endl;
return 0;
}