详解冒泡排序和快速排序
一般而言，竞赛所给的题目一般都会有多种的解法，它考核的是再限定的时间和空间内解决问题。
如果条件很宽松，那么可以在多种解法中选择一个最容易编程的算法；如果给的条件比较苛刻，那么能选择的合适算法就不多了。
下面使用一个例子来说明同样的问题如何选择不同的算法。
给出 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）然后以基准数为中心，将原数组分为左右两部分，分别对这两部分重复以上两个过程，直到得到每个子集中只有一个元素为止。
————————————————
版权声明：本文为CSDN博主「京茶吉鹿」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_52372879/article/details/122277461
