educoder:第2关：实现快速排序 |
您所在的位置：网站首页 › c语言实现快速排序 › educoder:第2关：实现快速排序 |
educoder:第2关：实现快速排序
|
educoder:第2关：实现快速排序
任务描述
本关要求通过补全快速排序私有函数QSort__来供函数QuickSort调用，以此来实现快速排序的功能。 相关知识 快速排序的基本过程是：从待排序记录中任选一个记录，以它的排序码作为中心值，将其它记录划分为两个部分，第一部分包含所有排序码小于等于中心值的记录，第二部分包含所有排序码大于中心值的记录。第一部分放在该记录的前面，第二部分放在该记录的后面。对这两个部分采用同样的方法进行处理，直到每个部分为空或只含一个记录为止。下图 1 给出了一个用中心值将排序记录分割为前后两部分的示例过程。
本关的编程任务是补全 step2/quickSort.cpp 文件中的QSort__函数来供函数QuickSort调用，按照从小到大的排列顺序实现快速排序的功能。 具体请参见后续测试样例。 本关涉及的代码文件 quickSort.cpp 的代码框架如下： #include #include #include #include"quickSort.h" void QSort__(int* a, int low, int high) //快速排序私有函数，供QuickSort()调用 //在a[low:high]中选择一个中心值，用该中心值将a[low:high]分割为两部分 //然后对两个部分递归地进行该操作。 { int i, j; if(low>=high) return; Swap(a[low], a[rand()%(high-low+1)+low]); //select a pivot randomly i=low; j=high; int temp=a[i]; // 请在此添加代码，补全函数QSort__ /********** Begin *********/ /********** End **********/ } void QuickSort(int* a, int n) //快速排序主函数 { srand((unsigned)time(0)); //for selecting the pivot randomly in QSort__(). QSort__(a, 0, n-1); } 评测说明本关的测试文件是 step2/Main.cpp ，测试过程如下： 平台编译 step2/Main.cpp ，然后链接相关程序库并生成 exe 可执行文件； 平台运行该 exe 可执行文件，并以标准输入方式提供测试输入； 平台获取该 exe 可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。 输入输出格式说明 输入格式： 首先输入一个正整数n。 然后输入n个整数。 输出格式： 输出对 n 个整数从小到大排序的结果。 以下是平台对 step1/Main.cpp 的样例测试集： 样例输入： 5 45 78 2 34 90 样例输出： sort result:2 34 45 78 90 开始你的任务吧，祝你成功！ Answer接下来是正式的解答 话不多说上代码 注释中有相应的我认为比较关键的解释 如果有什么不懂可以私信我 //排序算法实现文件 // #include #include #include #include"quickSort.h" void QSort__(int* a, int low, int high) //快速排序私有函数，供QuickSort()调用 //在a[low:high]中选择一个中心值，用该中心值将a[low:high]分割为两部分 //然后对两个部分递归地进行该操作。 { int i, j; if(low>=high) return;//递归结束条件：当low>=high时也就是对数组的划分到达最小的时候（划分中只有一个元素）递归结束 也就是排序完成 Swap(a[low], a[rand()%(high-low+1)+low]); //select a pivot randomly找出一个随机数 //rand()函数是随机返回一个0～32767的整数 i=low; j=high; int temp=a[i];//存贮的随机数 // 请在此添加代码，补全函数QSort__ /********** Begin *********/ while(i!=j) { while(j>i&&a[j]>=temp) { j--; } a[i]=a[j];//将从右往左找的第一个小于random的数填入空处 填完之后a[j]就是本次循环中的空处了 while(i |
【本文地址】
今日新闻 |
推荐新闻 |