因网站开发需要,wordpress flat,销售网站后台维护怎么做,东莞公共资源交易中心第1关#xff1a;冒泡排序
任务描述
本关任务#xff1a;实现冒泡排序算法#xff0c;并将乱序数列变成升序。
相关知识
为了完成本关任务#xff0c;你需要掌握#xff1a;1.冒泡排序算法。
冒泡排序算法
冒泡排序重复地遍历待排序的数列#xff0c;每次比较两个相…第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_.hvoid print_array(int *arr, int n)
// 打印数组
{if(n0){printf(ERROR: Array length is ZERO\n);return;}printf(%d, arr[0]);for (int i1; in; 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(i0;in-1;i)//进行 n-1 次{for(j0;jn-i-1;j)//每次 n-i-1 轮 if(arr[j]arr[j1]){//前后 大的数后移int temp arr[j];arr[j] arr[j1];arr[j1] temp; }if(i3)print_array(arr, n); //前三次输出 }print_array(arr, n); /********** End **********/
}
第2关选择排序
任务描述
本关任务实现选择排序算法并将乱序数列变成升序。
相关知识
为了完成本关任务你需要掌握1.选择排序算法。
选择排序算法
选择排序是一种简单直观的排序算法首先在未排序序列中找到最小元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。
算法步骤 初始状态无序序列为R[0,n−1]长度n有序区为空 第i1,..,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_.hvoid print_array(int *arr, int n)
// 打印数组
{if(n0){printf(ERROR: Array length is ZERO\n);return;}printf(%d, arr[0]);for (int i1; in; 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,temp0;for(i0;in-1;i){min arr[i];//设定最小值for(ji1;jn;j)if(minarr[j]){min arr[j];//如果出现更小的值保存更小值的下标flag 1;//标记找到更小的了需要更新最小值tempj;//保存下标}if(flag1)//flag1说明找到更小的值,即下标发生了变化 - 交换{int t arr[i];arr[i] arr[temp];arr[temp] t;flag 0 ;//恢复标志位}if(i3){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_.hvoid print_array(int *arr, int n)
// 打印数组
{if(n0){printf(ERROR: Array length is ZERO\n);return;}printf(%d, arr[0]);for (int i1; in; 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;in;i){if(arr[i]arr[i-1]){temp arr[i];for(ji-1;temparr[j]j!-1;j--){//注意此处的 !-1 arr[j1] arr[j];}arr[j1] temp;}if(i4){print_array(arr, n);}}print_array(arr, n); /********** End **********/
}
第4关希尔排序
任务描述
本关任务实现希尔排序算法并将乱序数列变成升序。
相关知识
为了完成本关任务你需要掌握1.希尔排序算法。
希尔排序算法
希尔排序由Shell在1959年发明又叫缩小增量排序是第一个突破O(n2)的排序算法属于简单插入排序的改进版会优先比较距离较远的元素。
算法步骤 选择一个增量序列T1T2… Tk其中TiTjTk1ij 每趟排序根据对应的增量Ti将待排序列分割成若干子序列分别对各子序列进行直接插入排序 按增量序列个数k对序列进行k趟排序。
希尔排序实例 下图的增量序列为521第一趟排序将增量为5的子序列进行插入排序第二趟排序将增量为2的子序列进行插入排序第三趟将增量为1的子序列进行插入排序最终完成排序。
希尔排序的核心在于增量序列的设定
既可以提前设定好增量序列也可以动态的定义增量序列。例如序列长度为n则动态增量为147...3x1n/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_.hvoid print_array(int *arr, int n)
// 打印数组
{if(n0){printf(ERROR: Array length is ZERO\n);return;}printf(%d, arr[0]);for (int i1; in; 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,t0;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 keyarr[end]){arr[end gap] arr[end];endend-gap;}arr[end gap] key;}print_array(arr, n);t;gapGap[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_.hvoid print_array(int *arr, int n)
// 打印数组
{if(n0){printf(ERROR: Array length is ZERO\n);return;}printf(%d, arr[0]);for (int i1; in; 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 i0 , j0,t0;//比较两个顺序表中的值并将小的值放入LC中当其中一个表比较完成后while(in1jn2){if(arr1[i]arr2[j])arr3[t] arr1[i];elsearr3[t] arr2[j]; }//直接将另一个未比较完成的表中的剩余值全部放到LC中if(in1){while(tarr3_length)arr3[t] arr2[j]; }else{while(tarr3_length)arr3[t] arr1[i];}return arr3;
/*注解①:1.此处必须使用malloc函数动态分配内存若使用int arr3[arr3_length]的方式分配内存,则当该函数结束此空间已经归并好的数据将被程序释放,在另一个函数中接收到的将是一堆垃圾值 2.通常来说动态分配内存很少失败,但 为使程序更加健壮,可以增加以下代码if(arr3NULL)return NULL; //动态分配空间失败 */ /********** End **********/
}int* merge_sort(int *arr, int n)
// 基于merge_array函数编程实现归并排序自上而下的递归方法
// 函数参数有序数组arr 数组arr长度
// 函数返回值返回从小到大排序后的数组
{// 请在这里补充代码完成本关任务/********** Begin *********/int mid ;int left 0 ,right n;//注解① mid (leftright)/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;/*注解① 此处 rightn 注解②:1. 当right1时说明小数组的长度为1即不可在分 2. 也可使用if(mid!0)因为left一定等于0,且right1故mid (01)/2 0; 3. 此处若换成if(leftright)是错误的因为按理说最后一次 left 0,right 1,此时 leftright始终成立,将一直递归下去,不会终止
*//********** 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_.hvoid print_array(int *arr, int n)
// 打印数组
{if(n0){printf(ERROR: Array length is ZERO\n);return;}printf(%d, arr[0]);for (int i1; in; 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(lr)//终止条件 { while((lr)arr[r]temp)//大数在高位不动r--;//注解①arr[l] arr[r];//小数在高位移动while((lr)arr[l]temp)l;arr[r] arr[l];}arr[l] temp;return l;/*注解①注意 此处的两个内部的while循环均再次进行了判断lowhigh 判断,因为在比较的过程中如果未发生值的覆盖,则low/high将一直移动,此过程中就可能导致 循环不在满足lowhigh ;
*//********** End **********/
}int* quick_sort(int *arr, int l, int r)
// 基于partition_array函数编程实现快速排序自上而下的递归方法
// 函数参数有序数组arr 初始l0rn-1
// 函数返回值返回从小到大排序后的数组
{// 请在这里补充代码完成本关任务/********** Begin *********/int pos partition_array(arr,l,r);if(lr){if(lpos-1)arr quick_sort(arr,l,pos-1);if(pos1r)arr quick_sort(arr,pos1,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_.hvoid print_array(int *arr, int n)
// 打印数组
{if(n0){printf(ERROR: Array length is ZERO\n);return;}printf(%d, arr[0]);for (int i1; in; i) {printf( %d, arr[i]);}printf(\n);
}void adjustHeap(int *arr, int param1, int j)
// 编程实现堆的调整
{// 请在这里补充代码完成本关任务/********** Begin *********/int temp;if(jparam1){int maxj;//根结点int s12*j1;//左子节点int s22*j2;//右子结点//找出最大结点if(arr[s1]arr[max]s1param1)maxs1;if(arr[s2]arr[max]s2param1)maxs2;//交换最大子节点到根结点并做递归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 lastn-1; //最后一个子结点位置int parent(last-1)/2; //最后一个子结点的父结点for(int iparent;i0;i--) {adjustHeap(arr,n,i); //从最后一个父结点开始做最大堆调整}for(int in-1;i0;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_.hvoid print_array(int *arr, int n)
// 打印数组
{if(n0){printf(ERROR: Array length is ZERO\n);return;}printf(%d, arr[0]);for (int i1; in; 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],MINarr[0], t 0 ;;int i ;//寻找数组中最大最小值 for(i0;in;i){if(arr[i]MAX)MAX arr[i]; if(arr[i]MIN)MIN arr[i];}//生成统计数组,并清空数据 int Arr_2[MAX] ;int j0;while(jMAX){Arr_2[j] 0;j; }for( i0;in;i)Arr_2[arr[i]];//统计 for( i MIN;iMAX;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_.hvoid print_array(int *arr, int n)
// 打印数组
{if(n0){printf(ERROR: Array length is ZERO\n);return;}printf(%d, arr[0]);for (int i1; in; 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 --桶的个数 -- 没多一个桶可容纳的待排序的数字就可以大10int bucketEle[10] ;//桶中情况 //寻找数组中最大最小值 for(i0;in;i)if(arr[i]MAX)MAX arr[i]; else if(arr[i]MIN) MIN arr[i];int len 15;//单个桶的长度 int bucketArry [Num][len];//清空桶for(i0;iNum;i){bucketEle[i] 0; for(j0;jlen;j)bucketArry[i][j]0;}//数据入桶for(i0;in;i) {int subScript_1 arr[i]/10;//寻找该入哪个桶 bucketArry[subScript_1][bucketEle[subScript_1]] arr[i];bucketEle[subScript_1];//统计桶中元素的个数}//冒泡排序【对每一个单独的桶进行排序】int temp,f;for(temp0;tempNum;temp)//二维数组的第几行 {int length bucketEle[temp];for(i0;ilength-1;i){for(j0;jlength-i-1;j){if(bucketArry[temp][j]bucketArry[temp][j1]){f bucketArry[temp][j];bucketArry[temp][j] bucketArry[temp][j1];bucketArry[temp][j1] f;}}}}int t0,k0;//数据整合for(i0;iNum;i){if(bucketEle[i]!0)//当前桶不空{while(kbucketEle[i]) {arr[t] bucketArry[i][k];t;//总元素k; }} k0;}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_.hvoid print_array(int *arr, int n)
// 打印数组
{if(n0){printf(ERROR: Array length is ZERO\n);return;}printf(%d, arr[0]);for (int i1; in; i) {printf( %d, arr[i]);}printf(\n);
}int* sort_array(int *arr, int n)
// 编程实现《基数排序算法》
// 函数参数乱序整数数组 数组长度
// 函数返回值返回从小到大排序后的数组
{// 请在这里补充代码完成本关任务/********** Begin *********/int MAX arr[0],MINarr[0], t 0 ;int i ;//寻找数组中最大最小值 for(i0;in;i){if(arr[i]MAX)MAX arr[i]; if(arr[i]MIN)MIN arr[i];}//生成统计数组,并清空数据 int Arr_2[MAX] ;int j0;while(jMAX){Arr_2[j] 0;j; }for( i0;in;i)Arr_2[arr[i]];//统计 for( i MIN;iMAX;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 **********/
}
