详解冒泡排序和快速排序
一般而言，竞赛所给的题目一般都会有多种的解法，它考核的是再限定的时间和空间内解决问题。
如果条件很宽松，那么可以在多种解法中选择一个最容易编程的算法；如果给的条件比较苛刻，那么能选择的合适算法就不多了。
下面使用一个例子来说明同样的问题如何选择不同的算法。
给出 n 个整数,请按从大到小的顺序输出其中前 m 大的数。
输入：每组测试数据有两行,第1行有两个数 n 和 m (0< n , m <1000000),第2行包含 n 个各不相同,且都处于区
间[-500000,500000]的整数。
输出：对每组測试数据接从大到小的顺序输出前大的数。
输入样例：
5 3
3 -35 92 213 -644
输出样例：
213 92 3
该题的思路是先对 100 万个数排序，然后输出前m大的数字。题目给出了代码运行时间，非Java语言的时间为 1s，内存为 32MB。
下面分别用冒泡排序、快速排序 2 种算法编程。
- 1、冒泡排序
首先用最简单的冒泡算法求解上面的问题。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int n,m;
int s[1000001];
void bubble_sort() {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n - i - 1; j++)
if (s[j] > s[j + 1]){
int temp = s[j];
s[j] = s[j + 1];
s[j + 1] = temp;
}
}
}
int main() {
while (~scanf("%d %d",&n,&m)){
for (int i = 0; i < n;i++) scanf("%d", &s[i]);
bubble_sort();
for (int i = n-1; i >= n-m;i--) {
printf("%d ", s[i]);
}
}
return 0;
}
在bubble_sort()运行后，得到从小到大的排序结果，然后从后往前打印前m大的数字。
冒泡排序算法的步骤如下：
（1） 第一轮，从第 1 个数到第 n 个数，逐个对比两个每相邻的 s[ j ]、s[ j + 1 ]，如果 s[ j ] > s[ j + 1 ]，则交换。这一
轮的结果是把最大的数 “冒泡” 到了第 n 个位置，在后面不用再管它。
（2）第二轮，从第 1 个数到第 n - 1 个数，对比每相邻的数。这一轮，把第 二大的数 “冒泡” 到了第 n - 1个位置。
（3）继续以上过程，直至结束。
- 2、快速排序
快速排序是一种基于分治法的优秀排序算法。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int n, m;
int s[1000001];
void quick_sort(int s[],int L,int R) {
int left = L, right = R;
int flag = s[left];
if (L > R) return;
while (left < right) {
while (s[right] >= flag && left < right) right--;
if (left < right) {
int temp = s[right];
s[right] = s[left];
s[left] = temp;
};
while (s[left] <= flag && left < right) left ++;
if (left < right) {
int temp = s[right];
s[right] = s[left];
s[left] = temp;
};
if (left >= right) s[left] = flag;
}
quick_sort(s,L,right - 1);
quick_sort(s,right + 1,R);
}
int main() {
while (~scanf("%d %d", &n, &m)) {
for (int i = 0; i < n; i++) scanf("%d", &s[i]);
quick_sort(s,0,n-1);
for (int i = n - 1; i >= n - m; i--) {
printf("%d ", s[i]);
}
}
return 0;
}
在quick_sort()运行后，得到从小到大的排序结果，然后从后往前打印前m大的数字。
快速排序算法的步骤如下：
（1）先选取一个基准数 flag，一般选择第一个元素作为基准数。
（2）将数组中小于基准数的数字放在基准数左边，数组种大于基准数的数字放在基准数右边。
（3）然后以基准数为中心，将原数组分为左右两部分，分别对这两部分重复以上两个过程，直到得到每个子集中只有一个元素为止。
