如何制作手机商城网站,关键词快速上首页排名,家装公司排行榜,wordpress+博客主题目录 1.归并排序递归实现
代码
2.归并排序非递归
代码
3.比较快排、归并和堆排序
4.归并排序实现外排序 1.归并排序递归实现 我们之前对两个有序数组进行排序就用到了归并的思想#xff0c;对于两个有序数组#xff0c;我们分别取他们首元素比较大小#xff0c;取小的插…目录 1.归并排序递归实现
代码
2.归并排序非递归
代码
3.比较快排、归并和堆排序
4.归并排序实现外排序 1.归并排序递归实现 我们之前对两个有序数组进行排序就用到了归并的思想对于两个有序数组我们分别取他们首元素比较大小取小的插入到一个新开辟的数组中 归并排序的前提就是要有两个有序序列而且还要开辟一块新的空间来存放新的有序的数组。
那么对于一个无序的数组该如何使用归并排序呢 这一整个数组我们可以把它分成左右两个区间来看一个是 [0,4] ,一个是 [5,9] 而只要这两个区间有序了我们就有办法通过控制下标来进行归并排序。 怎么使两个子区间有序呢这就又回到了二叉树的结构这不就是相当于二叉树的后序遍历吗我们要先使两个字区间有序然后再对这两个字区间进行归并排序。 递推到最后的子问题就是 只有一个数据时beginend 递推到最后就开始返回了 代码
最终左右区间都有序之后再归并就能够将整个数组都排成有序了。我们首先将归并的逻辑写出来当一个序列左右区间都有序了之后我们就要进行归并合成一个新的有序序列。
归并逻辑
void _MergePartSort(int* a, int begin, int end,int*tmp)
{int mid begin (end - begin) / 2;int begin1 begin;int end1 mid;int begin2 mid 1;int end2 end;int index begin;//将两个有序区间归并到一起while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}//剩余的数据放进去while (begin1 end1)tmp[index] a[begin1];while (begin2 end2)tmp[index] a[begin2];//最后将新序列拷贝回原数组memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));
}
归并的逻辑我们写完了之后就要考虑如何实现后序遍历了后序遍历无非就是先递归排序子区间最后将这两个子区间归并成一个有序的序列
//归并排序实现
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;//先处理子区间int mid begin (end - begin) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);//归并_MergePartSort(a, begin, end,tmp);
}
最后我们的归并排序的主函数中还创建了一个动态开辟数组我们要记得释放掉。为什么我们要单独拿一层逻辑逻辑来创建一个数组呢我们每一次归并都需要用到一个额外的数组与其每一次都开辟一次不如直接开辟一个完整的能够对所有数据归并临时存放的数组这样更好管理方便释放。 //归并排序 创建新数组
void MergeSort(int* a, int begin, int end)
{assert(a);int* tmp (int*)malloc(sizeof(int) * (end - begin1));assert(tmp);_MergeSort(a, begin, end,tmp);free(tmp);
}
归并排序不会像快排的递归那样可能会栈溢出归并排序由于每一次区间都是均分的最多调用logN层栈帧而他还创建了一个额外的数组来归并数据所以他的总的空间复杂度就是O(N)。 2.归并排序非递归
归并排序的递归实现其实不难难的是他的非递归实现。对于归并排序我们能使用栈或者队列来实现非递归吗栈和队列实现起来十分的复杂后序遍历不适合栈和队列的特点那么我们就得想其他的的办法来解决了。
其实对于归并排序我们只需要两层循环就能够实现他的非递归。首先数组的每一个数都可以看成是有序的那么我们是不是可以直接对相邻的两个数进行递归呢这样一来每两个数为一组就都是有序的了。 这样就成了 n/2 个有序序列然后对这些数据 相邻两组 进行归并 这时候我们就发现了一个要注意的问题就是在分组的时候有可能并不是偶数组可能是奇数组或者有些组可能数据并不满 比如当原数组是十一个元素时在两两归并之后最后一组只有一个数据我们在用代码实现时要考虑到这些点。 我们要怎么控制这些分组呢我们知道当数据总个数为n时第一次分组都是 一个数与一个数进行归并而第二次就变成了 两个数的有序序列 与 两个数的有序序列进行归并 然后就是 四个数的有序序列和四个数的有序序列进行归并以此类推最后一次 就是 n/2 个数据的有序序列和 n/2个数据的有序序列进行归并这是在每一次都是偶数个组的时候也就是数据总数为 2 的次方。
首先我们假设是 gap 个有序数与 gap 个有序数进行归并先把单趟的归并逻辑理清楚。非递归的实现也要依赖于一个额外的数组。 //gap个数为一组两组进行归并int begin1 ;//第一组的开始int end1 begin1 gap-1;int begin2 begin1 gap;int end2 begin1 2 * gap - 1; int i 0;for (i 0; i end; i 2 * gap){//gap个数为一组两组进行归并int begin1 i;//第一组的开始int end1 begin1 gap - 1;int begin2 begin1 gap;int end2 begin1 2 * gap - 1;int index begin1;//一次归并while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}}
这边是一轮归并的逻辑而我们除了归并之外还需要拷贝数据回到原数组我们要如何拷贝呢
可以一次将一轮归并之后的tmp数组全部拷贝到原数组也可以每一次两两归并就拷贝回去。我们先用一次性拷贝。 然后我们要开始处理边界的问题了也就是前面说的数据不是完整的偶数组。 首先第一种情况就是最后的 end1刚好是 end而 beign2 和 end2 越界了这种情况怎么处理呢我们直接将 begin1 到end1 的数据写到tmp就行了。 而第二种情况就是最后递归的 begin1合法而end1 就已经越界了更不用谈begin2和end2了这时候我们则是将 beign1 到 n-1 的数据写到tmp中。 第一种和第二种情况的处理是一样的 if (end1 end)//第一组就越界了或者第一组的 end1 就是数组尾{while (begin1 end){tmp[begin1] a[begin1];begin1;}break;} 第三种越界就是第二组数据部分越界也就是 begin2 end,而end2end这时候这两组还要进行归并。
这时候我们只需要把end2 修改为 end 就行了。
这样一来我们就能写出第一轮的相邻两个数的的归并的代码
//非递归归并
void MergeSortNonR(int* a, int begin, int end)
{int* tmp (int*)malloc(sizeof(int)*(end - begin 1));assert(tmp);int gap1;int i 0;for (i 0; i end; i 2 * gap){//gap个数为一组两组进行归并int begin1 i;//第一组的开始int end1 begin1 gap - 1;if (end1 end)//第一组就越界了或者第一组的 end1 就是数组尾{while (begin1 end){tmp[begin1] a[begin1];begin1;}break;}int begin2 begin1 gap;int end2 begin1 2 * gap - 1;if (end2 end){end2 end;}int index begin1;//一次归并while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}}memcpy(a, tmp, sizeof(int) * (end-begin1));}这一层逻辑写完就简单了我们在写一层循环来控制 gap 就行了gap每一次都是上次的二倍而因为数据个数可能不是 2 的次方个所以最后一次的 gap n 。而数据个数 n 我们用传过来的参数表示就是 end-begin1。
最后在把tmp数组释放掉我们就完成了归并的非递归实现。
代码
//非递归归并
void MergeSortNonR(int* a, int begin, int end)
{int* tmp (int*)malloc(sizeof(int)*(end - begin 1));assert(tmp);int gap1;for (; gap end - begin 1; gap * 2){int i 0;for (i 0; i end; i 2 * gap){//gap个数为一组两组进行归并int begin1 i;//第一组的开始int end1 begin1 gap - 1;if (end1 end)//第一组就越界了或者第一组的 end1 就是数组尾{while (begin1 end){tmp[begin1] a[begin1];begin1;}break;}int begin2 begin1 gap;int end2 begin1 2 * gap - 1;if (end2 end){end2 end;}int index begin1;//一次归并while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}}memcpy(a, tmp, sizeof(int) * (end - begin 1));}free(tmp);
}
我们可以观察每一轮归并的结果来分析程序逻辑是否正确
gap为1时 gap为2时 gap为4时 gap为8时 这时候就已经完全排完了。 3.比较快排、归并和堆排序
void test()
{int N 1000000;int* a1 (int*)malloc(sizeof(int) * N);assert(a1);int* a2 (int*)malloc(sizeof(int) * N);assert(a2);int* a3 (int*)malloc(sizeof(int) * N);assert(a3);srand((unsigned int)time(NULL));for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];a3[i] a1[i];}int begin1 clock();HeapSort(a1, N);int end1 clock();printf(HeapSort:%d\n, end1 - begin1);int begin2 clock();QuickSort(a1,0, N-1);int end2 clock();printf(QuickSort:%d\n, end2 - begin2);int begin3 clock();MergeSort(a1,0, N-1);int end3 clock();printf(MergeSort:%d\n, end1 - begin1);free(a1);free(a2);free(a3);
}当要排序一百万个数据时 而排序十万个数据时 这里我们就能发现虽然我们解析他们的时间复杂度都是NlogN但是其实快排是要比另外两个排序快的首先是因为堆排序要建堆建堆的时间复杂度为N而选数的时间复杂度时NlogN所以他要比快排慢而归并排序则是因为他要开辟额外的空间同时我们拷贝数据回原数组时memset的时间复杂度也很高影响了我们的效率。 4.归并排序实现外排序
什么是外排序
我们前面讲的排序都是在内存中去排序数据因为他们的数据量都不是很大在内存中能放下他们都是内排序算法。
而当我们的数据量十分大时无法一次性放进内存中进行排序数据存在磁盘中也就是外存中这时候我们就需要改进前面学过的排序来实现对外存中的数据进行排序而其他的排序算法都只能在内存中排序只有归并排序能实现外排序所以归并排序既是一种内排序算法也是外排序算法。
为什么不直接在磁盘文件中进行排序呢第一文件是不支持随机读写的只能做一个串行的直接访问虽然我们可以用 fseek 函数来修改文件指针的位置但是当数据量很大的时候我们是顾不过来对文件指针的操作的。第二磁盘的访问速度以及数据挪动等操作速度都是远慢于内存的在实际应用中不适合在磁盘中操作数据。
外排序的思路是怎么样的呢
首先我们有一个放了数据的文件数据很大无法一次性放到内存中 虽然我们无法一次性全加载到内存中但是我们可以先将一部分数据放到内存中去排序数据的个数取决于内存的大小。 这时候内存中的数据我们就能够通过内排序算法进行排序了最好用快排因为堆排效率比不上快排而归并则还需要额外的空间内存本来就不够了所以对内存中的数据排序不能用归并。 我们将排序好的数据从内存中输出到一个小文件中 然后重复上述过程直到把数据都读完排好序之后都写到小文件中 这时候我们就能得到几个数据有序的小文件对这些有序的小文件我们就能进行归并排序了。 这样一来我们就得到了一个排好序的文件。 归并排序实现外排序的思想其实并不难难的是在操作的过程中的文件操作以及给文件取名的细节还有最后归并小文件时的迭代。
我们首先创建一个文件我们在实现代码的时候没必要用海量数据来实现也做不到。这就假设内存的空间就够存储一个 二十个数据的数组因为我们要用数组来接受文件中的数据我们还要考虑内排序算法调用堆栈的消耗我们在文件中存进100个随机数据范围在100~999之间然后再放上几个二位数与四位数
int main()
{FILE* fout fopen(data, w);srand((unsigned)time(NULL));for (int i 0; i 100; i){int data rand() % 900 100;fprintf(fout, %d\n, data);}fclose(fout);return 0;
}
我们先生成一个data文件然后手动添加几个数据进去便于我们最后结果的检验。
有一点要注意我们在这个示例中的文件名都不加后缀了因为加了后缀之后太过复杂在后面部分给文件取名的时候而C语言对文件名的操作并不是这么方便所以我们就不加文件后缀了。 假如这就是我们要排序的文件。
我们假设内存中最多就只能放二十个整形数据除去排序所需要的空间这时候我们每次要用一个数组来接受20个数据对他们进行排序之后再分别写入一个小文件中保存 int main()
{//FILE* fout fopen(data, w);//srand((unsigned)time(NULL));//for (int i 0; i 100; i)//{// int data rand() % 900 100;// fprintf(fout, %d\n, data);//}//fclose(fout);char filename[20] data;//测试小文件的个数int filenumRead_Sort(filename);printf(%d, filenum);return 0;
}
读取数据并排序放到小文件的函数
//读取数据排序写入小文件
int Read_Sort(char* filename)
{//内存中最多存储个数int N 20;int* a (int*)malloc(sizeof(int) * N);assert(a);FILE* pf fopen(filename, r);assert(pf);//记录小文件个数并用于小文件命名int n 0;char sfile[20] sorted;int data;//用于读取保存数据int i 0;//a数组下标//读取数据while (fscanf(pf,%d, data) ! EOF){if (i N-1)//先放19个数据{a[i] data;}else//放第20个数据{a[i] data;//把第20个数据放进数组//对这一组数据排序QuickSort(a, 0, N - 1);//小文件命名char file[20];n;sprintf(file, %s%d, sfile, n);//将小文件命名为sorted1 sorted2 ... ...FILE* foutfopen(file, w);assert(fout);for (int j 0; j i; j){fprintf(fout, %d\n, a[j]);//存数据的时候要注意格式到时候取数据的格式要与存数据的格式一样}//写完之后关闭文件fclose(fout);//i复原重新读取i 0;}}//最后要判断a数组中还有没有数据if (i ! 0){n;char file[20];sprintf(file, %s%d, sfile, n);FILE* fout fopen(file, w);assert(fout);for (int j 0; j i; j)fprintf(fout,%d\n, a[j]);fclose(fout);}fclose(pf);//返回小文件个数free(a);return n;
}我们可以看到一共生成了6个小文件 我们的data总数是110个前五个文件都有20个数据第六个文件右10个数据说明这一步是没问题的。 这一步完成之后下一步就是对着6个小文件进行归并了。
文件归并的过程中我们每次都只操作三个文件file1 和 file2 是要读取数据进行归并的文件而mfile适用于归并后数据存储的文件。
一次归并完之后将 file1 改成 mfilesorted12去管理生成的归并之后的文件 file2则修改为sorted3然后再创建一个mfilesorted123文件来进行新的归并。 这个过程是一个循环与迭代的过程 //文件归并
void Merge_File(int n)
{//初始条件char filename[20] sorted;char file1[20]sorted1;char file2[20];char mfile[20] sorted12;int i 0;for (i 1; i n; i){sprintf(file2, %s%d, filename, i1);//对file2修改FILE* fin1 fopen(file1, r);assert(fin1);FILE* fin2 fopen(file2, r);assert(fin2);FILE* fout fopen(mfile, w);assert(fout);//读取file1和file2数据int num1;int ret1fscanf(fin1, %d\n, num1);int num2;int ret2 fscanf(fin2, %d\n, num2);while (ret1!EOFret2!EOF){if (num1 num2){fprintf(fout, %d\n, num1);ret1 fscanf(fin1, %d\n, num1);}else{fprintf(fout, %d\n, num2);ret2 fscanf(fin2, %d\n, num2);}}//其中一个文件读取完了while (ret1 ! EOF){fprintf(fout, %d\n, num1);ret1 fscanf(fin1, %d\n, num1);}while (ret2 ! EOF){fprintf(fout, %d\n, num2);ret2 fscanf(fin2, %d\n, num2);}//都读取完之后关闭文件fclose(fin1);fclose(fin2);fclose(fout);//迭代memcpy(file1, mfile, 20);//将file修改为 sorted12sprintf(mfile, %s%d, mfile, i 2);//将mfile修改为 sorted123}}这里我们注意用num1和num2还有ret1和ret2来分别保存读取的数据和fscanf的返回值如果不用ret1和ret2的话要特别注意不要多读或者漏读数据yaoqingchuwenjianzhizhendedingwei
当我们把程序运行完之后我们去工程目录底下就能找到这一些列文件 我们可以打开最终的文件 sorted123456来验证一下程序的正确性 首先数据的个数是没问题的还是110个数据而我们手动添加的十个数据也都在文件的开头和结尾这说明排序也没问题。 外排序的实现其实最主要的不是排序的算法而是对文件的操作的熟悉外排序我们可能造成写程序用不到但是在以后处理大数据的排序时我们就可以借鉴这个思路。
总的来说归并排序不适合常规场景因为他有额外的空间消耗但是适合这种外排序。
