广州住房和城乡建设局网站,网站建立方案,测速网站怎么做,网站搭建软件d1.快速排序#xff08;递归#xff09; 快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法#xff0c;其基本思想为#xff1a; 任取待排序元素序列中 的某元素作为基准值#xff0c;按照该排序码将待排序集合分割成两子序列#xff0c;左子序列中所有元素…1.快速排序递归 快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法其基本思想为 任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 。 void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort3(a, begin, end);//[begin,keyi-1]keyi[keyi1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
} 上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像同学们在写递归框架时可想想二叉 树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。 将区间按照基准值划分为左右两半部分的常见方式有 1. hoare 版本 2. 挖坑法 3. 前后指针版本 我来给大家讲解一下前后指针版本因为这个代码简洁但是不太好理解。 首先创建一个变量keyi保存left的值keyileft然后创建后指针prev开始也是在left位置prevleft前指针cur在prev前一个位置curprev1然后写一个while循环结束条件是curright,意味着cur越界了进入循环首先判断一下a[cur]和a[keyi]的大小如果a[cur]大则再判断prev是否等于cur如果等于则不用交换cur,如果两个条件都满足则交换a[prev]和a[cur]因为prev已经所以直接交换即可。循环结束之后再交换a[key]和a[prev]. cur的作用就是和prev拉开距离然后将大于a[keyi]的值放到右边的部分最后交换a[keyi]和a[prev]就完成了部分排序。 int PartSort(int* a, int left, int right)
{int keyi left;int prev left, cur prev 1;while (cur right){if (a[cur] a[keyi] (prev) ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);return prev;
} void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort3(a, begin, end);//[begin,keyi-1]keyi[keyi1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
} 2.快速排序优化 2.1三数取中 三数取中是取大小位于中间的值放到最左边这样可以防止快排中最坏的情况出现O(n*2)也就是要排序的这一组数据接近有序或者就是有序的情况那么使用了三数取中后这种最坏的情况就变成了最好的情况. //三数取中
int GetMidi(int* a, int left, int right)
{int midi (left right) / 2;if (a[left] a[midi]){if (a[midi] a[right]){return midi;}else if (a[right] a[left]){return left;}else{return right;}}else//a[left]a[midi]{if (a[left] a[right]){return left;}else if (a[midi] a[right]){return midi;}else{return right;}}
}
2.2小区间优化
当区间较小时可以使用插入排序来进行优化因为插入排序最坏的情况就是要插入的数都比前面的数小插入排序在小区间里面比较不错的一种排序算法在快速排序里面使用插入排序可以提高很多的效率。
void QuickSort2(int* a, int begin, int end)
{if (begin end)return;if ((end - begin 1) 10){int keyi PartSort3(a, begin, end);//[begin,keyi-1]keyi[keyi1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}else{InsertSort(abegin, end - begin 1);}
} 3.快速排序非递归
非递归的快速排序可以借助一个栈来实现先入右边的值再入左边的值然后每次取值都是先取栈顶也就是左边的值然后再进行部分排序直到返回的keyi-1left,就代表着左边排序完成右边返回的keyi1right,代表右边的部分排序完成。 void QuickSortNonR(int* a, int begin, int end)
{ST st;STInit(st);STPush(st, end);STPush(st, begin);while (!STEmpty(st)){int left STTop(st);STPop(st);int right STTop(st);STPop(st);int keyi PartSort3(a, left, right);if (keyi 1 right){STPush(st, right);STPush(st, keyi1);}if (keyi - 1 left){STPush(st, keyi-1);STPush(st, left);}}STDestroy(st);
} 今天的分享到这里就结束了感谢大家的阅读
