网站推广 营销,wordpress用户名无效,python基础教程pdf,短视频分享网站开发目录
一、归并排序
1.基本思想
2.归并排序的特性总结#xff1a; 3.代码实现#xff1a;
4.代码优化 #xff1a;
二、计数排序#xff08;非比较排序#xff09;
1. 概念#xff1a;
2.计数排序的特性总结#xff1a; 3.代码实现#xff1a; 一、归并排序
1.…目录
一、归并排序
1.基本思想
2.归并排序的特性总结 3.代码实现
4.代码优化
二、计数排序非比较排序
1. 概念
2.计数排序的特性总结 3.代码实现 一、归并排序
1.基本思想 归并排序 MERGE-SORT 是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法 Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 2.归并排序的特性总结 1. 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(N) 4. 稳定性稳定 3.代码实现
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;int mid (begin end) / 2;// [begin, mid] [mid1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);// 归并两个区间// ...int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;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 begin, tmp begin, sizeof(int) * (end - begin 1));
}
4.代码优化
在原代码基础上进行小区间优化能够提升一定的效率
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;//小区间优化if (end - begin 1 10){InsertSort(abegin, end - begin 1);return;}int mid (begin end) / 2;// [begin, mid] [mid1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);// 归并两个区间// ...int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;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 begin, tmp begin, sizeof(int) * (end - begin 1));
}二、计数排序非比较排序
1. 概念 思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中 计数排序非比较排序逻辑如下图借鉴网图 2.计数排序的特性总结 1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2. 时间复杂度 O(MAX(N, 范围 )) 3. 空间复杂度 O( 范围 ) 4. 稳定性稳定 3.代码实现
void CountSort(int* a, int n)
{int min a[0], max a[0];for (int i 0; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}int range max - min 1;int* countA (int*)malloc(sizeof(int) * range);memset(countA, 0, sizeof(int) * range);// 统计次数for (int i 0; i n; i){countA[a[i] - min];}// 排序int k 0;for (int j 0; j range; j){while (countA[j]--){a[k] j min;}}
}
