1、快速排序
Description
实现快速排序算法。
Input
输入第一行是一个整数n，表示待排序的元素个数。之后有n个整数，是待排序的元素。例如：106 8 9 2 5 1 0 3 7 4
Output
每次选择待排序数组中第1个元素作为基准元素，不使用Median3函数选择基准元素，当元素数量较少时不使用简单排序算法。在程序中设置一个全局变量，Qsort函数每次被调用都使该全局变量增1。排序完成后先输出全局变量的值，然后换行输出排序后的数组，元素之间有1个空格，最后一个元素之后也有1个空格。例如，对于上面的示例输入，输出为：150 1 2 3 4 5 6 7 8 9
Sample Input 1
10
6 8 9 2 5 1 0 3 7 4
Sample Output 1
15
0 1 2 3 4 5 6 7 8 9
Sample Input 2
2
5 3
Sample Output 2
3
3 5
Sample Input 3
8
1 2 3 4 5 6 7 8
Sample Output 3
15
1 2 3 4 5 6 7 8
Sample Input 4
10
1 2 3 1 2 3 1 2 3 1
Sample Output 4
11
1 1 1 1 2 2 2 3 3 3
Sample Input 5
20
32 78 1 76 153 988 87 2 999 433 100 65 91 101 102 876 222 6 23 12
Sample Output 5
27
1 2 6 12 23 32 65 76 78 87 91 100 101 102 153 222 433 876 988 999
2、归并排序
Description
实现归并排序算法。
Input
输入第一行是一个整数n，表示待排序的元素个数。之后有n个整数，是待排序的元素。例如：106 8 9 2 5 1 0 3 7 4
Output
在程序中设置一个全局变量，Msort函数每次被调用都使该全局变量增1。排序完成后先输出全局变量的值，然后换行输出排序后的数组，元素之间有1个空格，最后一个元素之后也有1个空格。例如，对于上面的示例输入，输出为：190 1 2 3 4 5 6 7 8 9
Sample Input 1
8
8 7 6 5 4 3 2 1
Sample Output 1
15
1 2 3 4 5 6 7 8
Sample Input 2
20
32 78 1 76 153 988 87 2 999 433 100 65 91 101 102 876 222 6 23 12
Sample Output 2
39
1 2 6 12 23 32 65 76 78 87 91 100 101 102 153 222 433 876 988 999
Sample Input 3
2
5 3
Sample Output 3
3
3 5