做一个网站成本大概多少钱,w网站怎么做,找聊城做网站,微信怎么关闭小程序功能目录 前言 快速排序
相遇位置一定比key小的原理#xff08;大#xff09;#xff1a;
避免效率降低方法#xff08;快排优化#xff09;
三数取中#xff08;选key优化#xff09;
小区间优化
hoare版本快排
挖坑法快排
前后指针快排
非递归快排
归并排序
非递…目录 前言 快速排序
相遇位置一定比key小的原理大
避免效率降低方法快排优化
三数取中选key优化
小区间优化
hoare版本快排
挖坑法快排
前后指针快排
非递归快排
归并排序
非递归归并
总结编辑 前言
本篇讲解上一篇没有讲解的快速排序和归并排序 上篇排序常见排序算法-CSDN博客 本期专栏算法_海盗猫鸥的博客-CSDN博客 个人主页海盗猫鸥-CSDN博客 这两种排序思想较为复杂和堆排序、希尔排序都为效率较高的排序算法且快排和归并都分为递归和非递归两种实现方法。 快速排序
hoare方法原理解析升序
图中循环开始时L指向比较区间的最左R指向比较区间的最右位置 1. 假设确定最左的数为key值 2. 则R--寻找小于key的值L寻找大于key的值找到后交换R和L所指向位置的值 3. 如此循环下去直到R等于L循环结束将key值和相遇位置一定小于key的值进行交换并将key指向相遇位置 4.完成一次循环之后小于key的值都在此时key位置的左边大于key的值都在key位置右边 5.将此时的key位置作为分界点分为左右俩区间进行递归 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void QuickSort(int* arr, int left, int right)
{if (left right){return;}//以key为基准int keyi left;int begin left;int end right;while (begin end){//先找小后找大能保证begin和end相遇位置的数据一定小于keyi位置的数据//右边找小while (begin end arr[end] arr[keyi]){end--;}//左边找大while (begin end arr[begin] arr[keyi]){begin;}Swap(arr[begin], arr[end]);}//Swap(arr[keyi], arr[begin]);keyi begin;QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi 1, right);
}
相遇位置一定比key小的原理大
升序
left做key保证R先走就能保证相遇位置一定小于key相对的right做key时就要让L先走保证相遇位置比key大
降序排列时则相反
因为在上一次交换中L与R交换值L所指向的位置就一定已经是小于key的值了此时到下一个循环R先再往前走L还没有动所以当R遇到L时就一定是上一轮交换过来的小于key的值所以相遇位置一定小于key
反之如果先让L先走那么相遇位置就一定是上一轮交换完成后大于key的值所在的位置也就是上一轮R所在位置一定大于key值
当前版本的快排当数据本身就有序时快排的时间复杂度将会退化为N^2
并且有栈溢出的风险递归深度太深将导致栈溢出因为函数栈帧空间较小
当每次的key越接近中间位置时快排的时间复杂度约为O(N*logN):
避免效率降低方法快排优化
三数取中选key优化 想办法使key的值更接近中间 使用随机值赋值key可以避免效率降低到O(N^2)但随机性任然较大 三数取中 将排序区间的leftright和位于最中间的数比较取大小居中的那个数作为key值但为保证后续排序逻辑不变要将key值和最左left位置上的值进行交换 小区间优化 假设每次key都比较接近中间位置那么每次区间分割都可以大致看为二分则其递归的形式就形似二叉树效率最高但当数据个数较少时使用递归来排序是不太合适的 所以当区间数据个数较少时我们可以直接使用插入排序 hoare版本快排
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}//三数取中
int GetMidi(int* arr, int left, int right)
{//返回三个数中值最小的下标int midi (left right) / 2;if (arr[left] arr[midi]){if (arr[midi] arr[right])return midi;else if (arr[left] arr[right])return right;elsereturn left;}else//arr[left] arr[midi]{if (arr[midi] arr[right])return midi;else if (arr[left] arr[right])return right;elsereturn left;}}//hoare
O(N*logN)
void QuickSort(int* arr, int left, int right)
{if (left right){return;}//小区间优化不再采取递归的方式if ((right - left 1) 10){//传递区间的起始地址arr leftInsertSort(arr left, right - left 1);}else{//以key为基准//固定以left为key时当数组倒序时将导致时间复杂度退化为O(N^2);//int keyi left;//三数取中int midi GetMidi(arr, left, right);Swap(arr[left], arr[midi]);//将要作为key的值交换到最左边int keyi left;int begin left;int end right;while (begin end){//先找小后找大能保证begin和end相遇位置的数据一定小于keyi位置的数据//右边找小while (begin end arr[end] arr[keyi]){end--;}//左边找大while (begin end arr[begin] arr[keyi]){begin;}Swap(arr[begin], arr[end]);}//Swap(arr[keyi], arr[begin]);keyi begin;QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi 1, right);}
}
挖坑法快排
原理解析升序 1. 将最左位置视为初始坑位并将其值赋值给key存储起来L指向最左边此时L所指就是坑位R指向最右位置 2. R开始从右往左找小于key的值找到后将这个位置的值赋值给坑位并将这个位置视为新的坑位 3. 接着L从左往右找大于key的值找到后将这个位置的值赋值给坑位并将这个位置视为新的坑位。 4. 直到L和R相遇同时指向坑位将key值赋值给坑位。此时小于key的值就都在坑位前大于key‘的值都在坑位后 5. 以最后的坑位为分界左右区间递归 void QuickSort(int* arr, int left, int right)
{if (left right){return;}//将第一个数据视为坑int keni left;int key arr[keni];int begin left;int end right;while (begin end){//找到小于key的值填到坑中while (begin end arr[end] key){end--;}arr[keni] arr[end];keni end;while (begin end arr[begin] key){begin;}arr[keni] arr[begin];keni begin;}//相遇后将key值赋给坑的位置arr[keni] key;QuickSort(arr, left, keni - 1);QuickSort(arr, keni 1, right);
}前后指针快排
原理解析升序 1. 以最左为key值prev从排序区间的第一个位置开始curprev1开始 2. 当cur所指位置值小于key值时prev后将prev位置和cur位置的数据交换位置然后cur继续寻找下一个符合条件的数据 3. cur所指位置值大于key时直接cur即可不论cur所指是否满足交换条件cur始终都要 实际就是让大于key的值都放在prev和cur所指的区间之间并将这些值通过交换一步步送到数组的右边 4. 直到cur超出数组范围此时prev所指的位置左边就全是小于key的值右边就全是大于key的值 5. 交换prev位置和key位置的数据将key重新指向prev本次循环结束 6. 然后以新key位置为分界左右区间递归 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void QuickSort(int* arr, int left, int right)
{if (left right)return;//小区间优化if ((right - left 1) 10){//传递区间的起始地址arr leftInsertSort(arr left, right - left 1);}else{//三数取中此优化后逻辑会改变原理分析处为没有三数取中优化的解析int midi GetMidi(arr, left, right);Swap(arr[left], arr[midi]);//将要作为key的值交换到最左边int keyi left;int prev left, cur left 1;//prev和cur中间都为大于key的值while (cur right){if (arr[cur] arr[keyi] prev)Swap(arr[prev], arr[cur]);cur;}Swap(arr[keyi], arr[prev]);keyi prev;QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi 1, right);}
}非递归快排
使用栈来模拟递归的区间分解模式 1. 循环每走一次相当于之前的一次递归 2. 取栈顶区间单趟排序然后右左子区间入栈栈后进先出 代码
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//非递归快排
//使用栈模拟递归分区逻辑DFS深度优先
//使用队列模拟BFS广度优先
void QuickSortNonR(int* arr, int left, int right)
{//创建栈存入右左区间ST st;STInit(st);STPush(st,right);STPush(st, left);//一次循环就是相当于一次递归while (!STEmpty(st)){//取区间//栈先进后出,先出的为区间左边界int begin STTop(st);STPop(st);int end STTop(st);STPop(st);//排序(前后指针法)int keyi begin;int prev begin, cur begin 1;//prev和cur中间都为大于key的值while (cur end){if (arr[cur] arr[keyi] prev)Swap(arr[prev], arr[cur]);cur;}Swap(arr[keyi], arr[prev]);keyi prev;//存储右左区间if (keyi 1 end)//keyi 1 end说明还有两个数以上{STPush(st, end);STPush(st, keyi 1);}if (begin keyi - 1){STPush(st, keyi - 1);STPush(st, begin);}}
}
快速排序的特性总结 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序上述几种在实际使用中效率差别不大时间复杂度O(N*logN)空间复杂度O(logN)递归损耗稳定性不稳定 归并排序
原理解析升序 1. 将数组从中间分为左右两个区间 2. 如果左右区间不有序就继续分解左右数组直到左右区间中都只存在一个数时左右区间就一定有序一个单独的数据一定有序 3. 那么如果左右区间有序就分别从左右区间的第一个数开始比较将左右区间中的数按照升序插入到临时数组中完成后临时数组中就是一个顺序结构
上文动图只显示了合并的思想分解的思想过程是由递归过程来实现的
代码
void _MergeSort(int* arr, int* tmp, int begin, int end)
{if (begin end)return;//将区间从中间分为左右区间int midi (begin end) / 2;int begin1 begin;int end1 midi;int begin2 midi 1;int end2 end;//[left,midi][midi1,right]_MergeSort(arr, tmp, begin1, end1);_MergeSort(arr, tmp, begin2, end2);int i begin;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2])//小的先插入tmp{tmp[i] arr[begin1];}else{tmp[i] arr[begin2];}}//将没有完成插入的一边全部插入到tmpwhile (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 n)
{//假设左右区间都为有序//取左右区间小的那个数插入新数组int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail!);return;}//排序核心_MergeSort(arr, tmp, 0, n - 1);free(tmp);tmp NULL;
}
注意区间划分问题 在进行左右分区时不能使用[left,midi-1][midi,right]来分区 由于midi是整形相除的结果所以存在数据丢失的情况若一个以区间[2,3]为例midi2 则此时再按照midi分区右区间仍然为[2,3]程序将陷入无限递归从而崩溃而如果按照[left,midi][midi1,right]来区分区间则右区间为[3,3]满足递归条件就返回了不会导致程序出错 非递归归并
思路 使用循环直接模拟归并合并的过程
理想数组思路图解数据个数等于gap 越界问题解析 参考代码
//归并排序非递归
void MergeSortNonR(int* arr, int n)
{//循环模拟int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail!);return;}//两组beginend分别表示归并的左右两组int begin1, end1;int begin2, end2;int gap 1;while (gap n){for (int i 0; i n; i gap * 2){//i为每次比较的左右两组最左边的起始位置begin1 i;end1 i gap - 1;begin2 i gap;end2 i 2 * gap - 1;int j i;//printf([%d,%d][%d,%d], begin1, end1, begin2, end2);if (begin2 n)break;if (end2 n)end2 n - 1;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2])//保证稳定性tmp[j] arr[begin1];elsetmp[j] arr[begin2];}//printf( );while (begin1 end1)tmp[j] arr[begin1];while (begin2 end2)tmp[j] arr[begin2];//每归并一组左右区间就拷贝一次memcpy(arr i, tmp i, sizeof(int) * (end2 - i 1));}//memcpy(arr, tmp, sizeof(int) * (n - 1));gap * 2;//printf(\n);}free(tmp);tmp NULL;
}归并排序的特性总结 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)额外开辟空间稳定性稳定 总结
排序的介绍到这里就完结啦~
欢迎大家继续关注我的博客~
