第一题：快速排序
这个题目很简单就是对一段长为n的数组，对其进行从小到大的排序后并输出以可。
输入格式：
输入共两行，第一行包含整数 n。 第二行包含 数列中的n 个整数。
输出格式：
输出排序后的结果
数据范围：
1≤n≤1000001≤n≤100000
输入样例：
5 7 2 3 8 10
输出样例：
2 3 7 8 10
讲解：
这就是一个经典的快速排序题，当然你也可以用其他方法，不过我们今天学习的是快排，那就希望大家可以使用快速排序写，这个题目目的很明确，就是进行排序就行，所以我们就在主函数中对他需要的数字进行输入，然后调用我们之前所说的模板就行，大家可以先自己尝试以下，如果解决不了就看一下我下面的AC代码，代码也有讲解，希望你看过之后可以知道为啥自己没写出来的原因。
AC代码：
#include <iostream> using namespace std ; const int N = 100010 ; int a[N] ; void quick_sort(int a[], int l, int r) { if(l>=r) return ; //数组中所含元素为一个或零个时返回 int i = l-1 ; int j = r+1 ; int x = a[l+r>>1] ; /* 这里对左边下标减一以及右边下标加一是为了后面do while语句的执行 因为刚开始都要i++ j-- 所以我们在开始定义的时候就直接先减去， 等后面第一步i++ j--时正好可以从左右两端坐标开始 也不耽误循环的进行 */ while(i<j) //两指针相遇就退出循环 { do i++ ; while(a[i] < x) ; //指针的移动 do j-- ; while(a[j] > x) ; //指针的移动 if(i<j) swap(a[i], a[j]) ; //交换 } quick_sort(a, l, j) ; //递归进行 quick_sort(a, j+1, r) ; } int main() { //按照题目输入 int n ; cin >> n ; for(int i=0 ; i<n; i++) { cin >> a[i] ; } quick_sort(a, 0, n-1) ; //调用模板 for(int i=0; i<n; i++) { cout << a[i] << " " ; } return 0 ; }
第二题：求第 k 小的数
题目描述
输入 n（1 <= n < 5000000）个数字 ai（1 <= ai < 10^9），输出这些数字的第 k 小的数。最小的数是第 0 小。
输入格式
无
输出格式
无
样例
样例输入
5 1 4 3 2 1 5
样例输出
2
讲解：
这个题就是一个小变式了，其实百变不离其总，也是要先对其进行排序，然后从前往后寻找就可以啦。
AC代码：
#include <iostream> using namespace std ; const int N = 5000010 ; int a[N] ; void quick_sort(int a[], int l, int r) { int x = a[l+r>>1] ; int i = l-1 ; int j = r+1 ; if(l>=r) return ; while(i<j) { do i++ ; while(x>a[i]) ; do j-- ; while(x<a[j]) ; if(i<j) swap(a[i],a[j]) ; } quick_sort(a,l,j) ; quick_sort(a,j+1,r) ; } int main() { int n, k ; cin >> n >> k ; for(int i=0; i<n; i++) { cin >> a[i] ; } quick_sort(a, 0, n-1) ; cout << a[k] << endl ; return 0 ; }
显而易见，这个代码也就是第一题代码的一个小变形，把输出变一下就行，所以就不做讲解了。
结尾
好的，到这里我们今天的算法学习就到了尾声，不过大家以后一点要多复习，不让会遗忘的而且模板也要多敲几遍，加深自己的印象。
