个人作品展示 网站,app模板大全,做学分网站,怎么做百度快照让网站排前面目录 #x1f4a1;基本思想
#x1f4a1;基本框架
#x1f4a1;分割方法
⭐Hoare版本
⭐挖坑法
⭐前后指针法
#x1f4a1;优化方法
⭐三数取中法
⭐小区间内使用插入排序
#x1f4a1;非递归实现快速排序
#x1f4a1;性能分析 #x1f4a1;基本思想 任取待排…目录 基本思想
基本框架
分割方法
⭐Hoare版本
⭐挖坑法
⭐前后指针法
优化方法
⭐三数取中法
⭐小区间内使用插入排序
非递归实现快速排序
性能分析 基本思想 任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 基本框架
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int* array, int left, int right)
{if(right - left 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div1, right)QuickSort(array, div1, right);
}
这是快速排序递归实现的主框架可以发现与二叉树的递归十分相似在递归时可以想想二叉树的递归规则。
分割方法
⭐Hoare版本
这是Hoare于1962年提出的一种二叉树结构的交换排序方法 这个方法的思想就是R找比key小的数L找比key大的数然后将R和L对应的数交换当R和L相遇时将R和L对应的数与key交换最终使得比key大的数都在key的右边比key小的数都在key的左边。 这里其实我们保存的时基准值的下标记为keyi这样做是为了方便交换不然交换时只是与key这个临时变量发生了交换而没有影响到原来的数组里的数。 这里其实还有几个疑点 当a[left],a[right]与a[keyi]相等时怎么办这里的处理方法其实就是不管它直接继续原来的过程就可以了最终两边排序时都会将这个数放到合理的位置。为什么当R与L相遇时它们所对应的数一定比a[keyi]小要得到这个结论必须要R先开始走当R和L相遇时有两种情况一是L动的时候遇见R此时R由于先走且一直在找比基准值小的数所以当R停下时R对应的数一定是小于等于基准值L找比基准值大的数一直没有找到遇见R就停下来二是R动的时候遇见LR没有找到比key小的所以一直走又因为L一直在找比基准值大的数所以当L停下时L对应的数一定大于基准值因此,只要R先走R和L相遇时对应的数一定比a[keyi]小。 ⭐挖坑法 所谓挖坑法就是第一次将基准值的位置设为坑(hole),然后R找比key小的数填入到坑中并使R对应的位置成为新的坑然后L找比key大的数填入到坑中并使L对应的位置成为新的坑再重复进行这个过程当R和L相遇时此时它们所对应的位置一定是一个坑然后再将key填入到坑中此时key左边的数一定比它小key右边的数一定比他大。 这个方法相较于hoare的方法更加好理解但是性能上并没有太大的变化。
//挖坑法
int PartSort(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);swap(a[begin], a[midi]);int key a[begin];int hole begin;while (begin end){//右边找小填到左边的坑while (begin end a[end] key){end--;}a[hole] a[end];hole end;//左边找大填到右边的坑while (begin end a[begin] key){begin;}a[hole] a[begin];hole begin;}a[hole] key;return hole;
}
⭐前后指针法 这个方法就是 cur遇到比key大的数curcur遇到比key小的数prev交换cur与prev位置的值cur。当cur超出数组边界时将prev位置的值与key位置的值交换。 int PartSort(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);swap(a[begin], a[midi]);int keyi begin;int prev begin;int cur begin 1;while (cur end){if (a[cur] a[keyi] prev ! cur)//自身交换减少了{swap(a[prev], a[cur]);}cur;}swap(a[keyi], a[prev]);keyi prev;return prev;
}
优化方法
⭐三数取中法
所谓三数取中法其实取的是三个数中的中位数将这个数作为基准值能够避免某些极端情况的出现比如数组已经接近有序。
⚠注这是针对基数选取进行的优化另外还有随机数法选数在这里就不过多介绍了。 int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;//取中位数if (a[begin] a[midi]){if (a[midi] a[end]){return midi;}else {if (a[begin] a[end])return end;elsereturn begin;}}else //midi begin{if (a[begin] a[end]){if (a[midi] end){return midi;}elsereturn end;}elsereturn begin;}
}
⭐小区间内使用插入排序
在递归到较小区间时如果仍然使用快速排序会造成时间上的浪费假如这个区间内有7个数那就要递归7次才能得到这个7个数的有序序列。 if(end-begin1 10)
{//某个区间内的小规模排序直接插入排序//进行插入排序InsertSort(arr,end-begin1);return;
}非递归实现快速排序 非递归实现方法其实与递归的方法类似但是需要借助栈这个数据结构避免其他方法造成栈溢出。 每次将要排序的区间的起始位置入栈然后排序时再取栈顶的前两个元素作为一个排序区间进行快速排序然后依次对key的左区间、右区间进行这样的操作最终得到有序序列。 void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(s);STPush(s, end);STPush(s, begin);while (!STEmpty(s)){int left STTop(s);STPop(s);int right STTop(s);STPop(s);int keyi PartSort(a, left, right);// [left, keyi-1] keyi [keyi1, right]if (left keyi - 1){STPush(s, keyi - 1);STPush(s, left);}if (keyi 1 right){STPush(s, right);STPush(s, keyi 1);}}STDestroy(s);
}
性能分析
时间复杂度最差O(N^2),最好O(NlogN)平均O(NlogN)空间复杂度O(logN),因为递归时创建的栈帧申请的空间没有销毁递归的深度为logN稳定性不稳定特点:数据越乱排序越快
