目录

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

第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

参考代码

#include "sort_.h" void print_array(int *arr, int n){    if(n==0){        printf("ERROR: Array length is ZERO\n");        return;    }    printf("%d", arr[0]);    for (int i=1; i arr[i + 1])             {                x = arr[i];                arr[i] = arr[i + 1];                arr[i + 1] = x;            }        }        if(j < 3) print_array(arr, n);    }    print_array(arr, n);}

第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

参考代码

#include "sort_.h"void print_array(int *arr, int n){    if(n==0){        printf("ERROR: Array length is ZERO\n");        return;    }    printf("%d", arr[0]);    for (int i=1; i

第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

参考代码

#include "sort_.h"void print_array(int *arr, int n){    if(n==0){        printf("ERROR: Array length is ZERO\n");        return;    }    printf("%d", arr[0]);    for (int i=1; i -1 && temp < arr[j])            arr[j + 1] = arr[j], j --;        arr[j + 1] = temp;        if (i < 3) print_array(arr, n);    }    print_array(arr, n);}

第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

参考代码

#include "sort_.h"void print_array(int *arr, int n){    if(n==0){        printf("ERROR: Array length is ZERO\n");        return;    }    printf("%d", arr[0]);    for (int i=1; i 0; gap /= 2)     {        for(i = gap; i = 0 && arr[j] > num; j -= gap)                arr[j + gap] = arr[j];            arr[j + gap] = num;        }        if(m < 3)        {            print_array(arr, n);            m ++;        }    }    print_array(arr,  n);}

第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

参考代码

#include "sort_.h"void print_array(int *arr, int n){    if(n==0){        printf("ERROR: Array length is ZERO\n");        return;    }    printf("%d", arr[0]);    for (int i=1; i 0)     {        int* arr1 = new int[mid];        int n1 = mid, n2 = n - mid;        int* arr2 = new int[n2];        for (int i = 0; i < n; i++)             if (i < mid) arr1[i] = arr[i];            else arr2[i - mid] = arr[i];         merge_sort(arr1, n1);           merge_sort(arr2, n - mid);             merge_array(arr1, n1, arr2, n2);    }    else return  merge_array(arr, n, NULL, 0);}

作者有言

如果感觉博主讲的对您有用，请点个关注支持一下吧，将会对此类问题持续更新……