在程序设计中通常会用到以下排序：
1.选择排序、插入排序、冒泡排序
2.堆排序、归并排序、快速排序
3.计数排序、基数排序、桶排序
前两类排序时基于比较的排序，第一类排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，第二类排序的时间复杂度为 O ( n l o n g n ) 。 O(nlongn)。 O(nlongn)。第三类排序不直接比较大小，而是对被排序的数值按照位划分，分类映射等处理方式，其时间复杂度不仅与n有关，还与数值的大小范围m有关。
离散化
假设问题涉及int范围内的n个整数a[1]-a[n],这n个整数可能重复，去重后共有m个。我们要把每个整数用1-m中的整数代替，并且保证大小顺序不变。
void discrete()
{
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
if(i==1||a[i]!=a[i-1])
b[++m]=a[i];
}
}
int query(int x)
{
return lower_bound(b+1.b+m+1,x)-b;
}
例题
acwing103.电影
将2*m+n个可能涉及到的语言存到数组中，并进行离散化处理。对于每一种语言对应观众的数量进行计数。挨个看每一个电影对应的高兴和比较高兴的观众的数量，选择出最优的。
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_N 200000
int all[MAX_N*3+5];
int a[MAX_N+5];
int b1[MAX_N+5],b2[MAX_N+5];
int l[MAX_N*3+5];
int cnt[MAX_N+5];
int score1[MAX_N+5],score2[MAX_N+5];
int r=0,q=0;
int n,m;
int query(int x)
{
return lower_bound(l+1,l+q+1,x)-l;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
all[++r]=a[i];
}
cin>>m;
for(int i=1;i<=m;i++)
{
scanf("%d",b1+i);
all[++r]=b1[i];
}
for(int i=1;i<=m;i++)
{
scanf("%d",b2+i);
all[++r]=b2[i];
}
sort(all+1,all+r+1);
for(int i=1;i<=n+2*m;i++)
{
if(i==1||all[i]!=all[i-1])
l[++q]=all[i];
}
for(int i=1;i<=n;i++)
{
int x=query(a[i]);
cnt[x]+=1;
}
int t1=-1,t2=-1,t3;
for(int i=1;i<=m;i++)
{
int s1=cnt[query(b1[i])];
int s2=cnt[query(b2[i])];
if(s1>t1||(s1==t1&&s2>t2))
{
t3=i;
t1=s1;
t2=s2;
}
}
cout<<t3;
return 0;
}
中位数
在有序序列中，中位数有一些优美的性质，可以引出一系列与他相关的问题。动态维护中位数也非常值得探讨。
在N为奇数时，货仓建在A[(N+1)/2];
在N为偶数时，货仓建在A[N/2]~A[N/2+1]。
因此不论哪种情况建在A[(N+1)/2]为最优。
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_N 100000
int n;
int a[MAX_N+5];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",a+i);
sort(a+1,a+n+1);
int t=a[(n+1)/2];
int ans=0;
for(int i=1;i<=n;i++)
ans+=abs(a[i]-t);
cout<<ans;
return 0;
}
交换左右两个相邻摊点只会改变某两列cl感兴趣的摊点数，交换上下只会改变某两行感兴趣的摊点数，所以可以把本题分成两个部分。
1.通过最少次数的左右交换使每列中cl感兴趣的摊点数相同。
2.通过最少次数的上下交换使每行中cl感兴趣的摊点数相同。
经计算
∣
x
1
∣
+
∣
x
2
∣
+
.
.
.
+
∣
x
n
∣
=
∣
x
1
−
c
1
∣
+
∣
x
2
−
c
2
∣
+
∣
x
n
−
c
n
∣
。其中
c
k
=
(
k
−
1
)
∗
∑
i
=
1
k
−
1
a
i
+
(
k
−
1
)
∗
a
(
a
为平均数
)
|x1|+|x2|+...+|xn|=|x1-c1|+|x2-c2|+|xn-cn|。其中ck=(k-1)*\sum\limits_{i=1}^{k-1}ai+(k-1)*a(a为平均数)
∣x1∣+∣x2∣+...+∣xn∣=∣x1−c1∣+∣x2−c2∣+∣xn−cn∣。其中ck=(k−1)∗i=1∑k−1ai+(k−1)∗a(a为平均数)因此可以把该问题转化为“货仓选址”。
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_N 100000
int n,m,t;
int row[MAX_N+5],col[MAX_N+5];
int sum[MAX_N+5];
int c[MAX_N+5];
long long solve(int l,int*a)
{
if(t%l)return -1;
int avg=t/l;
for(int i=1;i<=l;i++)
{
sum[i]=sum[i-1]+a[i];
c[i]=(i-1)*avg-sum[i-1];
}
for(int i=1;i<=l;i++)
{
c[i]=(i-1)*avg-sum[i-1];
}
sort(c+1,c+l+1);
int p=c[(l+1)/2];
long long ans=0;
for(int i=1;i<=l;i++)
ans+=1ll*abs(c[i]-p);
return ans;
}
int main()
{
cin>>n>>m>>t;
for(int i=1,x,y;i<=t;i++)
{
scanf("%d%d",&x,&y);
row[x]++;
col[y]++;
}
long long q1=solve(n,row);
long long q2=solve(m,col);
if(q1==-1&&q2==-1)
cout<<"impossible";
else if(q1==-1)
cout<<"column"<<" "<<q2;
else if(q2==-1)
cout<<"row"<<" "<<q1;
else cout<<"both"<<" "<<q1+q2;
return 0;
}
使用一个大顶堆和一个小顶堆。序列从小到大排名1~M/2存到大顶堆，M/2+1~M的存在小顶堆。
#include<iostream>
#include<queue>
using namespace std;
#define MAX_N 100000
int t;
int arr[MAX_N+5];
int main()
{
cin>>t;
while(t--)
{
int id,m,cnt=0;
scanf("%d %d",&id,&m);
printf("%d %d\n",id,(m+1)/2);
priority_queue<int>down;
priority_queue<int,vector<int>,greater<int>>up;
for(int i=1,x;i<=m;i++)
{
scanf("%d",&x);
if(down.size()==0||x<down.top())down.push(x);
else up.push(x);
if(down.size()>up.size()+1)up.push(down.top()),down.pop();
if(up.size()>down.size())down.push(up.top()),up.pop();
if(i%2)
{
printf("%d ",down.top());
if(++cnt%10==0)printf("\n");
}
}
if(cnt%10)printf("\n");
}
return 0;
}
第K大数
给定n个数，如何求出第k大数？
从大到小进行快速排序的思想是，在每一层递归中，随机选取一个数为基准，把比它大的交换到左半段，其余的和基准值自身一起作为右半段，然后继续递归对两边分别排序，平均情况下快速排序的复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。
实际上在选出来基准值之后，我们可以统计处大于基准值的数的数量cnt，如
k
≤
c
n
t
k\leq cnt
k≤cnt，我们就在左半边寻找第k大数；如果k>cnt,我们就在右半边寻找第k-cnt大数。在平均情况下，时间复杂度是
n
+
n
/
2
+
n
/
4
+
.
.
.
+
1
=
O
(
n
)
n+n/2+n/4+...+1=O(n)
n+n/2+n/4+...+1=O(n)。
逆序对
使用归并排序可以在 O ( l o g n ) O(logn) O(logn)时间内求出来一个长度为n的序列中逆序对的个数。归并排序每次把序列二分，递归对左右两个半边排序，然后合并两个序列。
#include<iostream>
using namespace std;
#define MAX_N 500000
long long a[MAX_N+5],t[MAX_N+5];
long long merge_sort(int l,int r)
{
if(l==r)return 0;
int mid=l+r>>1;
long long ret=merge_sort(l,mid)+merge_sort(mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])t[++k]=a[i++];
else if(a[i]>a[j])
{
ret+=(mid-i+1);
t[++k]=a[j++];
}
}
while(i<=mid)t[++k]=a[i++];
while(j<=r)t[++k]=a[j++];
for(int i=l,j=1;i<=r;i++,j++)a[i]=t[j];
return ret;
}
int main()
{
int n;
while(scanf("%d",&n),n)
{
for(int i=1;i<=n;i++)
scanf("%lld",a+i);
printf("%lld\n",merge_sort(1,n));
}
return 0;
}
对于n为奇数的情况，两个局面可相互到达等价于把各个方格的数依次写成一行，逆序对个数奇偶性相同。
对于n为偶数地情况，两个局面可相互到达等价于把各个方格的数依次写成一行，逆序对个数奇之差和两个局面下空格所在的行数之差奇偶性相同。
在n*m网格上，也服从上面两个结论之一（根据列数奇偶性分类讨论）。
#include<iostream>
using namespace std;
#define MAX_N 500
int arr[MAX_N*MAX_N+5];
int t[MAX_N*MAX_N+5];
long long merge(int l,int r)
{
if(l==r)return 0;
int mid=(l+r)>>1;
int i=l,j=mid+1,k=0;
long long res=merge(l,mid)+merge(mid+1,r);
while(i<=mid&&j<=r)
{
if(arr[i]<=arr[j])t[++k]=arr[i++];
else{
res+=(mid-i+1);
t[++k]=arr[j++];
}
}
while(i<=mid)t[++k]=arr[i++];
while(j<=r)t[++k]=arr[j++];
for(int i=l,j=1;i<=r;i++,j++)
arr[i]=t[j];
return res;
}
int main()
{
int n,a;
while(scanf("%d",&n)!=EOF)
{
int cnt=0;
if(n==1)
{
scanf("%d%d",&a,&a);
printf("TAK\n");
continue;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&a);
if(a==0)continue;
arr[++cnt]=a;
}
long long q1=merge(1,cnt);
cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&a);
if(a==0)continue;
arr[++cnt]=a;
}
long long q2=merge(1,cnt);
if((q1&1)==(q2&1))printf("TAK\n");
else printf("NIE\n");
}
return 0;
}