网站加载慢,wordpress4.8模板路径,关键词密度查询站长工具,青岛网站推广方案目录
快速排序#xff08;hoare版本#xff09;
初级实现
问题改进
中级实现
时空复杂度
高级实现
三数取中 快速排序#xff08;hoare版本#xff09; 历史背景#xff1a;快速排序是Hoare于1962年提出的一种基于二叉树思想的交换排序方法 基本思想#xff1a…目录
快速排序hoare版本
初级实现
问题改进
中级实现
时空复杂度
高级实现
三数取中 快速排序hoare版本 历史背景快速排序是Hoare于1962年提出的一种基于二叉树思想的交换排序方法 基本思想通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列 初级实现 实现步骤 1、确定排序开始时key 每轮排序作为基准元素的元素下标 、left 负责寻找大于基准元素的元素下标 、right 负责寻找小于基准元素的元素下标 三者的初始值 int left begin; //数组首元素下标
int right end; //数组尾元素下标
int keyi begin; //即可以是首元素下标、也可以是尾元素下标一般来说是首元素下标 2、right和left开始自己的寻找任务当a[right] a[keyi]right就--继续向左走当a[left] a[keyi]left就继续向右走当二者都在找的过程中在某一位置停下时两个while循环均结束交换此时的a[left]和a[right] void QuickSort(int* a, int begin, int end)
{int left begin, right end;int keyi begin;// 右边找小while (a[right] a[keyi]){--right;}// 左边找大while (a[left] a[keyi]){left;}Swap(a[left], a[right]);} 3、当left与right相遇即left right时此时元素的值一定小于基准元素的值所以交换当前元素与基准元素的位置因为我们要做的就是将小于基准元素的数放在左边大于的放在右边 void QuickSort(int* a, int begin, int end)
{int left begin, right end;int keyi begin;while (left right){// 右边找小while (a[right] a[keyi]){--right;}// 左边找大while (a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);
} 关于“为什么相遇位置一定会比基准元素小”的解释 因为我们规定右边先走当然你也可以让左基准元素是数组尾元素然后左边先走这里就不再分析了这样就会有两种相遇的情况 ①right遇到leftright没找到比基准元素小的一直走找到时停下然后left向右走当二者相遇即right left时停下原因我们后面会将所处位置的元素的值小于基准元素 ②left遇到rightright先走找到小于基准元素的位置停下left开始找比基准元素大的没有找到一直走遇到right停下相遇位置是right前面说过此时的位置应该是小于基准元素的位置“right先走找到小于基准元素的位置停下” 至此我们快速排序的初级实现已经完成了接下来就是处理我们遗留的一些问题了
问题改进 1、产生原因有时我们写的代码只适用于部分数据但是换成其它数据时就会出错为了保证我们代码的通用性我们要进行多次的用例测试比如我们将数组换为{6,1,2,5,4,6,9,7,10,8} 可以发现之前的代码并不能让right和left相遇又因为我们规定right先走所以我们为了能让二者相遇需要保证left永远不会超过right故在a[right] a[keyi]之前加上left right即left right a[right] a[keyi]left也是一样的道理 void QuickSort(int* a, int begin, int end)
{int left begin, right end;int keyi begin;while (left right){// 右边找小while (left right a[right] a[keyi]){--right;}// 左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);
} 2、产生原因当我们将基准元素换到数组的中的某个位置时它左侧的元素经过一系列检查与交换的操作后已经全部是小于基准元素的元素右边的元素也已经全部是大于基准元素的元素现在我们要做的就是将左右两边的元素均变为有序当左右两边均有序时该数组就完全有序原因自己想去这就需要用到递归思想了在前面我们说过hoare版本的快排是基于二叉树思想的当我们尝试对上面的数组开始递归操作时如果还是原来的代码就会出现下图所示的问题 可以发现 原本我们是想通过右递归将右侧大于基准元素的几个元素变为有序但可以看到的是只有当a[right] 4时才会停下此时就已经在左递归的范围内了因此为了保证不会越界我们还需要为a[right] a[keyi]加上一个即a[right] a[keyi]左递归也是一样的道理 void QuickSort(int* a, int begin, int end)
{int left begin, right end;int keyi begin;while (left right){// 右边找小while (left right a[right] a[keyi]){--right;}// 左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);
} 中级实现
至此我们开始进行递归操作关于递归的过程如下图所示 关于递归的代码也不再过多解释自行理解即可
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int left begin, right end;int keyi begin;while (left right){// 右边找小while (left right a[right] a[keyi]){--right;}// 左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
} 以上就是一个“较为”完整的快速排序的代码
时空复杂度 最坏时间复杂度ON^2当数组已经降序有序或升序有序时此时基准元素一直位于首元素或尾元素n个元素要进行n次快速排序才能将当前的顺序改变n*n 最好时间复杂度ON*logN每次划分都能将数组均匀地分成两个接近子数组N个元素要进行logN次的排序N*logN 空间复杂度OlogN或ON在递归过程中需要使用栈来保存函数调用信息所以快速排序的空间复杂度取决于递归调用的层数。在最坏情况下递归调用栈可能达到O(n)的空间复杂度最好的空间复杂度为O(logn) 高级实现 当面对有序队列时快速排序的效率确实会降低。这是因为快速排序的分区操作通常选择一个基准元素并将小于等于基准的元素放在左侧大于基准的元素放在右侧。如果输入数据已经有序那么每次分区后只能将一个元素移到正确位置上而剩余部分仍然需要进行递归调用。为了应对这种情况可以采取以下方法来提高快速排序在有序队列上的效率 随机化选择基准通过随机选择基准值可以降低出现最坏情况即已经有序的概率。这样可以增加快速排序处理无序数据时的性能。 三数取中法使用三数取中法来选择合适的基准值。从待排序数组中选取头、尾和中间位置上的三个数并将它们按照大小顺序排列。然后选取其中位数作为划分子数组即作为枢纽以避免最坏情况发生。 插入排序优化当待排序子数组长度较小时比如小于某个阈值可以切换到插入排序算法进行处理。插入算法对局部有序数据表现良好在长度较短的子数组上可以提高排序效率。 优化递归调用通过限制递归深度或者使用尾递归优化等方法减少对有序数据的不必要处理。 这些方法可以在特定情况下提高快速排序算法在有序队列上的性能但需要根据具体场景选择合适的策略。 三数取中
注意事项获取的是下标为begin、midi、end的三个元素中的中位数非最多非最小
完整代码如下
int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;// begin midi end 三个数选中位数if (a[begin] a[midi]){if (a[midi] a[end])return midi; //返回a[midi] a[midi] a[end]else if (a[begin] a[end])return begin; //返回a[end] a[begin] a[midi]elsereturn end; //返回a[begin] a[end] a[midi]}else // a[begin] a[midi]{if (a[midi] a[end])return midi; //返回a[end] a[mid] a[begin]else if (a[begin] a[end])return begin; //返回a[midi] a[begin] a[end]else return end; //返回a[midi] a[end] a[begin]}
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin, right end;int keyi begin;while (left right){// 右边找小while (left right a[right] a[keyi]){--right;}// 左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
}
~over~
