工信部外国网站备案,做导师一般去什么网站找素材,上海专业网站建设 公司,建筑工程网上竣工验收入口前言#xff1a;在前面我们讲了各种常见的排序#xff0c;今天我们就来对排序部分收个尾#xff0c;再来对归并排序通过递归和非递归的方法进行实现#xff0c;与对计数排序进行简单的学习。 #x1f496; 博主CSDN主页:卫卫卫的个人主页 #x1f49e; #x1f449; 专栏…前言在前面我们讲了各种常见的排序今天我们就来对排序部分收个尾再来对归并排序通过递归和非递归的方法进行实现与对计数排序进行简单的学习。 博主CSDN主页:卫卫卫的个人主页 专栏分类:数据结构 代码仓库:卫卫周大胖的学习日记 关注博主和博主一起学习!一起努力 目录 C语言排序算法 - 归并排序与计数排序归并排序 - 递归模拟实现归并排序的实现步骤 归并排序-非递归模拟实现计数排序 C语言排序算法 - 归并排序与计数排序
归并排序 - 递归模拟实现
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤。
分解将数组中的元素分成两个部分再将那俩个部分分成两个部分直到分成只剩一个元素不能分解为止。将分解后的元素俩俩依次归并并且再归并的过程中对齐进行排序因此归并完成的时候也就排序完成了如下图所示。 归并排序的实现步骤
将俩个有序数列合并后进行排序。开辟一块临时空间存间将两个序列中的较小值依次放入当有一个序列走到其尾部的时候退出循环结束排序。我们需要考虑当一个数列走到尾部的时候但另一个序列并没有完成排序情况因此找到那个没有走完的数列让其直接全部尾插到开辟的临时空间的尾部即可(如下图所示)。归并排序是一个非常经典的分治问题因此我们通过递归把数组不断分为俩个部分然后依次对其进行排序
代码实现:
void _MergeSort(int* a, int begin,int end,int* tmp)//归并排序
{if (begin end)return;int mid (begin end) / 2;_MergeSort(a, begin, mid, tmp);//分为左半边 a[begin] | a[mid]_MergeSort(a, mid 1, end, tmp);int begin1 begin;int begin2 mid 1;int i begin1;int end1 mid;int end2 end;while (begin1 end1 begin2 end)//排序{if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}//此时可能出现没有走完的情况while (begin1 end1){tmp[i] a[begin1];}while (begin2 end){tmp[i] a[begin2];}memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int));//拷贝回去}void MergeSort(int* a, int n)
{assert(a);int* tmp (int*)malloc(sizeof(int) * n);//开辟临时空间if (tmp NULL){printf(malloc fail\n);exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
函数测试:
void Test_MergeSort()
{int a[] { 1,2,30,0,99,1,7,8,2,11,0,3,13 };MergeSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));}int main()
{Test_MergeSort();
}运行结果: 归并排序-非递归模拟实现
归并排序的非递归实现是非常复杂的一个算法在快速排序中我们使用栈来存储待排数组的左右区间模拟递归的过程然而在归并排序中我们无非用栈来实现因为我们无非将分解后的区间在通过栈来合并因此我们在归并排序中不能这么实现。 实现思路:
还记得我们在递归实现的过程中是将其直接拆分成无法再进行拆分的单个元素嘛我们在这直接通过一个gap将这个数组直接看成拆分后的数组然后直接对其进行归并。我们将间距为1的数组依次合并后我们在让gap变为4然后再对这一数组元素进行依次合并然后以此类推直到gap比我们的数组的元素个数还大时停止排序即可。我们需要考虑边界问题即数组中的元素不一定总是二的倍数因此我们需要考虑第一个数组越界第二个数组全部越界和第二个数组部分越界这三种情况。下图是对gap为1的部分图 代码实现:
void MergeSortNoR(int* a, int n)//归并排序 -- 非递归
{int* tmp (int*)malloc( n * sizeof(int));int gap 1;while (gap n){int i 0;for (i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;//第一个数组的区间int begin2 i gap, end2 i 2 * gap - 1;//此时第二个数组的区间if (end1 n)break;if (begin2 n)break;if (end2 n)end2 n - 1;int j i;//此时合并数组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, (end2 - i 1) * sizeof(int));//拷贝回去}gap * 2;}}函数测试: void Test_MergeSortNoR()
{int a[] { 1,2,30,0,99,1,7,8,2,3 };MergeSortNoR(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}
int main()
{Test_MergeSortNoR();return 0;
}运行结果: 计数排序
计数排序是一种非比较排序算法它的基本思想是统计每个元素在待排序序列中出现的次数然后依次按照元素值的大小将元素按照出现的次数放入有序序列中。计数排序是一种稳定排序算法但是它只适用于元素取值范围较小且分布较均匀的情况 统计元素出现的次数遍历待排序序列统计每个元素出现的次数并记录在一个辅助数组中(通常辅助数组的大小为最大元素的大小)。 计算元素的位置根据元素出现次数的累加值计算出每个元素在有序序列中的位置。 将元素放入有序序列中根据元素的位置将元素依次放入有序序列中。 将辅助数组中计数不为0的数依次传给原数组此时即可完成排序. 代码实现:
void CountSort(int* a,int n)//计数排序
{int max a[0];int 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(max1 ,4);if (tmp NULL)//如果空间申请失败报个错并中止程序{perror(calloc);return;}for (i 0; i n; i){tmp[a[i]];}int j 0;for (i 0; i max 1; i){while (tmp[i]){a[j] i;tmp[i]--;}}}函数测试:
void Test_CountSort()
{int a[] { 1,0,0,2,333,3,0,99 };CountSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));}
int main()
{Test_CountSort();}运行结果: 我们思考一下如果数组每次都是开辟最大的元素的个数的时候是不是会照成空间上的一种浪费并且如果我们需要存储有负数的时候我们又该怎么办解决办法
我们找到数组中的最大值和最小值让其相减此时我们让其数组中的每个元素都可以因此往前挪动了即最小值无论它是多少它都会在0这个位置最大值也会在其相对映射的地方。同理开辟最大值减去最小值加1的空间即可并不需要额外再多开辟空间。
代码优化实现:
void CountSort(int* a,int n)//计数排序
{int max a[0];int 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 range max - min 1;int* tmp (int*)calloc(range ,4);if (tmp NULL)//如果空间申请失败报个错并中止程序{perror(calloc);return;}for (i 0; i n; i){tmp[a[i] - min];}int j 0;for (i 0; i range; i){while (tmp[i]){a[j] i min;tmp[i]--;}}}函数测试:
void Test_CountSort()
{int a[] { 1,-1,-3,-10,0,2,333,3,0,-3,99 };CountSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));}运行结果 结语今天的内容就到这里吧谢谢各位的观看如果有讲的不好的地方也请各位多多指出作者每一条评论都会读的谢谢各位。 这里也祝各位寒假快乐哦
