o2o网站建设最好公司,手机端网站建设公司,最新招商代理项目,做网站的外包需要分享客户信息目录
归并排序
1.基本思想#xff1a;
2.原理图#xff1a;
1#xff09;分解合并
2#xff09;数组比较和归并方法#xff1a;
3.代码实现#xff08;递归方式#xff09;#xff1a;
4.归并排序的非递归方式
原理#xff1a;
情况1#xff1a;
情况2
2.原理图
1分解合并
2数组比较和归并方法
3.代码实现递归方式
4.归并排序的非递归方式
原理
情况1
情况2
情况3
非递归代码实现
归并排序的特性总结
计数排序
基本思想
算法原理
算法升级
计算排序的特点
代码实现
排序算法复杂度及稳定性分析
什么时稳定性
各种常见排序算法的总结 归并排序
1.基本思想 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法, 该算法是采用分治法Divide andConquer的一个非常典型的应用。 将已有序的子序列合并得到完全有序的序列 即先使每个子序列有序再使子序列段间有序。 若将两个有序表合并成一个有序表称为二路归并。 2.原理图
1分解合并 第一层将一个数组分两个大组 第二层再继续分直到分成每组都只有一个为止 分解完了之后就是进行合并每两个小数组按顺序合并成一个大的数组 最终合并称为一个有序的集合 动图效果 归并排序是在原数组上进行的用一个临时数组来做归并把归并好的元素复制回原数组 2数组比较和归并方法 用上述长度为4的集合举例 第一步比较p1和p2位置元素的大小谁的小将谁的值放到p位置并将指向小的元素的那个指针并且将p 1比2小放1到p位置p1p ...... 第二步按第一步的步骤逐一比较直到有一个指针走到了集合之外如下 此时p2已经走到了集合外就可以退出循环了 第三步放一个循环将没走完的那个集合的剩余元素按顺序放到大集合种即可 当p走到大集合外面时结束循环 3.代码实现递归方式
//归并排序递归实现//归并子函数
//在遇到需要malloc扩容的函数时将malloc代码放入主函数另写一个子函数用来完成递归
void _MergeSort(int* a, int begin ,int end, int* temp)
{//最后只剩下一个数的时候就说明beginend返回if (begin end){return;}int mid (begin end) / 2;//[begin, mid] [mid1, end] 递归让子区间都有序_MergeSort(a, begin, mid, temp); //递归左半区_MergeSort(a, mid1, end, temp); //递归右半区//归并int begin1 begin, end1 mid; //左区间[begin1, end1]int begin2 mid 1, end2 end; //右区间[begin2, end2]int i begin;//如果左右两个区间都没有结束就继续只要有一个区间结束就终止while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){temp[i] a[begin1]; }else{temp[i] a[begin2];}}//将没走到头的区间按顺序放到后面while (begin1 end1){temp[i] a[begin1];}while (begin2 end2){temp[i] a[begin2];}//将临时区间的数据拷贝回原数组memcpy(a begin, temp begin, sizeof(int) * (end - begin 1));
}//归并主函数
void MergeSort(int* a, int n)
{int* temp (int*)malloc(sizeof(int) * n);if (temp NULL){perror(malloc fail);exit(-1);}_MergeSort(a, 0, n-1, temp);free(temp);temp NULL;
}
4.归并排序的非递归方式
原理 控制每次参与归并的元素即可可以先定义一个变量rangeN让其来划分区域 开始时rangeN1区域为1则是有序 i i 2*rangeN 定义 i 来区分每块区域 左区域[begin1,end1] 右区域[begin2,end2] 上图情况是一个特殊情况如果遇到不能被完全划分左右区域对称的情况分为以下三种
情况1
当最后一个区域进行归并时最后一组的左区间越界所以需要对左区间的end1进行控制 情况2
当最后一个区域进行归并时最后一组的右区间全部越界所以需要对右区间的begin2进行控制 情况3 当最后一个小组进行归并时由于右区间越界所以我们需要对右区间end2进行控制 非递归代码实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int)*n);if (tmp NULL){perror(malloc fail);exit(-1);}// 归并每组数据个数从1开始因为1个认为是有序的可以直接归并int rangeN 1;while (rangeN n) {for (int i 0; i n; i 2 * rangeN){// [begin1,end1][begin2,end2] 归并int begin1 i, end1 i rangeN - 1;int begin2 i rangeN, end2 i 2 * rangeN - 1;int j i;// end1 begin2 end2 越界的三种情况//一定需要按顺序进行判断不然会出错//end1越界情况1//解决直接退出本次循环可以不让后面的进行归并再下一次循环时再排序if (end1 n){break;}//begin2出界情况2//解决直接退出本次循环可以不让后面的进行归并再下一次循环时再排序else if (begin2 n){break;}//end2越界情况3//解决让end2等于数组最后的下标else 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));}rangeN * 2;}free(tmp);tmp NULL;
} 归并排序的特性总结 归并的缺点在于需要O(N)的空间复杂度 归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定 计数排序
基本思想 之前学习的排序无论是希尔排序还是堆排序都用的是比较两个数大小的方式进行的排序 而计数排序不是用比较的方法来进行排序的它利用的是数组下标的计数来进行的排序 具体实现方法如下 算法原理 现假设有一组0~4的数据需要排序{ 233403243 } 创建一个临时数组temp来依次记录每个数的出现次数 原数组中 0出现了1次就在temp下标为0的位置记录1 1没有出现 就在temp下标为1的位置记录0 2出现了2次就在temp下标为0的位置记录2 3出现了4次就在temp下标为0的位置记录3 4出现了2次就在temp下标为0的位置记录2 数组每一个下标位置的值代表了数列中对应整数出现的次数。
有了这个 “统计结果”排序就很简单了。直接遍历数组输出数组元素的下标值元素的值是几就输出几次 这样就能得到一个有序序列了
这就是计数排序的过程因为他没有进行数与数之间的比较 所以他的性能甚至快过那些O( log N) 的排序
可以看到上面的排序是一种特殊情况那如果我们要排序的数组是 9000~9009那么是不是得浪费前九千多个空间
又或者是在原数组里面有负数的情况下是不是九不能进行计数排序了
这就要对现有的算法进行一些小小的升级了
算法升级
例如我们有一组这样的数900490019002900590049001
这个数组最大是9005但最小的数是9001如果用长度为9005的数组那么按照上面的方法排序肯定会太过浪费
事实上我们只需要开辟大小为5的数组即可最大数 - 最小数 19005 - 9001 1 5
用下标为0的记录9001用下标为4的记录9005 当然对于负数也一样可以使用这里就不一一展示了 计算排序的特点 稳定性稳定时间复杂度Onk空间复杂度Onk 对于数据率不是很大并且数据比较集中时计数排序是一个很有效的排序算法 计数排序的局限性 不能对小数进行排序只适用于整数 代码实现
分4步实现
找到数组中的最大最小值计算范围开辟临时数组空间统计相同元素出现次数根据计数结果将序列依次放回原来的数组中
//计数排序
void CountSort(int* a, int n)
{//确定数组里面的最大最小值int max a[0], min a[0];for (int i 1;i n;i){if (a[i] min)min a[i];if (a[i] max)max a[i];}//范围 最大值 - 最小值 1//比如从 0 到 9 有10个数int range max - min 1;//用calloc开辟range个大小为int的空间并给每个元素赋值为0int* countA (int*)calloc(range, sizeof(int));if (countA NULL){perror(calloc fail);exit(-1);}//统计相同元素出现的次数for (int i 0;i n;i){//a[i] - min 是a[i]下标在countA里面对应的相对位置countA[a[i] - min];}//排序根据计数结果将序列依次放回原来的数组中int k 0;for (int j 0;j range;j){while (countA[j]--){//j min 就是数组元素的大小a[k] j min;}}free(countA);
} 排序算法复杂度及稳定性分析
什么时稳定性 稳定性的价值 比如再考试排名的时候第三名种有三个人的成绩相同那么如果先交卷的人是第三名的话就要去再成绩排序的时候保证其稳定性 各种常见排序算法的总结
