目录

算法设计与分析——十大经典排序算法

第1关：冒泡排序

 参考代码

第2关：选择排序

参考代码

第3关：插入排序

 参考代码

第4关：希尔排序

参考代码

第5关：归并排序

 参考代码

作者有言

---

一个不知名大学生，江湖人称菜狗
original author: jacky Li
Email : 3435673055@qq.com

Time of completion：2023.2.28
Last edited: 2023.2.28

导读：

帮助算法设计初学者快速掌握算法设计，帮助安静对ABCD……等的重要性排序更清晰！

算法设计与分析——十大经典排序算法

第1关：冒泡排序

任务描述

本关任务：实现冒泡排序算法，并将乱序数列变成升序。

相关知识

为了完成本关任务，你需要掌握：1.冒泡排序算法。

冒泡排序算法

冒泡排序重复地遍历待排序的数列，每次比较两个相邻元素，如果它们的顺序错误就把它们交换。重复地进行遍历直到没有再需要交换时表示数列已经排序完成。

• 算法步骤：
  1. 比较相邻的元素：若第一个比第二个大，则交换；
  2. 遍历开始第一对到结尾最后一对，执行步骤1；
  3. 重复步骤1~2，直到排序完成。
• 可改进的冒泡排序：第一趟排序之后最后一个元素是最大的，因此下一趟遍历只需执行到倒数第二对。

编程要求

本关的编程任务是补全右侧代码片段sort_array中Begin至End中间的代码，具体要求如下：

• 在sort_array中，实现冒泡排序算法，完成指定输出。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：

10

7 1 4 6 8 9 5 2 3 10

预期输出：

1 4 6 7 8 5 2 3 9 10

1 4 6 7 5 2 3 8 9 10

1 4 6 5 2 3 7 8 9 10

1 2 3 4 5 6 7 8 9 10

测试输入：

15

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48

预期输出：

3 38 5 44 15 36 26 27 2 46 4 19 47 48 50

3 5 38 15 36 26 27 2 44 4 19 46 47 48 50

3 5 15 36 26 27 2 38 4 19 44 46 47 48 50

2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

 参考代码

1. #include “sort_.h”
3. void print_array(int *arr, int n)
4. {
5. if(n==0){
6. printf(“ERROR: Array length is ZERO\n”);
7. return;
8. }
9. printf(“%d”, arr[0]);
10. for (int i=1; i<n; i++) {
11. printf(” %d”, arr[i]);
12. }
13. printf(“\n”);
14. }
16. void sort_array(int *arr, int n)
17. {
18. int i, x, j;
19. for(j = 0; j < n; j ++)
20. {
21. for(i = 0; i < n – 1; i ++)
22. {
23. if(arr[i] > arr[i + 1])
24. {
25. x = arr[i];
26. arr[i] = arr[i + 1];
27. arr[i + 1] = x;
28. }
29. }
30. if(j < 3) print_array(arr, n);
31. }
32. print_array(arr, n);
33. }

第2关：选择排序

任务描述

本关任务：实现选择排序算法，并将乱序数列变成升序。

相关知识

为了完成本关任务，你需要掌握：1.选择排序算法。

选择排序算法

选择排序是一种简单直观的排序算法，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 算法步骤：
  1. 初始状态：无序序列为R[0,n−1]，长度n，有序区为空；
  2. 第i=1,..,n−1趟排序从当前无序区R[i−1,n−1]中选出最小的元素R[k]，并将它与无序区的第1个记录R[i−1]交换，则R[0,i−1]变为元素个数增加1的新有序区，R[i,n−1]变为元素个数减少1的新无序区；
  3. n−1趟选择交换后结束。

编程要求

本关的编程任务是补全右侧代码片段sort_array中Begin至End中间的代码，具体要求如下：

• 在sort_array中，实现选择排序算法，完成指定输出。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：

10

7 1 4 6 8 9 5 2 3 10

预期输出：

1 7 4 6 8 9 5 2 3 10

1 2 4 6 8 9 5 7 3 10

1 2 3 6 8 9 5 7 4 10

1 2 3 4 5 6 7 8 9 10

测试输入：

15

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48

预期输出：

2 44 38 5 47 15 36 26 27 3 46 4 19 50 48

2 3 38 5 47 15 36 26 27 44 46 4 19 50 48

2 3 4 5 47 15 36 26 27 44 46 38 19 50 48

2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

参考代码

1. #include “sort_.h”
3. void print_array(int *arr, int n)
4. {
5. if(n==0){
6. printf(“ERROR: Array length is ZERO\n”);
7. return;
8. }
9. printf(“%d”, arr[0]);
10. for (int i=1; i<n; i++) {
11. printf(” %d”, arr[i]);
12. }
13. printf(“\n”);
14. }
16. void sort_array(int *arr, int n)
17. {
18. int len = n;
19. int minIndex, temp;
20. for (int i = 0; i < len – 1; i++)
21. {
22. minIndex = i;
23. for (int j = i + 1; j < len; j++)
24. if (arr[j] < arr[minIndex])
25. minIndex = j;
27. temp = arr[i];
28. arr[i] = arr[minIndex];
29. arr[minIndex] = temp;
30. if (i < 3) print_array(arr, n);
31. }
32. print_array(arr, n);
33. }

第3关：插入排序

任务描述

本关任务：实现插入排序算法，并将乱序数列变成升序。

相关知识

为了完成本关任务，你需要掌握：1.插入排序算法。

插入排序算法

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 算法步骤：
  1. 从第一个元素开始，该元素认为已经被排序；
  2. 取下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果已排序元素大于新元素，将已排序元素移到下一位置；
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤2~5。

编程要求

本关的编程任务是补全右侧代码片段sort_array中Begin至End中间的代码，具体要求如下：

• 在sort_array中，实现插入排序算法，完成指定输出。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：

10

7 1 4 6 8 9 5 2 3 10

预期输出：

1 7 4 6 8 9 5 2 3 10

1 4 7 6 8 9 5 2 3 10

1 4 6 7 8 9 5 2 3 10

1 2 3 4 5 6 7 8 9 10

测试输入：

15

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48

预期输出：

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48

3 38 44 5 47 15 36 26 27 2 46 4 19 50 48

3 5 38 44 47 15 36 26 27 2 46 4 19 50 48

2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

 参考代码

1. #include “sort_.h”
3. void print_array(int *arr, int n)
4. {
5. if(n==0){
6. printf(“ERROR: Array length is ZERO\n”);
7. return;
8. }
9. printf(“%d”, arr[0]);
10. for (int i=1; i<n; i++) {
11. printf(” %d”, arr[i]);
12. }
13. printf(“\n”);
14. }
16. void sort_array(int *arr, int n)
17. {
18. int i, j, temp;
19. for(i = 0; i < n – 1; i ++)
20. {
21. temp = arr[i + 1];
22. j = i;
23. while(j > -1 && temp < arr[j])
24. arr[j + 1] = arr[j], j –;
25. arr[j + 1] = temp;
26. if (i < 3) print_array(arr, n);
27. }
28. print_array(arr, n);
29. }

第4关：希尔排序

任务描述

本关任务：实现希尔排序算法，并将乱序数列变成升序。

相关知识

为了完成本关任务，你需要掌握：1.希尔排序算法。

希尔排序算法

希尔排序由Shell在1959年发明，又叫缩小增量排序，是第一个突破O(n2)的排序算法，属于简单插入排序的改进版，会优先比较距离较远的元素。

• 算法步骤：
  1. 选择一个增量序列T1​，T2​，… ，Tk​，其中Ti​>Tj​，Tk​=1，i>j；
  2. 每趟排序，根据对应的增量Ti​，将待排序列分割成若干子序列，分别对各子序列进行直接插入排序；
  3. 按增量序列个数k，对序列进行k趟排序。
• 希尔排序实例： 下图的增量序列为：5，2，1，第一趟排序将增量为5的子序列进行插入排序，第二趟排序将增量为2的子序列进行插入排序，第三趟将增量为1的子序列进行插入排序，最终完成排序。

• 希尔排序的核心在于增量序列的设定：

  既可以提前设定好增量序列，也可以动态的定义增量序列。例如序列长度为n，则动态增量为：1，4，7，…，3x+1<n/3。

编程要求

本关的编程任务是补全右侧代码片段sort_array中Begin至End中间的代码，具体要求如下：

• 在sort_array中，使用增量序列[5, 2, 1]实现希尔排序算法，完成指定输出。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：

8

6 10 5 2 4 9 1 7

预期输出：

6 1 5 2 4 9 10 7

4 1 5 2 6 7 10 9

1 2 4 5 6 7 9 10

1 2 4 5 6 7 9 10

测试输入：

10

7 1 4 6 8 9 5 2 3 10

预期输出：

7 1 2 3 8 9 5 4 6 10

2 1 5 3 6 4 7 9 8 10

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

参考代码

1. #include “sort_.h”
3. void print_array(int *arr, int n)
4. {
5. if(n==0){
6. printf(“ERROR: Array length is ZERO\n”);
7. return;
8. }
9. printf(“%d”, arr[0]);
10. for (int i=1; i<n; i++) {
11. printf(” %d”, arr[i]);
12. }
13. printf(“\n”);
14. }
16. void sort_array(int *arr, int n)
17. {
18. int i, j, m = 0;
19. for(int gap = 5; gap > 0; gap /= 2)
20. {
21. for(i = gap; i < n; i++)
22. {
23. int num = arr[i];
24. for(j = i – gap; j >= 0 && arr[j] > num; j -= gap)
25. arr[j + gap] = arr[j];
26. arr[j + gap] = num;
27. }
28. if(m < 3)
29. {
30. print_array(arr, n);
31. m ++;
32. }
33. }
34. print_array(arr, n);
35. }

第5关：归并排序

任务描述

本关任务：实现归并排序算法，并将乱序数列变成升序。

相关知识

为了完成本关任务，你需要掌握：1.归并排序算法。

归并排序算法

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，是采用分治法Divide and Conquer的一个非常典型的应用。分Divide：将问题分成一些小的问题然后递归求解；治Conquer：将分的阶段得到的各答案合并在一起。

• 算法步骤：
  1. 把长度为n的输入序列分成两个长度为n/2的子序列；
  2. 对这两个子序列分别采用归并排序；
  3. 将两个排序好的子序列合并成一个最终的排序序列。

编程要求

本关的编程任务是补全右侧代码片段merge_array和merge_sort中Begin至End中间的代码，具体要求如下：

• 在merge_array中，实现两个有序数组arr1和arr2合并。
• 在merge_sort中，实现归并排序：自上而下的递归方法。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：

10

7 1 4 6 8 9 5 2 3 10

预期输出：

1 2 3 4 5 6 7 8 9 10

测试输入：

15

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48

预期输出：

2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

 参考代码

1. #include “sort_.h”
3. void print_array(int *arr, int n)
4. {
5. if(n==0){
6. printf(“ERROR: Array length is ZERO\n”);
7. return;
8. }
9. printf(“%d”, arr[0]);
10. for (int i=1; i<n; i++)
11. printf(” %d”, arr[i]);
12. printf(“\n”);
13. }
15. int* merge_array(int *arr1, int n1, int* arr2, int n2)
16. {
17. int* res;
18. res = new int[n1 + n2];
19. int a1 = 0, a2 = 0, index = 0;
21. for (int i = 0; i < n1+n2; i++)
22. if (i < n1) res[i] = arr1[i];
23. else res[i] = arr2[i – n1];
25. sort(res, res + n1 + n2);
26. return res;
27. }
29. int* merge_sort(int *arr, int n)
30. {
31. int mid = n / 2;
32. if (mid > 0)
33. {
34. int* arr1 = new int[mid];
35. int n1 = mid, n2 = n – mid;
36. int* arr2 = new int[n2];
37. for (int i = 0; i < n; i++)
38. if (i < mid) arr1[i] = arr[i];
39. else arr2[i – mid] = arr[i];
41. merge_sort(arr1, n1);
42. merge_sort(arr2, n – mid);
43. merge_array(arr1, n1, arr2, n2);
44. }
45. else return merge_array(arr, n, NULL, 0);
46. }