目录
（一）快速排序（1）题目-求第k个数（2）代码`
（二）归并排序（1）题目-求逆序数对（2）代码
（三）总结
（一）快速排序
（1）题目-求第k个数
给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列从小到大排序后的第k个数。
输入格式 第一行包含两个整数 n 和 k。 第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。
输出格式 输出一个整数，表示数列的第k小数。
数据范围 1≤n≤100000, 1≤k≤n
输入样例：
5 3 2 4 1 5 3
输出样例：
3
（2）代码`
#include<iostream>
using namespace std
;
const int N
=100010;
int q
[N
],k
,n
;
int quick_sort(int l
,int r
,int k
){
if(l
>=r
)return q
[l
];
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
]);
}
int s
=j
-l
+1;
if(k
<=s
) quick_sort(l
,j
,k
);
else quick_sort(j
+1,r
,k
-s
);
}
int main(){
scanf("%d%d",&n
,&k
);
for(int i
=0;i
<n
;i
++)scanf("%d",&q
[i
]);
cout
<<quick_sort(0,n
-1,k
);
}
（二）归并排序
（1）题目-求逆序数对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
输入格式 第一行包含整数n,表示数列的长度。 第二行包含n个整数,表示整个数列。
输出格式 输出一个整数,示逆序对的个数。
数据范围 1≤n≤100000,
输入样例：
6 2 3 4 5 6 1
输出样例：
5
（2）代码
#include<iostream>
using namespace std
;
typedef long long LL
;
const int N
=100010;
int q
[N
],n
,tmp
[N
];
LL
merge_sort(int l
,int r
){
if(l
>=r
)return 0;
int mid
=l
+r
>>1;
LL res
=merge_sort(l
,mid
)+merge_sort(mid
+1,r
);
int i
=l
,j
=mid
+1;
int k
=0;
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
,k
=0;i
<=r
;)q
[i
++]=tmp
[k
++];
return res
;
}
int main(){
scanf("%d",&n
);
for(int i
=0;i
<n
;i
++)scanf("%d",&q
[i
]);
cout
<<merge_sort(0,n
-1);
return 0;
}
（三）总结
1.快速选择算法的时间复杂度为O(N)； 2.[i,j]中数组长度为j-i+1; 3.注意typedef的写法。
若有不正确之处，望大家指正，共同学习！谢谢！！！
本文参考网址
