头歌-十大经典排序算法
桶排序是计数排序的升级版。第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的新无序区；选择排序是一种简单直观的排序算法，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序
第1关：冒泡排序
任务描述
本关任务：实现冒泡排序算法，并将乱序数列变成升序。
相关知识
为了完成本关任务，你需要掌握：1.冒泡排序算法。
冒泡排序算法
冒泡排序重复地遍历待排序的数列，每次比较两个相邻元素，如果它们的顺序错误就把它们交换。重复地进行遍历直到没有再需要交换时表示数列已经排序完成。
- 算法步骤：
- 比较相邻的元素：若第一个比第二个大，则交换；
- 遍历开始第一对到结尾最后一对，执行步骤
1； - 重复步骤
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<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;
int temp;
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);
/********** End **********/
}
第2关：选择排序
任务描述
本关任务：实现选择排序算法，并将乱序数列变成升序。
相关知识
为了完成本关任务，你需要掌握：1.选择排序算法。
选择排序算法
选择排序是一种简单直观的排序算法，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 算法步骤：
-
初始状态：无序序列为R[0,n−1]，长度n，有序区为空；
-
第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的新无序区；
-
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<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.插入排序算法。
插入排序算法
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
- 算法步骤：
-
从第一个元素开始，该元素认为已经被排序；
-
取下一个元素，在已经排序的元素序列中从后向前扫描；
-
如果已排序元素大于新元素，将已排序元素移到下一位置；
-
重复步骤
3，直到找到已排序的元素小于或者等于新元素的位置； -
将新元素插入到该位置后；
-
重复步骤
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<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)的排序算法，属于简单插入排序的改进版，会优先比较距离较远的元素。
- 算法步骤：
-
选择一个增量序列T1，T2，… ，Tk，其中Ti>Tj，Tk=1，i>j；
-
每趟排序，根据对应的增量Ti，将待排序列分割成若干子序列，分别对各子序列进行直接插入排序；
-
按增量序列个数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<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：将分的阶段得到的各答案合并在一起。
- 算法步骤：
-
把长度为n的输入序列分成两个长度为n/2的子序列；
-
对这两个子序列分别采用归并排序；
-
将两个排序好的子序列合并成一个最终的排序序列。
编程要求
本关的编程任务是补全右侧代码片段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<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.快速排序算法。
快速排序算法
快速排序是最常用的一种排序算法，它的特点是速度快、效率高。快速排序的基本思想：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素作为基准值。
- 算法步骤：
-
从数列中挑出一个元素，称为
基准pivot； -
分区
partition操作：比基准值小的元素放在左边，比基准值大的元素放在右边； -
递归
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
#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是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
- 算法步骤：
-
将初始待排序关键字序列
(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； -
将堆顶元素
R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn)，且满足R[1,2…n-1]<=R[n]； -
由于交换后新的堆顶
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
#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.计数排序算法。
计数排序算法
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
- 算法步骤：
-
找出待排序的数组中最大和最小的元素；
-
统计数组中每个值为
i的元素出现的次数，存入数组C的第i项； -
对所有的计数累加（从
C中的第一个元素开始，每一项和前一项相加）； -
反向填充目标数组：将每个元素
i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
编程要求
本关的编程任务是补全右侧代码片段sort_array中Begin至End中间的代码，具体要求如下：
- 在
sort_array中，实现计数排序算法，完成指定输出。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入： 10 7 1 4 6 8 9 5 2 3 10 预期输出： 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 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<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
void sort_array(int *arr, int n)
// 编程实现《计数排序算法》
// 函数参数：乱序整数数组 数组长度
// 要求输出：调用print_array(int *arr, int n)输出：
// 每一行一个元素及其个数（升序），如 1 1
// 以及最终的升序序列
{
// 请在这里补充代码，完成本关任务
/********** 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);
}
print_array(arr,n);//输出
/********** End **********/
}
第9关：桶排序
任务描述
本关任务：实现桶排序算法，并将乱序数列变成升序。
相关知识
为了完成本关任务，你需要掌握：1.桶排序算法。
桶排序算法
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
- 算法步骤：
-
设置一个定量的数组当作空桶；
-
遍历输入数据，并且把数据一个一个放到对应的桶里去；
-
对每个不是空的桶进行排序；
-
从不是空的桶里把排好序的数据拼接起来。
编程要求
本关的编程任务是补全右侧代码片段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
#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 i,j,MAX = arr[0],MIN = arr[0],Num = 10;
//Num --桶的个数 -- 没多一个桶，可容纳的待排序的数字就可以大10
int bucketEle[10] ;//桶中情况
//寻找数组中最大最小值
for(i=0;i<n;i++)
if(arr[i]>=MAX)
MAX = arr[i];
else if(arr[i]<=MIN)
MIN = arr[i];
int len =15;//单个桶的长度
int bucketArry [Num][len];
//清空桶
for(i=0;i<Num;i++)
{
bucketEle[i] = 0;
for(j=0;j<len;j++)
bucketArry[i][j]=0;
}
//数据入桶
for(i=0;i<n;i++)
{
int subScript_1 = arr[i]/10;//寻找该入哪个桶
bucketArry[subScript_1][bucketEle[subScript_1]] = arr[i];
bucketEle[subScript_1]++;//统计桶中元素的个数
}
//冒泡排序【对每一个单独的桶进行排序】
int temp,f;
for(temp=0;temp<Num;temp++)//二维数组的第几行
{
int length = bucketEle[temp];
for(i=0;i<length-1;i++)
{
for(j=0;j<length-i-1;j++)
{
if(bucketArry[temp][j]>bucketArry[temp][j+1])
{
f = bucketArry[temp][j];
bucketArry[temp][j] = bucketArry[temp][j+1];
bucketArry[temp][j+1] = f;
}
}
}
}
int t=0,k=0;
//数据整合
for(i=0;i<Num;i++)
{
if(bucketEle[i]!=0)//当前桶不空
{
while(k<bucketEle[i])
{
arr[t] = bucketArry[i][k];
t++;//总元素
k++;
}
}
k=0;
}
return arr;
/********** End **********/
}第10关：基数排序
任务描述
本关任务：实现基数排序算法，并将乱序数列变成升序。
相关知识
为了完成本关任务，你需要掌握：1.基数排序算法。
基数排序算法
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
- 算法步骤：
-
取得数组中的最大数，并取得位数；
-
arr为原始数组，从最低位开始取每个位组成radix数组； -
对
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
#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 **********/
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
18
0- 0
已为社区贡献1条内容
所有评论(0)