网站建设 九艾,免费科技,折叠分类目录模板wordpress,网站空间 哪个公司好快速排序法 递归法
霍尔版本(左右指针法)
1.思路
1、选出一个key#xff0c;一般是最左边或是最右边的。 2、定义一个begin和一个end#xff0c;begin从左向右走#xff0c;end从右向左走。#xff08;需要注意的是#xff1a;若选择最左边的数据作为key#xff0c;则… 快速排序法 递归法
霍尔版本(左右指针法)
1.思路
1、选出一个key一般是最左边或是最右边的。 2、定义一个begin和一个endbegin从左向右走end从右向左走。需要注意的是若选择最左边的数据作为key则需要end先走若选择最右边的数据作为key则需要bengin先走。 3、在走的过程中若end遇到小于key的数则停下begin开始走直到begin遇到一个大于key的数时将begin和right的内容交换end再次开始走如此进行下去直到begin和end最终相遇此时将相遇点的内容与key交换即可。选取最左边的值作为key 4.此时key的左边都是小于key的数key的右边都是大于key的数 5.将key的左序列和右序列再次进行这种单趟排序如此反复操作下去直到左右序列只有一个数据或是左右序列不存在时便停止操作此时此部分已有序
tip1
常选左为key那右边先走。
优化一选key的常见三种方法 1.三数取中(比较推荐) 三数取中 left mid right大小居中的值也就是不是最大也不是最小的 2.随机取一个 3.取中间位置
//关于选kevi——三数取中作为kevi比较好
int Getmid(int* arr, int left, int right)
{//方法1三数取中//left mid right//找到三者——中间值的下标返回int mid (left right) / 2;if (arr[left] arr[mid]){if (arr[mid] arr[right]){return mid;}else if(arr[right]arr[mid]){return right;}else{return left;}}else //此时已经arr[left]arr[mid]{if (arr[right] arr[mid]){return mid;}else if (arr[left] arr[right]){return left;}else{return right;}}
}
//方法2随机取一个还行
int GetRand(int* arr, int left, int right)
{srand((size_t)time(NULL));return rand() % (right-left1)left;
}
//方法3取中间位置
int GetMid(int* arr, int left, int right)
{return (left right) / 2;
}优化二小区间优化
优化小数组的交换就是为了解决大才小用问题
原因对于很小和部分有序的数组快排不如插排好。当待排序序列的长度分割到一定大小后继续分割的效率比插入排序要差此时可以使用插排而不是快排
截止范围待排序序列长度N 10虽然在5~20之间任一截止范围都有可能产生类似的结果这种做法也避免了一些有害的退化情形。
if (right - left 1 10)
{InsertSort(a left, right - left 1); //使用插入排序return;
}2.图解
单趟动图
3.代码
代码如下
//hoare(霍尔)版本(左右指针法)
#includestdio.h
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;//记录一下因为后面要变化int beginleft;int endright;//选左边为keyint mid Getmid(arr, left, right); //三数取中Swap(arr[mid],arr[left]); //把找到的移到最左边int kevi left;while (left right){//右先走// 注意:leftright//right,找小while (left right arr[right] arr[kevi]){right--;}//left找大while (left right arr[left] arr[kevi]){left;}//交换(大和小的)Swap(arr[left], arr[right]);}//交换key和相遇点Swap(arr[kevi], arr[right]);kevi right; //更新kevi//递归// 右边大于kevi 左边小于kevi//此时[begin,kevi) kevi [kevi1,end]QuickSort(arr, begin,kevi-1);QuickSort(arr, kevi1,end);
}运行结果
挖坑法
1.思路
选key左边为key(坑)右边先走找小小于key,找到把值放key坑里,此时right变新坑左边后走找大大于key,找到把值放key坑里,此时left变新坑。一直相遇把一开始key的值放相遇点递归下去
2.图解 3.代码
//挖坑法
void QuickSort_keng(int* arr,int begin,int end)
{//递归结束if (begin end)return;//int left begin;int right end;int mid Getmid(arr, left, right); //三数取中Swap(arr[mid], arr[left]); //换过来int kevi arr[left]; //设置开始的坑位,保存key的值int keng left; //记录坑位的位置while (left right){//right 找小while (leftrightarr[right] kevi){right--;}Swap(arr[right], arr[keng]); //交换right位置变成新的坑位keng right;//left找大while (left right arr[left] kevi){left;}Swap(arr[left], arr[keng]); //交换left位置变成新的坑位keng left; }//最终把kevi放keng位置(相遇点)arr[keng] kevi;//递归QuickSort_keng(arr,begin,keng-1);QuickSort_keng(arr, keng1, end);}前后指针法
1.思路
1、选出一个key一般是最左边或是最右边的。2、起始时prev指针指向序列开头cur指针指向prev1前后指针。3、若cur指向的内容小于key则prev先向后移动一位然后交换prev和cur指针指向的内容然后cur指针4、若cur指向的内容大于key则cur指针直接。如此进行下去直到cur到达end位置此时将key和prev指针指向的内容交换即可。
经过一次单趟排序最终也能使得key左边的数据全部都小于keykey右边的数据全部都大于key。
然后也还是将key的左序列和右序列再次进行这种单趟排序如此反复操作下去直到左右序列只有一个数据或是左右序列不存在时便停止操作
2.图解 3.代码
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//前后指针版本
void QuickSort_prev(int* arr, int begin, int end)
{//递归结束if (begin end) return;记录区间范围int left begin;int right end;int kevi left; //记录key的下标//前后指针int prev left;int cur left 1;while (cur right){if (arr[cur] arr[kevi] prev ! cur){//把小的交换到前面Swap(arr[cur],arr[prev]);}cur;}//cur越界了交换kevi和prevSwap(arr[kevi], arr[prev]);kevi prev;//递归QuickSort_prev(arr, left, kevi - 1);QuickSort_prev(arr, kevi 1, right);}非递归法
1.思路 使用stack来存储待处理的区间先入栈的是右端点然后是左端点。 在while循环中只要栈不为空就继续处理。 每次从栈中弹出两个元素分别代表当前处理区间的左右端点。 执行一趟快速排序的划分操作使用kevi作为基准元素的索引prev用于记录小于基准元素的最后一个元素的位置。 在while循环中cur遍历当前区间如果发现比基准元素小的元素则将其与prev位置的元素交换。 划分完成后将基准元素与prev位置的元素交换确保基准元素位于中间位置。 检查新的区间是否需要继续排序如果需要则将新的区间端点压入栈中。 重复步骤2-7直到栈为空这意味着所有元素都已经被排序。
2.图解 3.代码
这里得单趟我套用了前面 前后指针的方法
//非递归
void QuickSort_None(int* arr, int begin, int end)
{stackint st; //栈//先入右后入左st.push(end);st.push(begin);//不为空while (!st.empty()){//出栈区间开始一趟int left st.top();st.pop();int right st.top();st.pop();//走单趟int kevi left;int prev left;int cur left1;while (cur right){//把小的换到前面if (arr[cur] arr[kevi] prev ! cur){Swap(arr[prev], arr[cur]);}cur;}//把kevi换到相遇点Swap(arr[kevi],arr[prev]);kevi prev;//入栈新区间-先右后左// [begin,kevi-1] kevi [kevi1,end]if (kevi 1 right){st.push(end); //先右后左st.push(kevi1);}if (leftkevi-1){st.push(kevi-1); // 先右后左st.push(left);}}
}算法性能 1.时间复杂度 2.空间复杂度 3.稳定性
不稳定 下面2 2 1 的例子,两个2相对位置发生变化
