汕尾住房和城乡建设局网站,巩义推广网站哪家好,做平面设计必看的网站,网站开发计划和预算文章目录 1. 快排之三路划分1. 1 三路划分的诞生由来1. 2 三路划分的具体思路1. 3 代码实现 2. 快排之自省排序2. 1 自省排序的目的2. 2 自省排序的思路2. 3 自省排序的实现代码 3. 归并排序外排序3. 1 外排序介绍3. 2 归并排序外排序的思路3. 3 归并排序的实现代码 1. 快排之三… 文章目录 1. 快排之三路划分1. 1 三路划分的诞生由来1. 2 三路划分的具体思路1. 3 代码实现 2. 快排之自省排序2. 1 自省排序的目的2. 2 自省排序的思路2. 3 自省排序的实现代码 3. 归并排序外排序3. 1 外排序介绍3. 2 归并排序外排序的思路3. 3 归并排序的实现代码 1. 快排之三路划分
1. 1 三路划分的诞生由来 通过详解八大排序三------快速排序的介绍。我们可以知道决定快排性能的关键是key的寻找若是每次寻找的key都能将数组二分之一那么快排的性能最佳若是每次寻找的key都是将数组分成 1 和 N-1 个数那么快排的时间复杂度就是O(N^2)。 通过 前后指针 和 寻找随机key 我们可以解决绝大部分数组的找key需求。但是也会有一小部分的数组需求没有实现。 例如 在面对含有大量重复数据的数组时hoare版本 和 lomuto版本 的性能都有一定程度的退化。而三路划分是针对大量重复数据的找key方法。 1. 2 三路划分的具体思路 三路划分的核心思路可以理解为 hoare版本 和 lomuto版本 的结合将数组划分成三个区域比key小的区域A等于key的区域B大于key的区域C。 通过左右指针的方式将小于key的数放进区域A大于key的数放进区域C。 再对区域A和C进行划分。直到全部划分完成。 具体的实现思路 key默认取left位置的值。 left指向区间最左边right指向区间最后边cur指向left1位置。 cur遇到比key小的值后跟left位置交换换到左边leftcur。 例如上面的数组由于1 6所以1换到6的位置上。 一直重复直到 left 交换完。得到 cur遇到比key大的值后跟right位置交换换到右边right-- 。 接着以上述数组举例。左边数组交换完成接着交换右边数组 重复交换得到 cur遇到跟key相等的值后cur。 直到cur right结束 最终得到 这样就将数组分成了三个区域。 1. 3 代码实现
//三路划分
void ThreeWaySort(int* arr, int left, int right)
{if (left right){return;}//取一个随机值当keyint randi left (rand() % (right - left 1));Swap(arr[left], arr[randi]);int key arr[left];int cur left 1;int begin left,end right;while (cur right){if (arr[cur] key){Swap(arr[left], arr[cur]);}else if (arr[cur] key){Swap(arr[cur], arr[right--]);}else {cur;}}ThreeWaySort(arr, begin, left - 1);ThreeWaySort(arr, right 1, end);
}2. 快排之自省排序
2. 1 自省排序的目的 自省排序的诞生和三路划分相似都是原有的排序在面对新的问题时出现效率不足的情况。 三路划分面对数组中含有大量重复数据的情况具有显著的性能提升。但是在其他情况下就很一般同时三路划分相比一般的快排具有一定的损耗。 这个时候就有自省排序的出现。 2. 2 自省排序的思路 自省排序的本质很简单。就是通过一个深度检测器—可以理解为当前排序的时间复杂度检测器。判断当前快排的深度有没有超过logn。超过了就说明当前排序的效率是有问题的。然后接下来过程就不再使用快排而是使用堆排序进行排序。 2. 3 自省排序的实现代码
void AdJustDown(int* arr,int sz,int parent)
{int child parent * 2 1;while (child sz){if (child 1 sz arr[child 1] arr[child]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}void HeapSort(int* arr, int sz)
{for (int i (sz - 1 - 1) / 2; i 0; --i){AdJustDown(arr, sz, i);}int end sz - 1;while (end 0){Swap(arr[0], arr[end]);AdJustDown(arr, end, 0);--end;}
}void InsertSort(int* arr, int sz)
{for (int i 1; i sz; i){int end i - 1;int tmp arr[i];while (end 0){if (tmp arr[end]){arr[end 1] arr[end];--end;}else {break;}}arr[end 1] tmp;}
}void IntroSort(int* arr,int left,int right,int depth,int defaultDepth)
{if (left right){return;}if (right - left 1 16)//当需要排序的数据总数小于16就可以使用选择排序这时这个排序的效率是最高的{InsertSort(arr left,right - left 1);return;}if (depth defaultDepth)//深度检测器。深度大于一定程度调用堆排序{HeapSort(arr left, right - left 1);return;}depth;int begin left, end right;int randi left (rand() % (right - left 1));Swap(arr[left], arr[randi]);//随机数取keyint prev left, cur prev 1;int keyi left;while (cur right){if (arr[cur] arr[keyi] prev ! cur){Swap(arr[cur], arr[prev]);}cur;}Swap(arr[prev], arr[keyi]);keyi prev;//使用的是lomuto版本的快排IntroSort(arr,begin,keyi - 1,depth,defaultDepth);//depth是当前的深度defaultDepth是预定的深度。//depth超过dedaultDepth就说明深度有问题IntroSort(arr,keyi 1,end,depth,defaultDepth);
}void IntroQuickSort(int* a, int left, int right)
{int depth 0;int logn 0;int N right - left 1;for (int i 1; i N; i * 2){logn;//计算目标深度}IntroSort(a, left, right, depth, logn * 2);
}3. 归并排序外排序
3. 1 外排序介绍
外排序External Sorting是指能处理极大量数据的排序算法。通常来说外排序处理的数据不能一次装入内存只能放在读写较慢的外存储器(通常是硬盘)上。外排序通常采用的是⼀种“排序-归并”的策略。在排序阶段先读入能放在内存中的数据量将其排序输出到⼀个临时文件依此进行将待排序数据组织为多个有序的临时文件。然后在归并阶段将这些临时文件组合为⼀个大的有序文件也即排序结果。
3. 2 归并排序外排序的思路
读取n个值排序后写到file1再读取n个值排序后写到file2。file1和file2利用归并排序的思想依次读取比较取小的尾插到mfilemfile归并为一个有序文件。将file1和file2删掉mfile重命名为file1。再次读取n个数据排序后写到file2。继续走file1和file2归并重复步骤2直到文件中无法读出数据。最后归并出的有序数据放到了file1中。 3. 3 归并排序的实现代码
#includestdio.h
#includetime.h
#includestdlib.hvoid Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}int compare(const void* a,const void* b)
{return (*(int*)a - *(int*)b);
}int ReadNDataSortToFile(FILE* fout, int n, const char* file1)
{int* a (int*)malloc(sizeof(int) * n);//创建好一个数组放下抽取出的数据if (a NULL){perror(malloc error!);return 0;}int x 0;//创建一个数用来记录抽取出的数据int j 0;for (int i 0; i n; i){if (fscanf(fout, %d, x) EOF)//从文件中抽取的数据break;//如果x EOF说明文件中所有的数均已被抽出跳出循环a[j] x;//j的大小等于已经被抽取的数据}if (a 0)//如果上面的程序正常运行而数组a是空的说明这个文件是空的已经没有数据了{free(a);//那么就不需要继续抽取文件直接退出return 0;}qsort(a, j, sizeof(int), compare);//给抽出的数据排好序//打开文件file1和file2用来存储抽取出的排序好的数据mfile用来存储归并好的两个文件/*const char* file1 file1.txt;const char* file2 file2.txt;const char* mfile mfile.txt;*/FILE* fin fopen(file1, w);//创建一个fin文件用来放置排好序的数据if (fin NULL){free(a);perror(fopen error!);return 0;}for (int i 0; i j; i){//阅读文件fprintf(fin, %d\n, a[i]);//将数据放置进文件中}free(a);//释放数组fclose(fin);//关闭文件return j;//返回的是实际读取到的数据个数。没有数据就返回0。
}void MergeSortFile(const char* file1, const char* file2, const char* mfile)
{//创建好三个临时文件用来存储排序好的数据FILE* fout1 fopen(file1, r);if (fout1 NULL){perror(fopen1 error!);return 0;}FILE* fout2 fopen(file2, r);if (fout2 NULL){perror(fopen2 error!);return 0;}//但是你要往这个文件中写入就应该用w的方式打开FILE* mfin fopen(mfile, w);//这里用w的方式打开if (mfin NULL){perror(mfin error!);return 0;}//下面是利用归并排序思路。把比较的数据换成打开文件的形式int x1 0, x2 0;int ret1 fscanf(fout1, %d, x1);//把fout1的第一个数据赋值给retint ret2 fscanf(fout2, %d, x2);//把fout2的第一个数据赋值给ret//将两个文件的数据进行比较由小到大依次放进mfile文件中while (ret1 ! EOF ret2 ! EOF){if (x1 x2){fprintf(mfin, %d\n, x1);ret1 fscanf(fout1, %d, x1);//上一个数据放置完成。赋值下一个数据}else{fprintf(mfin, %d\n, x2);ret2 fscanf(fout2, %d, x2);}}//上面while跳出的条件意味着有一个文件的数据没有比较完成。这里对剩余数据进行判断while (ret1 ! EOF){fprintf(mfin, %d\n, x1);ret1 fscanf(fout1, %d, x1);}while (ret2 ! EOF){fprintf(mfin, %d\n, x2);ret2 fscanf(fout2, %d, x2);}//判断完成需要关闭文件 /*文件使用三部曲1.打开文件2.读取文件3.关闭文件*/fclose(fout1);fclose(fout2);fclose(mfin);
}//创建一个含有随机N个数据的文件
void CreateNData()
{int n 1000000;srand(time(0));const char* file data.txt;FILE* fin fopen(file,w);if (fin NULL){perror(fopen error!);return 0;}for (int i 0; i n; i){int x rand() i;fprintf(fin, %d\n, x);}fclose(fin);
}int main()
{//CreateNData();//创建三个文件用来排序const char* file1 file1.txt;const char* file2 file2.txt;const char* mfile mfile.txt;//给待排序数组创建一个临时文件FILE* fout fopen(data.txt, r);if (fout NULL){perror(fout fopen error!);return 0;}int m 100000;//这个是读取要排序的数据从fout里读取是读取到这个file1和file2这个文件中//每个文件读取m个数据ReadNDataSortToFile(fout, m,file1);//这个fout是一个已经打开的文件怎么能再次打开呢ReadNDataSortToFile(fout, m, file2);//由于data.txt的文件非常大一次排序不了全部的数据所以要多次排序while (1)//循环多次排序{//把这个file1和file2中的数据在归并到这个mfile中MergeSortFile(file1, file2, mfile);//删除file1和file2remove(file1);remove(file2);//将mfile重命名为file1rename(mfile, file1);int n 0;if ((n ReadNDataSortToFile(fout, m, file2)) 0)//n0说明文件中已经没有数据需要排序了break;}return 0;
}
