#头歌 数据结构 实验十二 排序的实现

发布时间：2024年01月04日

第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

开始你的任务吧，祝你成功！

最后通关代码：

//

// ?sort_.cpp

// ?Sort

//

// ?Created by ljpc on 2018/4/20.

// ?Copyright ? 2018年 ljpc. All rights reserved.

//

#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<n; i++) {

? ? ? ? printf(" %d", arr[i]);

? ? }

? ? printf("\n");

}



?

void sort_array(int *arr, int n)

// ?编程实现《冒泡排序算法》：将乱序序列arr转化为升序序列

// ?函数参数：乱序整数数组arr 数组长度

// ?要求输出：调用print_array(int *arr, int n)输出前三次冒泡操作后的序列，以及最终的升序序列

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

/*

? ? int i ,j;

? ? for(i=0;i<n-1;i++)//进行 n-1 次

? ? {

? ? ? ? for(j=0;j<n-i-1;j++)//每次 n-i-1 轮

? ? ? ? ? ? if(arr[j]>arr[j+1])

? ? ? ? ? ? {//前>后 ?大的数后移

? ? ? ? ? ? ? ? int temp ? =arr[j];

? ? ? ? ? ? ? ? ? ? arr[j] ? ?= arr[j+1];

? ? ? ? ? ? ? ? ? ? arr[j+1] = temp;

? ? ? ? ? ? }

? ? ? ? if(i<3)

? ? ? ? ? ? print_array(arr, n); //前三次输出 ?

? ? }

? ? ? ?

? ? ? ?print_array(arr, n); ? ? ? ? ?

? ? */

? ? //优化：

? ? int i ,j;

? ? int flag ;

? ? for(i=0;i<n-1;i++)//进行 n-1 次

? ? {

? ? ? ? flag = 0;//交换标识

? ? ? ? for(j=0;j<n-i-1;j++)//每次 n-i-1 轮

? ? ? ? ? ? if(arr[j]>arr[j+1])

? ? ? ? ? ? {//前>后 ?大的数后移

? ? ? ? ? ? ? ? int temp ? =arr[j];

? ? ? ? ? ? ? ? ? ? arr[j] ? ?= arr[j+1];

? ? ? ? ? ? ? ? ? ? arr[j+1] = temp;

? ? ? ? ? ? ? ? ? ? flag ?= 1;

? ? ? ? ? ? }

? ? ? ? //-----------------------------

? ? ? ? ? ? if(flag==0)

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? /*

? ? ? ? ? ? ? ? 如果此时flag == 0

? ? ? ? ? ? ? ? 说明当前轮没有发生交换

? ? ? ? ? ? ? ? 即；此时当前数列已经"有序"

? ? ? ? ? ? */

? ? ? ? //-----------------------------

? ? ? ? ? ? if(i<3)

? ? ? ? ? ? ? ? print_array(arr, n); //前三次输出 ?

? ? }

? ? ? ?print_array(arr, n); ?

? ?

? ? /********** End **********/

}



第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

开始你的任务吧，祝你成功！

最后通关代码：

//

// ?sort_.cpp

// ?Sort

//

// ?Created by ljpc on 2018/4/20.

// ?Copyright ? 2018年 ljpc. All rights reserved.

//

#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<n; i++) {

? ? ? ? printf(" %d", arr[i]);

? ? }

? ? printf("\n");

}

void sort_array(int *arr, int n)

// ?编程实现《选择排序算法》：将乱序序列arr转化为升序序列

// ?函数参数：乱序整数数组（无重复元素） 数组长度

// ?要求输出：调用print_array(int *arr, int n)输出前三次选择操作后的序列，以及最终的升序序列

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

?int i ,j,min;

? ? ?int flag = 0,temp=0;

? ? for(i=0;i<n-1;i++)

? ? {

? ? ? ? min = arr[i];//设定最小值

? ? ? ? for(j=i+1;j<n;j++)

? ? ? ? ? ? if(min>arr[j])

? ? ? ? ? ? ? ? {//如果出现更小的值，保存更小值的下标

? ? ? ? ? ? ? ? ? ? min = arr[j];

? ? ? ? ? ? ? ? ? ? flag = 1;

? ? ? ? ? ? ? ? ? ? temp=j;

? ? ? ? ? ? ? ? }

? ? ? ?if(flag==1)//"flag==1"说明找到更小的值,即下标发生了变化 -> 交换

? ? ? ?{

? ? ? ? ? int t = arr[i];

? ? ? ? ? arr[i] ?= arr[temp];

? ? ? ? ? arr[temp] = t;

? ? ? ? ? flag = 0 ;

? ? ? ?}

? ? ? ? if(i<3)

? ? ? ? ? ? print_array(arr, n); //前三次输出 ?

? ? }

? ? ? ?

? ? ? ?print_array(arr, n); ? ?

? ?

? ?

? ? /********** End **********/

}



第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

开始你的任务吧，祝你成功！

最后通关代码：

//

// ?sort_.cpp

// ?Sort

//

// ?Created by ljpc on 2018/4/20.

// ?Copyright ? 2018年 ljpc. All rights reserved.

//

#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<n; i++) {

? ? ? ? printf(" %d", arr[i]);

? ? }

? ? printf("\n");

}

void sort_array(int *arr, int n)

// ?编程实现《插入排序算法》：将乱序序列arr转化为升序序列

// ?函数参数：乱序整数数组（无重复元素） 数组长度

// ?要求输出：调用print_array(int *arr, int n)输出前三次插入操作后的序列，以及最终的升序序列

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

int i ,j ,temp;

? ? for(i =1;i<n;i++)

? ? {

? ? ? if(arr[i]<arr[i-1])

? ? ? {

? ? ? ? temp = arr[i];

? ? ? ? for(j=i-1;temp<arr[j]&&j!=-1;j--)//注意此处的 ?!=-1 ? ? ? ? ?

? ? ? ? ? ? ?arr[j+1] = arr[j];

? ? ? ? ? ? ?

? ? ? ? ? ? ?

? ? ? ? arr[j+1] =temp;

? ? ? }

? ? ? if(i<4)

? ? ? ? print_array(arr, n);

? ? }

? ? ?print_array(arr, n); ?

? ? ?

? ?

? ? /********** End **********/

}



?

第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

开始你的任务吧，祝你成功！

最后通关代码：

//

// ?sort_.cpp

// ?Sort

//

// ?Created by ljpc on 2018/4/20.

// ?Copyright ? 2018年 ljpc. All rights reserved.

//

#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<n; i++) {

? ? ? ? printf(" %d", arr[i]);

? ? }

? ? printf("\n");

}

void sort_array(int *arr, int n)

// ?编程实现《希尔排序算法》：将乱序序列arr转化为升序序列

// ?函数参数：乱序整数数组 数组长度

// ?要求输出：调用print_array(int *arr, int n)输出三遍增量排序操作后的序列，以及最终的升序序列

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

int i = 0,t=0;

? ? int key = 0;

? ? int end = 0;

? ? int Gap[4] = {5,2,1,-1};//最后的-1为终止条件

? ? //如果需要跟给增量，直接在这里给

? ? int gap = Gap[t];//给增量

? ? while (gap > 0)

? ? {

? ? ? ? for (i = gap; i < n; i++)

? ? ? ? {

? ? ? ? ? ? key = arr[i];

? ? ? ? ? ? end = i - gap;

? ? ? ? ? ? while (end >= 0 && key<arr[end])

? ? ? ? ? ? {

? ? ? ? ? ? ? ? arr[end + gap] = arr[end];

? ? ? ? ? ? ? ? end=end-gap;

? ? ? ? ? ? }

? ? ? ? ? ? arr[end + gap] = key;

? ? ? ? }

? ? ? ?

? ? ? ? print_array(arr, n);

? ? ? ? t++;

? ? ? ? gap=Gap[t];

? ?

? ? }

? ? print_array(arr, n); ?

? ?

? ? /********** End **********/

}



第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

开始你的任务吧，祝你成功！

最后通关代码:

//

// ?sort_.cpp

// ?Sort

//

// ?Created by ljpc on 2018/4/20.

// ?Copyright ? 2018年 ljpc. All rights reserved.

//

#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<n; i++) {

? ? ? ? printf(" %d", arr[i]);

? ? }

? ? printf("\n");

}

int* merge_array(int *arr1, int n1, int* arr2, int n2)

// ?编程实现两个有序数组arr1和arr2合并

// ?函数参数：有序数组arr1 数组arr1长度 有序数组arr2 数组arr2长度

// ?函数返回值：返回从小到大排序后的合并数组

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

//定义

? ? int arr3_length = ?n1 + n2;

? ? int *arr3 = (int *)malloc(sizeof(int)*arr3_length);//注解①

? ? ?

? ? int i=0 , j=0,t=0;

? ? //比较两个顺序表中的值，并将小的值放入LC中，当其中一个表比较完成后

? ? while(i<n1&&j<n2)

? ? ? ? {

? ? ? ? ? ? if(arr1[i]<=arr2[j])

? ? ? ? ? ? ? ? arr3[t++] = arr1[i++];

? ? ? ? ? ? else

? ? ? ? ? ? ? ? arr3[t++] = arr2[j++]; ?

? ? ? ? }


?

? ? //直接将另一个未比较完成的表中的剩余值全部放到LC中

? ? if(i==n1)

? ? ? ? {

? ? ? ? ? ? while(t<arr3_length)

? ? ? ? ? ? ? ? arr3[t++] = arr2[j++]; ?

? ? ? ? }

? ? else

? ? ? ? {

? ? ? ? ? ? while(t<arr3_length)

? ? ? ? ? ? arr3[t++] = arr1[i++];

? ? ? ? }

? ? return arr3;

/*

? ? 注解①:

? ? ? ? 1.此处必须使用malloc函数动态分配内存

? ? ? ? ? 若使用int arr3[arr3_length]的方式

? ? ? ? ? 分配内存,则当该函数结束，此空间已经

? ? ? ? ? 归并好的数据将被程序释放,在另一个

? ? ? ? ? 函数中接收到的将是一堆垃圾值

? ?

? ? ? ? 2.通常来说动态分配内存很少失败,但

? ? ? ? 为使程序更加健壮,可以增加以下代码

? ? ? ? if(arr3==NULL)

? ? ? ? ? ? return NULL; //动态分配空间失败

? ?

*/ ?

? ? /********** End **********/

}

int* merge_sort(int *arr, int n)

// ?基于merge_array函数编程实现归并排序：自上而下的递归方法

// ?函数参数：有序数组arr 数组arr长度

// ?函数返回值：返回从小到大排序后的数组

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

int mid ;

? ? int left = 0 ,right = n;//注解①

? ? mid = (left+right)/2;

? ?

? ? if(right!=1)//注解②

? ? {

? ? ? ? //从mid将数组分成两部分

? ? ? ? int *Arr_1 = &arr[left],*Arr_2 = &arr[mid];

? ? ? ? //左侧

? ? ? ? Arr_1 = merge_sort(Arr_1,mid);

? ? ? ? //右侧

? ? ? ? Arr_2 = merge_sort(Arr_2,right-mid);

? ? ? ?

? ? ? ? //合并

? ? ? ? arr = merge_array(Arr_1,mid,Arr_2,right-mid);

? ? }

? ? return arr;

? ?

/*

? ? 注解①：

? ? ? ? 此处 right==n

? ?

? ? 注解②:

? ? ? ? 1. ?当right==1时说明"小数组"的长度为1

? ? ? ? ? ? 即：不可在分

? ? ? ?

? ? ? ? 2. ?也可使用

? ? ? ? ? ? if(mid!=0)

? ? ? ? ? ? ? ? 因为：left一定等于0,且right==1

? ? ? ? ? ? ? ? 故：mid = (0+1)/2 = 0;

? ? ? ? ? ?

? ? ? ? 3. ?此处若换成

? ? ? ? ? ? if(left<right)是错误的

? ? ? ? ? ? 因为按理说最后一次 left = 0,right = 1,

? ? ? ? ? ? 此时 left<right始终成立,将一直递归下去,

? ? ? ? ? ? 不会终止 ? ? ? ? ?

*/

? ? ? ?

? ?

? ? /********** End **********/

}



?

第6关：快速排序-交换类

任务描述

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

相关知识

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

快速排序算法

快速排序是最常用的一种排序算法，它的特点是速度快、效率高。快速排序的基本思想：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素作为基准值。

  • 算法步骤：

  1. 从数列中挑出一个元素，称为基准pivot；

  2. 分区partition操作：比基准值小的元素放在左边，比基准值大的元素放在右边；

  3. 递归recursive：把小于基准值元素的子数列和大于基准值元素的子数列分别递归排序。

编程要求

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

  • 在partition_array中，实现数组分区：选定一个基准，左边比基准小，右边比基准大，返回基准所处位置。
  • 在quick_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

开始你的任务吧，祝你成功！

最后通关代码:

//

// ?sort_.cpp

// ?Sort

//

// ?Created by ljpc on 2018/4/20.

// ?Copyright ? 2018年 ljpc. All rights reserved.

//

#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<n; i++) {

? ? ? ? printf(" %d", arr[i]);

? ? }

? ? printf("\n");

}

int partition_array(int *arr ,int l,int r)

// 编程实现arr[l, r]分区：选定一个基准，左边比基准小，右边比基准大

// 返回基准所处位置

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

int temp = arr[l];//临时空间，存放"枢轴"

? ? while(l<r)//终止条件

? ? { ? ? ? ?

? ? ? ? while((l<r)&&arr[r]>=temp)//"大"数在高位不动

? ? ? ? ? ? r--;//注解①

? ? ? ? arr[l] = arr[r];//"小"数在高位移动

? ? ? ? while((l<r)&&arr[l]<=temp)

? ? ? ? ? ? l++;

? ? ? ? arr[r] = arr[l];

? ? }

? ? arr[l] = temp;

? ? return l;

? ? /*

? ? 注解①

? ? 注意： 此处的两个内部的while循环均再次进行了判断

? ? ? ? ? ? ? ? low<high 判断,因为在比较的过程中，如果未发生

? ? ? ? ? ? ? ? 值的覆盖,则low/high将一直移动,此过程中就可能

? ? ? ? ? ? ? ? 导致 循环不在满足low<high ;

*/ ?

? ? /********** End **********/

}

int* quick_sort(int *arr, int l, int r)

// ?基于partition_array函数编程实现快速排序：自上而下的递归方法

// ?函数参数：有序数组arr 初始l=0，r=n-1

// ?函数返回值：返回从小到大排序后的数组

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

int pos = partition_array(arr,l,r);

? ? if(l<r)

? ? {

? ? ? ? if(l<pos-1)

? ? ? ? ? ? arr = quick_sort(arr,l,pos-1);

? ? ? ? if(pos+1<r)

? ? ? ? ? ? arr = quick_sort(arr,pos+1,r);

? ? }

? ? return arr; ?

? ? /********** End **********/

}

第7关：堆排序-选择类

任务描述

本关任务：实现堆排序算法，并将乱序数列变成升序。堆排序是对树型选择排序的进一步改进。

相关知识

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

堆排序算法

堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

  • 算法步骤：

  1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

  2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn)，且满足R[1,2…n-1]<=R[n]；

  3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

编程要求

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

  • 在adjustHeap中，实现堆的调整。
  • 在heap_sort中，构建大顶堆，并调用adjustHeap实现堆的调整。
测试说明

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

以下是平台的测试样例：

测试输入： 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

开始你的任务吧，祝你成功！

最后通关代码:

//

// ?sort_.cpp

// ?Sort

//

// ?Created by ljpc on 2018/4/20.

// ?Copyright ? 2018年 ljpc. All rights reserved.

//

#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<n; i++) {

? ? ? ? printf(" %d", arr[i]);

? ? }

? ? printf("\n");

}

void adjustHeap(int *arr, int param1, int j)

// 编程实现堆的调整

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

int temp;

? ? if(j<param1)

? ? {

? ? ? ? int max=j;//根结点

? ? ? ? int s1=2*j+1;//左子节点

? ? ? ? int s2=2*j+2;//右子结点

? ? ? ? //找出最大结点

? ? ? ? if(arr[s1]>arr[max]&&s1<param1)

? ? ? ? ? ? max=s1;

? ? ? ? if(arr[s2]>arr[max]&&s2<param1)

? ? ? ? ? ? max=s2;

? ? ? ? //交换最大子节点到根结点并做递归

? ? ? ? if(max!=j)

? ? ? ? {

? ? ? ? ? ?

? ? ? ? ? ? temp ? ? = arr[max];

? ? ? ? ? ? arr[max] = arr[j];

? ? ? ? ? ? arr[j] ? = temp;

? ? ? ? ? ?

? ? ? ? ? ? adjustHeap(arr,param1,max); ? ?

? ? ? ? }

? ? } ?

? ? /********** End **********/

}

int* heap_sort(int *arr, int n)

// ?基于adjustHeap函数编程实现堆排序

// ?函数参数：无序数组arr 数组长度n

// ?函数返回值：返回从小到大排序后的数组

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

//创建初始堆

? ? int i,temp;

? ? int last=n-1; ? ? ? ? ? ? ? //最后一个子结点位置

? ? int parent=(last-1)/2; ? ? ?//最后一个子结点的父结点

? ? for(int i=parent;i>=0;i--) ?

? ? {

? ? ? ? adjustHeap(arr,n,i); ? ? ? ?//从最后一个父结点开始做最大堆调整

? ? }

? ? for(int i=n-1;i>=0;i--)//依次将最大堆的根结点（最大值）取出

? ? {

? ? //将最大堆的根（最大值）换到最后

? ? ? ? temp ? = arr[i];

? ? ? ? arr[i] = arr[0];

? ? ? ? arr[0] = temp;

? ? //除去最大值,对交换后的二叉树做最大堆调整，使二叉树根结点始终为最大值 ? ?

? ? ? ? adjustHeap(arr,i,0); ? ? ? ?

? ? }

? ? return arr;


?

? ? /********** End **********/

}


第8关：基数排序-分配类

任务描述

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

相关知识

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

基数排序算法

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

  • 算法步骤：

  1. 取得数组中的最大数，并取得位数；

  2. arr为原始数组，从最低位开始取每个位组成radix数组；

  3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

编程要求

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

  • 在sort_array中，实现基数排序算法，并返回升序的数组。
测试说明

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

以下是平台的测试样例：

测试输入： 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

开始你的任务吧，祝你成功！

最后通关代码:

//

// ?sort_.cpp

// ?Sort

//

// ?Created by ljpc on 2018/4/20.

// ?Copyright ? 2018年 ljpc. All rights reserved.

//

#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<n; i++) {

? ? ? ? printf(" %d", arr[i]);

? ? }

? ? printf("\n");

}


?

int* sort_array(int *arr, int n)

// ?编程实现《基数排序算法》

// ?函数参数：乱序整数数组 数组长度

// ?函数返回值：返回从小到大排序后的数组

{

? ? // 请在这里补充代码，完成本关任务

? ? /********** Begin *********/

int MAX =arr[0],MIN=arr[0], t =0 ;

? ? int i ;

? ? //寻找数组中最大最小值

? ? for(i=0;i<n;i++)

? ? ? ? {

? ? ? ? ? ? if(arr[i]>=MAX)

? ? ? ? ? ? ? ? ? ? MAX = arr[i]; ? ? ?

? ? ? ? ? ? ?if(arr[i]<=MIN)

? ? ? ? ? ? ? ? ? ? MIN = arr[i];

? ? ? ? }

? ? ? ?

? ? //生成统计数组,并清空数据

? ? int Arr_2[MAX] ;

? ? int ?j=0;

? ? while(j<=MAX)

? ? {

? ? ? ? ? ? Arr_2[j] =0;

? ? ? ? ? ? j++;

? ? }

? ? for( i=0;i<n;i++)

? ? ? ? ?Arr_2[arr[i]]++;//统计

? ? ? ? ?

? ? for( i = MIN;i<=MAX;i++)

? ? ? ? {

? ? ? ? // ? int temp = Arr_2[i];//保存arr数组中每个数出现的次数

? ? ? ? ? ?while(Arr_2[i]!=0)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? arr[t] = i;//还原数组

? ? ? ? ? ? ? ? t++;

? ? ? ? ? ? ? ? Arr_2[i]--;

? ? ? ? ? ? }

? ? ? ? ? ? //if(temp!=0)

? ? ? ? ? ?// ? printf("%d %d\n",i,temp);

? ? ? ? ?

? ? ? ? }

? ?

? ? return arr;//输出

? ?

? ? /********** End **********/

}



?

文章来源:https://blog.csdn.net/2302_79707613/article/details/135335027
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章