番禺网站开发哪家强,电商平台入驻,WordPress报错关闭,做网站的主要作用常见的内排序算法
插入排序
直接插入排序
原理#xff1a;相当于扑克牌变成有序#xff0c;先拿第一张#xff0c;把他调节成有序#xff0c;再拿第二张#xff0c;与第一张相比找到第二张的位置#xff0c;再继续拿第三张#xff0c;以此类推。
void InsertSort(in…常见的内排序算法
插入排序
直接插入排序
原理相当于扑克牌变成有序先拿第一张把他调节成有序再拿第二张与第一张相比找到第二张的位置再继续拿第三张以此类推。
void InsertSort(int* arr, int n)
{for (int i 1; i n; i){int end i - 1;int tmp arr[i];while (end 0){if (tmp arr[end]){arr[end 1] arr[end];arr[end] tmp;}else{break;}end--;}}
}//时间复杂度为O(N^2),逆序时间复杂度最坏由于插入排序在有序的时候时间复杂度为O(N),在逆序时时间复杂度为O(N^2),所以如果我们想加快排序的速度我们可以先对他进行一个预排序然后再进行一个插入排序。
希尔排序
原理间隔为gap的分为一组假设下图的gap为3总计gap组 也就是说{34111}分为一组{9564}和{31264}分为一组依次往前排序和插入排序很像都是前面先排好再排下一个
void ShellSort(int* arr, int n)//先搞一个预排的雏形gap假设为3
{int gap 1;for (int k 0; k gap; k){for (int j k; j n - gap; j gap){int end j;int tmp arr[end gap];while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}}
}
下面就可以确定gap的取值了
void ShellSort(int* arr, int n)
{int gap n;while (gap 1){gap gap / 3 1;//这样gap最后一定是1相当于一个插入排序for (int k 0; k gap; k){for (int j k; j n - gap; j gap){int end j;int tmp arr[end gap];while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}}}
}选择排序
选择排序
void SelectSort(int* arr, int n)
{int begin 0, end n - 1;while (begin end){int maxi begin;int mini end;for (int i begin; i end; i){if (arr[i] arr[maxi]){maxi i;}if (arr[i] arr[mini]){mini i;}}swap(arr[begin], arr[mini]);if (begin maxi){maxi mini;}swap(arr[end], arr[maxi]);begin;end--;}
}堆排
typedef struct heap
{int* arr;int size;int capacity;
}heap;
//向下调整
void AdjustDown(int* arr, int begin, int n)
{int father begin;int child 2 * father 1;while (childn){if (child 1 n arr[child] arr[child 1]){child;}if (arr[father] arr[child]){swap((arr[father]), (arr[child]));father child;child 2 * father 1;}else{break;}}
}
//向上调整
void AdjustUp(int* arr, int n, int end)
{int child end - 1;while (child 0){if (child 1 n arr[child] arr[child 1]){child;}int father (child - 1) / 2;if (arr[child] arr[father]){swap((arr[child]), (arr[father]));}child father;}
}
//堆初始化
void HeapInit(heap* obj)
{assert(obj);obj-arr (int*)malloc(sizeof(int) * 4);if (obj-arr NULL){perror(malloc fail);return;}obj-capacity 4;obj-size 0;
}//堆插入
void HeapPush(heap* obj, int val)
{assert(obj);if (obj-size obj-capacity){int* tmp (int*)realloc(obj-arr, obj-capacity * 2 * sizeof(int));if (tmp NULL){perror(malloc fail);return;}obj-arr tmp;obj-capacity * 2;}obj-arr[obj-size] val;obj-size;AdjustUp(obj-arr, 0, obj-size);
}//堆排序
void HeapSort(int* arr, int n)
{//建大堆for (int i 0; i n; i){AdjustUp(arr, n, i 1);}for (int i n - 1; i 0; i--){swap(arr[0], arr[i]);AdjustDown(arr, 0, i);}
}交换排序
冒泡排序
void BubbleSort(int* arr, int n)
{for (int i 0; i n; i){bool flag true;for (int j 0; j n - i - 1; j){if (arr[j] arr[j 1]){swap(arr[j], arr[j 1]);flag false;}}if (flag)break;}
}由于希尔排序的预排序是一个变化的过程所以希尔排序的时间复杂度极其复杂我们记住一个结论希尔排序的时间复杂度约为O(N^1.3)要注意的是希尔排序在最后一次循环中gap必须为1
快速排序
霍尔排序
霍尔排序以数组中某一个数作为基准值按照该排序把待排序集合分为两部分这个数左边的值都比这个数小这个数右边的值都比这个数的大再用递归重复此过程设置一个left指针一个right指针left指针从0位置开始right指针从n-1的位置开始left指针遇到比中间值key大的与right指针遇到比中间值key小的位置交换
int HoareSortPart(int* arr, int begin,int end)
{int left begin1, right end, key begin;while (left right){while (left right arr[right] arr[key]){right--;}while (left right arr[left] arr[key]){left;}swap(arr[left], arr[right]);}swap(arr[key], arr[left]);return left;
}//快速排序 Hoare版本
void HoareSort(int* arr, int begin,int end)
{if (begin end){return;}int mid HoareSortPart(arr, begin, end);HoareSort(arr, begin, mid - 1);HoareSort(arr, mid 1, end);
}关于为什么要让right指针先走归根结底是为了让left指针和right指针相遇的时候得到的位置所在的值比中间值key要小我们可以把left指针与right指针相遇分为两种情况一种是left遇到right指针另一种是right指针遇到left指针 一.left遇到right指针因为一个循环是right先走所以right指针已经遇到了比key小的值并且还没有交换所以left遇到right时遇到的就是比key小的数。 二.right指针遇到left指针因为right指针在走也就是上一个循环里的left指针已经走完了并且已经交换了数字所以left位置的值应该是小于或者等于key的right再遇到left遇到的就是比key小的数所以综上所述无论是left遇到right还是right遇到left最终得到的数都是小于key或者等于key的。
挖坑法
左右交替选择数左边left指针选出比key大的值右边right选出比key小的值覆盖原来的坑直到left指针与right指针相遇再把key放入最后left和right相遇的坑
int HoleSortPart(int* arr, int begin, int end)
{int key arr[begin];int left begin, right end;int hole begin;while (left right){while (left right arr[right] key){right--;}arr[hole] arr[right];hole right;while (left right arr[left] key){left;}arr[hole] arr[left];hole left;}arr[hole] key;return hole;
}void HoleSort(int* arr, int begin, int end)
{if (begin end){return;}int mid HoleSortPart(arr, begin, end);HoleSort(arr, mid 1, end);HoleSort(arr, begin, mid - 1);
}双指针法
cur找小prev前面的数都比key小翻滚的往后走
int QuickSortPart(int* arr, int begin, int end)
{int prev begin, cur begin 1;int key arr[begin];while (cur end){if (arr[cur] key){prev;swap(arr[cur], arr[prev]);}cur;}swap(arr[begin], arr[prev]);return prev;
}void QuickSort(int* arr, int begin, int end)
{if (begin end){return;}int mid QuickSortPart(arr, begin, end);QuickSort(arr, begin, mid - 1);QuickSort(arr, mid1, end);
}快排的劣势
快排若每次都取左边的那个数作为中间值时如果数组有序快排的时间复杂度会达到O(N^2)而若每次选取到的是数组的中位数的时候效率是最高的为了改变这一劣势我们引入三数取中算法。
三数取中算法
int GetMidIndex(int* arr, int left, int right)
{int mid (left right) / 2;if (arr[left] arr[right]){if (arr[mid] arr[left])return left;else if (arr[mid] arr[right])return right;elsereturn mid;}else//arr[left]arr[right]{if (arr[mid] arr[right])return right;else if (arr[mid] arr[left])return left;elsereturn mid;}
}三数取中后的三种快排算法如下记得要取完值后和begin位置的值互换
int HoareSortPart(int* arr, int begin,int end)
{int left begin, right end;int tmp GetMidIndex(arr, begin, end);swap(arr[tmp], arr[begin]);int key begin;while (left right){while (left right arr[right] arr[key]){right--;}while (left right arr[left] arr[key]){left;}swap(arr[left], arr[right]);}swap(arr[key], arr[left]);return left;
}//快速排序 Hoare版本
void HoareSort(int* arr, int begin,int end)
{if (begin end){return;}int mid HoareSortPart(arr, begin, end);HoareSort(arr, begin, mid - 1);HoareSort(arr, mid 1, end);
}//快速排序 挖坑法版本
int HoleSortPart(int* arr, int begin, int end)
{int tmp GetMidIndex(arr, begin, end);swap(arr[tmp], arr[begin]);int key arr[begin];int left begin, right end;int hole begin;while (left right){while (left right arr[right] key){right--;}arr[hole] arr[right];hole right;while (left right arr[left] key){left;}arr[hole] arr[left];hole left;}arr[hole] key;return hole;
}void HoleSort(int* arr, int begin, int end)
{if (begin end){return;}int mid HoleSortPart(arr, begin, end);HoleSort(arr, mid 1, end);HoleSort(arr, begin, mid - 1);
}int QuickSortPart(int* arr, int begin, int end)
{int tmp GetMidIndex(arr, begin, end);swap(arr[tmp], arr[begin]);int prev begin, cur begin 1;int key arr[begin];while (cur end){if (arr[cur] key){prev;swap(arr[cur], arr[prev]);}cur;}swap(arr[begin], arr[prev]);return prev;
}void QuickSort(int* arr, int begin, int end)
{if (begin end){return;}int mid QuickSortPart(arr, begin, end);QuickSort(arr, begin, mid - 1);QuickSort(arr, mid1, end);
}https://leetcode.cn/problems/sort-an-array/ 上面那个链接可以用来测排序的算法正不正确如果你用我上面的代码去这个链接测的话你会发现有一个数量庞大的都是同一个数字的数组跑不过去时间复杂度太高了三数取中可以解决数组有序的问题但无法解决数组都是同一个数字的问题,所以我、我们还要对此进行改进我们上面主要是用两路划分因为我们只分了大于大于key和小于大于key两个部分我们现在要采取的方法称作三路划分也就是分为三部分左边那一部分是小于key,中间那部分是等于key的部分右边那部分是大于key的部分通过这种方法我们就可以很快的通过全是同一个数的样例但不建议用递归因为要传回来两个数可能会用到数组传参
void ThreeRoadQuickSort(int* arr, int begin, int end)
{if (begin end)return;int cur begin 1, left begin, right end;int tmp GetMidIndex(arr, begin, end);int key arr[tmp];while (cur right){if (arr[cur] key){swap(arr[left], arr[cur]);left;}else if (arr[cur] key){swap(arr[right], arr[cur]);right--;}else{cur;}}ThreeRoadQuickSort(arr, begin, left - 1);ThreeRoadQuickSort(arr, right 1, end);
}快排的非递归形式
快排还存在一个风险如果数字太多递归层次太深会有栈溢出的风险所以我们还是要研究一下快排的非递归的形式
void QuickSortNoR(int* arr, int begin, int end)//1 9
{stack st;InitStack(st);PushStack(st, end);PushStack(st, begin);while (!isemptyStack(st)){int first TopStack(st);PopStack(st);int last TopStack(st);PopStack(st);int mid HoareSortPart(arr, first, last);//三种快排part选哪一个都可以if (mid - 1 first){PushStack(st, mid - 1);PushStack(st, first);}if (last mid 1){PushStack(st, last);PushStack(st, mid1);}}
}但大家拿上面那个代码去测试的时候会发现时间复杂度还是超时了在这里把三数取中改成随机数即可
归并排序
归并排序
归并排序是将已经有序的子序列合并也就是先让子序列间有序再让子序列段间有序最后将两个有序表合成一个有序表称为二路归并。
归并排序递归版本
//归并排序 递归版本
void MergeSortPart(int* arr, int begin, int end,int* tmp)
{if (begin end)//不会存在不存在的区间所以不需要大于等于return;int mid (begin end) / 2;MergeSortPart(arr, begin, mid, tmp);MergeSortPart(arr, mid 1, end, tmp);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[i] arr[begin1];}else{tmp[i] arr[begin2];}}while (begin1 end1){tmp[i] arr[begin1];}while (begin2 end2){tmp[i] arr[begin2];}memcpy(arr begin, tmp begin, sizeof(int) * (end - begin 1));
}
void MergeSort(int* arr, int begin, int end)
{if (begin end)return;int i 0;int* tmp (int*)malloc(sizeof(int) * (end - begin 1));MergeSortPart(arr, begin, end, tmp);free(tmp);
}//时间复杂度为O(N*logN),空间复杂度为O(N)归并有一个缺点比如说我们要分1w个数分为1250只需要三次而剩下最后十个要递归要分四次所以我们可以在这个地方用一个优化称为小区间优化
void MergeSortPart2(int* arr, int begin, int end, int* tmp)
{if (begin end)//不会存在不存在的区间所以不需要大于等于return;if (end - begin 1 10){InsertSort(arr begin, end - begin 1);//最好选插入排序而不是冒泡return;}int mid (begin end) / 2;MergeSortPart(arr, begin, mid, tmp);MergeSortPart(arr, mid 1, end, tmp);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[i] arr[begin1];}else{tmp[i] arr[begin2];}}while (begin1 end1){tmp[i] arr[begin1];}while (begin2 end2){tmp[i] arr[begin2];}memcpy(arr begin, tmp begin, sizeof(int) * (end - begin 1));
}上图就是对归并的part的优化假设把归并排序的调用看做一个二叉树设这棵树的递归调用次数为2^h-1,而最后一层的递归调用次数就有2 ^(h-1)次基本上占了调用次数的一半而倒二层调用2 ^h-2次递归调用占总的递归调用次数的25%第三层为12.5%这样的三层最后一层调用下来所要占的递归调用次数达到了87.5%如果继续扩大数据量去调用其他的排序已经意义不大了
归并排序的非递归版本
归并排序的非递归版本比递归版本复杂很多是要先选一个一个数再两组进行对比再选两个两个数…四个四个数…以此类推然后再继续两组进行对比但边界情况的考虑会相对比较麻烦只有2的次幂才能不考虑边界如果数组数不是2的次幂则要进行修正分别有三种情况我们称第一组的开头和结尾为begin1和end1第二组为begin2和end2第一种情况是end1begin2和end2都越界第二种情况是begin2和end2越界第三种情况是end2越界对于第一种和第二种情况因为第二组都是完全越界我们只需要把第一组数据保留拷贝回去即可所以下面对第二组数据的begin2和end2进行处理使其无法进入第一个while循环和第三个while循环第三种情况我们只需要对end2进行修正因为归并排序是不需要对比的两组数据个数一样的所以我们可以直接让end2n-1即可正常归并
void MergeSortNoR(int* arr, int begin, int end)
{int gap 1;int n end - begin 1;int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}while (gap n){for (int i 0; i n; i2*gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;int j i;int sz end2 - begin1 1;if (end1 n||begin2n)//对边界进行修正{end1 n - 1;sz end1 - begin1 1;begin2 end2 1;}else if (end2 n){end2 n - 1;sz end2 - begin1 1;}while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[j] arr[begin2];}else{tmp[j] arr[begin1];}}while (begin1 end1){tmp[j] arr[begin1];}while (begin2 end2){tmp[j] arr[begin2];}memcpy(arr i, tmp i, sizeof(int) * sz);//归并一组拷贝一组这种方法可以用整体拷贝}gap * 2;}free(tmp);
}非比较排序 计数排序
//计数排序
void CountSort(int* arr, int n)
{int mintmp arr[0], maxtmp arr[0];for (int i 0; i n; i){if (arr[i] mintmp){mintmp arr[i];}if (arr[i] maxtmp){maxtmp arr[i];}}int range maxtmp - mintmp 1;int* tmp (int*)malloc(sizeof(int) * range);if (tmp NULL){perror(malloc fail);return;}for (int i 0; i range; i){tmp[i] 0;}for (int i 0; i n; i){tmp[arr[i]-mintmp];}int j 0;for (int i 0; i range; i){while (tmp[i]--){arr[j] i mintmp;}}
}这个排序的时间复杂度为O(Nrange),当range很小的时候它会很快但range很大的时候就不一样了这个排序有两个缺陷一是这个排序依赖数据范围二是只能用于整型
稳定性
最后讨论一下排序的稳定性若有两个数tmp1和tmp2且这两个数相等若排序之前tmp1就在tmp2前排序后相对位置也不改变这个排序的稳定性就好。 直接插入排序冒泡排序归并排序是稳定的排序。 希尔排序选择排序选数稳定交换时不稳定堆排序快速排序是不稳定的排序。
内排序结语
上面所说的全部属于内排序内排序和外排序最大的区别就是数据量内排序的数据量较小可以放在内存中直接排序而外排序的数据量大内存装不下所以要放在磁盘里排序所以我们接下来将介绍用归并排序对文件里的数据进行排序
外排序
归并排序既可以用作内排序假设我们将要把40个G的数据进行排序但内存只有1G我们就可以把这个40G的大文件分为40个1G的小文件然后两两排序合成一个个2G的文件以此类推我们在对小文件排序的时候要使用快排不能用归并因为一个内存只有1G的空间的情况下我们用归并会耗费更多的内存下面是文件排序的代码里面的n是可以修改的决定你一个小文件可以放多少个数字
void _FileMergeSort(char* f1, char* f2, char* mf)
{int a1, a2;FILE* File1 fopen(f1, r);if (File1 NULL){printf(open fail);exit(-1);}FILE* File2 fopen(f2, r);if (File2 NULL){printf(open fail);exit(-1);}FILE* mFile fopen(mf, w);if (mFile NULL){printf(open fail);exit(-1);}int flag1 fscanf(File1, %d , a1);int flag2 fscanf(File2, %d , a2);while (flag1 ! EOF flag2 ! EOF){if (a1 a2){fprintf(mFile, %d , a2);flag2 fscanf(File2, %d , a2);}else{fprintf(mFile, %d , a1);flag1 fscanf(File1, %d , a1);}}while (flag1 ! EOF){fprintf(mFile, %d , a1);flag1 fscanf(File1, %d , a1);}while (flag2 ! EOF){fprintf(mFile, %d , a2);flag2 fscanf(File2, %d , a2);}fclose(File1);fclose(File2);fclose(mFile);
}void FileMergeSort()
{FILE* fp;int a 0;int n 10;int arr[10];char filename[20];fp fopen(Sort.txt, r);int i 0;int filenames 0;while (fscanf(fp, %d , a) ! EOF){if (i n - 1)//8{arr[i] a;}else{arr[i] a;QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);sprintf(filename, Sort_%d.txt, filenames);FILE* tmp fopen(filename, w);if (tmp NULL){printf(error);exit(-1);}for (int j 0; j n; j){fprintf(tmp, %d , arr[j]);}i 0;fclose(tmp);}}//文件归并char mfile[100], file1[100], file2[100];sprintf(file1, Sort_0.txt);sprintf(mfile, Sort_sum.txt);for (int i 1; i n; i){sprintf(file2, Sort_%d.txt, i);_FileMergeSort(file1, file2, mfile);sprintf(file1, mfile);sprintf(mfile, %d.txt, i);}fclose(fp);
}
