建网站选哪个,宁波网站建设设计图,网站优化公司哪家服务好,公共法律知识培训网站目录
1. 归并排序
1.1 递归实现
1.2 非递归实现
1.3 归并排序特性总结 2. 计数排序
代码实现 3. 总结 1. 归并排序 基本思想#xff1a; 归并排序#xff08;merge sort#xff09;是建立在归并操作上的一种有效的排序算法#xff0c;该算法是采用分治法#xff0…目录
1. 归并排序
1.1 递归实现
1.2 非递归实现
1.3 归并排序特性总结 2. 计数排序
代码实现 3. 总结 1. 归并排序 基本思想 归并排序merge sort是建立在归并操作上的一种有效的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 划分阶段通过递归不断地将数组从中间点分开。 合并阶段当数组中只有一个元素时停止划分开始合并将左右两个较短的子序列按照一定的规则合并。 拆分序列 (leftright)/2为中间点将数组拆分成两个无序序列循环拆分拆分到最后每个序列都是单独的一个元素再开始归并。 合并有序序列 从两个数列的第一个数开始谁小就先取谁放到临时数组中指针再向后走接着进行比较如果一个数列走完了另一个数列还有剩余直接把剩余的元素依次取下来放到临时数组中。 递归展开图
通过观察归并排序与二叉树后序遍历递归顺序相同。
1.1 递归实现
//归并
void merge(int* a, int* tmp, int left, int mid, int right)//左半区的起始位置 中间点 右半区结束位置
{int begin1 left, end1 mid;int begin2 mid 1, end2 right; //[left,mid] [mid1,right] //划分成[left,mid-1][mid,right]会造成死循环int i left;while (begin1 end1 begin2 end2)//左半区有元素并且右半区也有元素{if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}//归并左半区剩余元素while (begin1 end1){tmp[i] a[begin1];}//归并右半区剩余元素while (begin2 end2){tmp[i] a[begin2];}//将临时数组中归并后的元素拷贝到原数组当中memcpy(a left, tmp left, (right - left 1) * sizeof(int));
}
//划分和归并
void Msort(int* a, int* tmp, int left, int right)
{if (left right)return;//找中间点int mid (left right) / 2; //[begin,mid-1] [mid,end] //递归划分左半区域Msort(a, tmp, left, mid);//递归划分右半区域Msort(a, tmp, mid 1, right);//归并merge(a, tmp, left, mid, right);}
//归并排序入口
void MergeSort(int* a, int n)
{//开辟一个辅助数组int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail!);return;}Msort(a, tmp, 0, n - 1);//划分和归并free(tmp);//释放空间tmp NULL;
}复杂度分析 时间复杂度O(n*logn) 数组划分的深度是 logn而在每一层递归中合并操作的时间复杂度是 O(n)所以总的时间复杂度为O(n*logn)这个时间复杂度是在最好、最坏和平均情况下都成立的因为归并排序不依赖于原始数组的顺序。 空间复杂度O(n) 归并排序需要在归并过程中需要与原数组同样的存储空间存放归并结果还需要额外的空间来存储递归调用的栈占用空间 nlogn 。 1.2 非递归实现 定义一个变量gap规定gap为每组归并数据的数据个数gap1,2,4,8,16……1个和一个归并2个和2个归并4个和4个归并依次循环下去直到gapn。 //归并排序——非递归
void MergeSortNonRecur(int* a, int n)
{//开辟一个辅助数组int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail!);return;}//规定gap为每组归并数据的数据个数int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1; if (begin2 n)//第二组越界不存在这一组就不需要归并了{break;}if (end2 n)//第二组begin2没越界end2越界了修正一下继续归并{end2 n - 1;}printf([%d][%d][%d][%d] , begin1, end1, begin2, end2);int k i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[k] a[begin1];}else{tmp[k] a[begin2];} }while (begin1 end1){tmp[k] a[begin1];}while (begin2 end2){tmp[k] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}printf(\n);gap * 2;}free(tmp);tmp NULL;
}上面两条 if 语句是为了处理一下越界情况 非递归的迭代方法避免了递归时深度为log₂n的栈空间空间只是用到归并临时用的tmp数组空间复杂度为O(n),避免递归在时间性能上有一定的提升使用归并排序时尽量考虑用非递归方法。 1.3 归并排序特性总结 时间复杂度O(n*logn) 空间复杂度O(n) 稳定性稳定 缺点缺点在于需要O(N)的空间复杂度归并排序应用更多的是解决在磁盘中的外排序问题。 适用性归并排序适用于各种数据规模的排序而且对于大规模数据的排序效果较好。它的时间复杂度稳定在O(nlogn)不会因为数据规模的增大而导致时间复杂度的增加。由于其空间复杂度较高通常在内排序中不会使用归并排序而是选择快速排序。在外排序中对于无法一次性加载到内存的大规模数据进行排序归并排序则是一个很好的选择。 2. 计数排序 计数排序是一种非比较型排序算法适用于一定范围内的整数排序。在计数排序中我们不直接比较元素的大小而是利用数组索引来统计每个元素的出现次数。 思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中 要根据range的范围来创建统计数组count,比如上面数组值的范围是99~109如果按照最大值创建那就需要长度109的数组会造成极大的空间浪费。 所以变形一下每个元素在统计数组的位置为减去最小值之后的下标位置。 calloc函数开辟空间的时候会把空间的每个字节都初始化为0这就不需要我们手动去初始化了没有出现的数字在统计数组中就是0。 代码实现
void CountSort(int* a, int n)
{int min a[0], max a[0]; //找最大和最小值for (int i 1; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}int range max - min 1;//数值范围int* count (int*)calloc(range, sizeof(int));if (count NULL){perror(calloc fail!);return;}//统计次数for (int i 0; i n; i){count[a[i] - min];}//排序int j 0;for (int i 0; i range; i){while (count[i]--){a[j] i min;}}free(count);count NULL;
} 计数排序是稳定的排序算法时间复杂度为 O(n range)空间复杂度为 O(range)。但是计数排序对数据的要求较为严格只适合整数和范围集中的数据。 3. 总结
排序方法时间复杂度平均时间复杂度最好时间复杂度最坏空间复杂度稳定性冒泡排序O(n²)O(n)O(n²)O(1)稳定简单选择排序O(n²)O(n²)O(n²)O(1)不稳定直接插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序O(nlogn)~O(n²)O(n^1.3)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(nlogn)O(n²)O(logn)~O(n)不稳定
