网站用什么主机,品牌建设实施方案 报优评奖,网络广告的优势有哪些,wordpress视频网站模板决战排序之巅#xff08;二#xff09; 排序测试函数 void verify(int* arr, int n) 归并排序递归方案代码可行性测试 非递归方案代码可行性测试 特点分析 计数排序代码实现代码可行性测试 特点分析 归并排序 VS 计数排序#xff08;Release版本#xff09;说明1w rand( ) … 决战排序之巅二 排序测试函数 void verify(int* arr, int n) 归并排序递归方案代码可行性测试 非递归方案代码可行性测试 特点分析 计数排序代码实现代码可行性测试 特点分析 归并排序 VS 计数排序Release版本说明1w rand( ) 数据测试10w rand( ) 数据测试100w rand( ) 数据测试1000w rand( ) 数据测试 测试代码结语 欢迎来到决战排序之巅栏目 本期给大家带来的是归并排序与计数排序的实现与比较。 在上期决战排序之巅一中给大家带来了插入排序(希尔) 与 选择排序(堆排) 的实现与比较感兴趣的可以看看。 排序测试函数 void verify(int* arr, int n)
主要功能测试arr数组中的顺序是否全为非升序的顺序。 代码如下
void verify(int* arr, int n)
{for (int i 1; i n; i){assert(arr[i] arr[i - 1]);}
}如果arr数组中顺序不全为非升序则assert()直接终止程序 若全为非升序则程序可通过该函数。
归并排序
基本思想采用分治算法将已有的有序子序列进行合并得到完全有序的序列即先使每个子序列有序再使子序列所合并的序列有序。 归并排序的核心步骤就是分解与合并。
递归方案
如下图所示我们可以先将一组数据由大到小逐个分开再依次合并。 下图绿线为分解蓝线为合并。我们可以看到排序数据分解时当子序列内个数为1 时,不再分解随后进行依次的合并1 9 合并为1 9的子序列5 6合并成5 6的体序列同理可得3 8 2 7再让子序列合并1 9 6 5合并成1 5 6 9。3 8和2 7合并成2 3 7 8。最后两个字序列合并成1 2 3 5 6 7 8 9 至此归并排序完毕。 具体代码如下
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);assert(tmp);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}void MergeSort(int* a, int n)是我们排序的调用函数因为他的参数形式不宜用递归实现所以我们可以写一个子函数void _MergeSort(int* a,int begin,int end ,int* tmp)来实现主要程序的编写如下
void _MergeSort(int* a,int begin,int end ,int* tmp)
{if (begin end)return;int mid (begin end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);int left1 begin, right1 mid;int left2 mid 1, right2 end;int i 0;while (left1 right1 left2 right2){if (a[left1] a[left2])tmp[i] a[left2];elsetmp[i] a[left1];}while (left1 right1){tmp[i] a[left1];}while (left2 right2){tmp[i] a[left2];}memcpy(a begin, tmp, i * sizeof(int));
}我们先通过以下代码进行归并排序“分解”的实现 if (begin end)return; int mid (begin end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);当子序列内个数为1 时return 返回当子序列内个数大于1 时进行以下编写 有递归可知此时的小标区间为[begin , mid] 与 [mid 1 , end]是排好序的子区间所有此时我们只要将其合并好就可以了。 int left1 begin, right1 mid;int left2 mid 1, right2 end;int i 0;while (left1 right1 left2 right2){if (a[left1] a[left2])tmp[i] a[left2];elsetmp[i] a[left1];}while (left1 right1){tmp[i] a[left1];}while (left2 right2){tmp[i] a[left2];}memcpy(a begin, tmp, i * sizeof(int));最后将tmp上的数据拷贝到a的[begin , end]区间即可。 代码可行性测试
void _test()
{int n 100000000;int* arr (int*)malloc(sizeof(int) * n);for (int i 0; i n; i){arr[i] rand();}MergeSort(arr, n);verify(arr, n);free(arr);
}运行结果如下 程序通过verify(int* arr int n)函数,且成功运行代码无误。
非递归方案
在非递归方案中我们可以利用循环来实现主要实现过程如下视频所示 归并排序思想 我们可以定义一个gap并且gap的初始置为1用来表示子序列的最小个数为1随后在整体排完相邻两个子序列后gap乘以2此时数组内小标区间为 [ n ∗ g a p , n ∗ ( g a p ∗ 2 − 1 ) ] ∪ [ 0 , g a p − 1 ] , n ∈ N [n * gap , n * (gap * 2-1)]\cup[0 , gap-1] ,n\in N^ [n∗gap,n∗(gap∗2−1)]∪[0,gap−1],n∈N是有序的如此循环直到, n ≤ g a p n\leq gap n≤gap时跳出循环代码如下
void MergeSortNonR(int* a,int n)
{int* tmp (int*)malloc(sizeof(int) * n);assert(tmp);int gap 1;while (n gap){for (int i 0; i n; i gap * 2){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i gap * 2 - 1;int j begin1;if (end1 n begin2 n){break;}if (end2 n){end2 n - 1;}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}memcpy( a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tmp);
}我们先看如何分解利用gap来确定子序列的元数个数再利用for循环来实现两个相邻子序列的排序即下标区间[begin1,end1] , [begin2,end2]的排序 注意在分配完区间[begin1,end1] ,和[begin2,end2]后我们要对区间范围的有效性进行检查因为非递归的方案通过比较相邻的子序列gap以2的幂次方所增长适用的数组长度也为2的幂次方所以我们要对end1 , begin2 , end2进行检查如果end1 , begin2 大于数组总个数n时直接break即可因为此时的[begin1n-1]已经是有序的了如果end2大于n则令end2n-1此时我们只要排好[begin1,end2] , [begin2,n-1]即可,具体过程如下 for (int i 0; i n; i gap * 2){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i gap * 2 - 1;int j begin1;if (end1 n begin2 n){break;}if (end2 n){end2 n - 1;}//合并过程}合并过程与递归方案相同但需要注意的是数组拷贝的时候for循环依次拷贝一次。 代码可行性测试 程序通过verify(int* arr int n)函数,且成功运行代码无误。
特点分析
特性归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 时间复杂度O(N*logN) 空间复杂度O(N) 稳定性稳定
计数排序
基本思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。
代码实现
实现步骤
选出要排序数组a中的最值再相减求出数组的相对范围 n m a x − m i n 1 n max - min 1 nmax−min1用calloc开辟n个空间为tmp利用i遍历a让数组tmp[ a [ i ] − m i n a[i] - min a[i]−min]最后再遍历tmp , 此时tmp的数组下标 min就表示数据的大小tmp[数组下标]表示该数据的个数所以在此时为a直接赋值即可。 具体代码如下
void CountSort(int* a, int n)
{int max a[0], min a[0];int i 0;for (i 0; i n; i){if (max a[i]){max a[i];}if (min a[i]){min a[i];}}int* tmp (int*)calloc((max - min 1), sizeof(int));assert(tmp);for (i 0; i n; i){tmp[a[i] - min];}int j 0;for (i 0; i max - min 1; i){int count tmp[i];while (count--){a[j] i min;}}free(tmp);
}代码可行性测试 程序通过verify(int* arr int n)函数,且成功运行代码无误。
特点分析
特点分析计数排序在数据范围集中时效率很高但是适用范围及场景有限例如小数结构体字符串无法比较 时间复杂度O(MAX(N,范围)) 空间复杂度O(范围)
归并排序 VS 计数排序Release版本
说明
以下会分别对1w,10w,100w,1000w的数据进行100次的排序比较并计算出排一趟的平均值。
下面是用来生成随机数的代码可以确保正数与负数的随机分布。 for (i 0; i n; i){if (rand() % 2){arr3[i] arr2[i] arr1[i] -rand() i;}else{arr3[i] arr2[i] arr1[i] rand() - i;}}介绍就到这里了让我们来看看这100次排序中谁才是你心目中的排序呢 PS100次只是一个小小的测试数据有兴趣的朋友可以在自己电脑上测试更多的来比较哦。
1w rand( ) 数据测试 10w rand( ) 数据测试 100w rand( ) 数据测试 1000w rand( ) 数据测试 测试代码
void Test_MergeSort_CountSort()
{int n 10000000;int count 100;int* arr1 numcreate(n);int* arr2 numcreate(n);int* arr3 numcreate(n);int time1 0, time2 0, time3 0;int tmp count;while (tmp--){int i 0;for (i 0; i n; i){if (rand() % 2){arr3[i] arr2[i] arr1[i] -rand() i;}else{arr3[i] arr2[i] arr1[i] rand() - i;}}int begin1 clock();MergeSort(arr1, n);int end1 clock();int begin2 clock();MergeSortNonR(arr2, n);int end2 clock();int begin3 clock();CountSort(arr3, n);int end3 clock();time1 end1 - begin1;time2 end2 - begin2;time3 end3 - begin3;}printf(MergeSort: %.2f\n, (float)time1/count);printf(MergeSortNonR: %.2f\n, (float)time2 / count);printf(CountSort: %.2f\n, (float)time3 / count);free(arr1);free(arr2);free(arr3);
}从结果来看计数排序快于归并排序但它的局限性无法比较小数结构体与字符串 再看归并排序非递归类的要略胜一筹哦。
结语
看完之后谁才是你心目中的排序呢 欢迎留言让我们一起来期待在下一期 《决战排序之巅(三)》。
以上就是本期的全部内容喜欢请多多关注吧
