中国建设银行官网站金银纪念币,网页设计图片怎么放进去,网页制作价格表,内置wordpress主机目录
算法设计与分析——十大经典排序算法
第1关#xff1a;冒泡排序 参考代码
第2关#xff1a;选择排序
参考代码
第3关#xff1a;插入排序 参考代码
第4关#xff1a;希尔排序
参考代码
第5关#xff1a;归并排序 参考代码
作者有言 一个不知名大学生#x…
目录
算法设计与分析——十大经典排序算法
第1关冒泡排序 参考代码
第2关选择排序
参考代码
第3关插入排序 参考代码
第4关希尔排序
参考代码
第5关归并排序 参考代码
作者有言 一个不知名大学生江湖人称菜狗 original author: jacky Li Email : 3435673055qq.com Time of completion2023.2.28 Last edited: 2023.2.28 导读 帮助算法设计初学者快速掌握算法设计帮助安静对ABCD……等的重要性排序更清晰 算法设计与分析——十大经典排序算法
第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)
{int i, x, j;for(j 0; j n; j ){for(i 0; i n - 1; i ){if(arr[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.选择排序算法。
选择排序算法
选择排序是一种简单直观的排序算法首先在未排序序列中找到最小元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。 算法步骤 初始状态无序序列为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)
{int len n;int minIndex, temp;for (int i 0; i len - 1; i) {minIndex i;for (int j i 1; j len; j) if (arr[j] arr[minIndex]) minIndex j;temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;if (i 3) print_array(arr, n);}print_array(arr, n);
}
第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)
{int i, j, temp;for(i 0; i n - 1; i ){temp arr[i 1];j i;while(j -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)的排序算法属于简单插入排序的改进版会优先比较距离较远的元素。 算法步骤 选择一个增量序列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)
{int i, j, m 0;for(int gap 5; gap 0; gap / 2) {for(i gap; i n; i) {int num arr[i];for(j i - gap; j 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将分的阶段得到的各答案合并在一起。 算法步骤 把长度为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)
{int* res;res new int[n1 n2];int a1 0, a2 0, index 0;for (int i 0; i n1n2; i) if (i n1) res[i] arr1[i];else res[i] arr2[i - n1];sort(res, res n1 n2);return res;
}int* merge_sort(int *arr, int n)
{int mid n / 2;if (mid 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);
} 作者有言 如果感觉博主讲的对您有用请点个关注支持一下吧将会对此类问题持续更新……
