广州网站建设外包公司,html做网站例子,齐河网站建设电话,淘宝电商怎么做快速排序#xff08;Quick Sort#xff09;是一种基于分治思想的排序算法#xff0c;它通过将待排序数组分成两个子数组#xff0c;其中一个子数组的所有元素都比另一个子数组的元素小#xff0c;然后对这两个子数组递归地进行排序#xff0c;最终将整个数组排序。快速排…快速排序Quick Sort是一种基于分治思想的排序算法它通过将待排序数组分成两个子数组其中一个子数组的所有元素都比另一个子数组的元素小然后对这两个子数组递归地进行排序最终将整个数组排序。快速排序是一种原地排序算法其时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。
下面是使用 C 实现的 经典 快速排序算法
#include vector
#include iostream
using namespace std;int partitionSimple(vectorint array, int left, int right)
{if (left right){return -1;}// Use the value of index right as the pivotconst int pivot array[right];int lessBound left - 1;for (int i left; i right; i){// If the current element is not more than then pivot value,// then swap it with the less parts next value, and make the less part add 1if (array[i] pivot){swap(array[i], array[lessBound]);}}// At last, swap the pivot with the next element of less partswap(array[lessBound 1], array[right]);return lessBound 1;
}void quickSortSimple(vectorint array, int left, int right)
{if (left right){return;}const int pivotIndex partitionSimple(array, left, right);quickSortSimple(array, left, pivotIndex - 1);quickSortSimple(array, pivotIndex 1, right);
}void quickSort(vectorint array)
{quickSortSimple(array, 0, array.size() - 1);
}经典快速排序的实现过程可以分为两个步骤
分割子问题选取一个元素作为基准值pivot将待排序数组分成两个子数组一个子数组中的元素都小于等于基准值另一个子数组中的元素都大于等于基准值。合并解决方案对两个子数组分别进行快速排序递归最后将两个已排序的子数组合并成一个有序数组。
递归的部分其实比较好理解和实现那么现在可以将问题简化为给定一个数组和一个基准值如何将小于等于基准值的元素放在数组左边将大于基准值的元素放在数组右边
我的实现思路是利用一个小于等于pivot值的边界的索引这样一个概念变量对应代码中的lessBound它对应的元素及其左边部分都小于等于pivot值。在随后的数组遍历过程中如果遍历的元素满足这样的条件则将该元素与lessbound的后一位对调然后将lessbound的范围扩大一位。核心思路类似快慢指针即lessbound扮演的是慢指针i扮演的是快指针。
最后数组已经被分成了两个子数组其中一个子数组中的元素都小于等于基准值另一个子数组中的元素都大于基准值。然后分别对这两个子数组进行递归。
快速排序的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)其中 n n n 是待排序数组的长度。快速排序每次将待排序数组分成两个子数组其中一个子数组中的元素都小于等于基准值另一个子数组中的元素都大于等于基准值。
由于快速排序每次都将待排序数组分成两个子数组因此递归树的高度为 l o g n logn logn。每个节点所处理的子问题的规模最大为 n n n因此快速排序的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。
需要注意的是在最坏情况下快速排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)此时待排序数组已经有序或者接近有序且每次选取的基准值都是数组中的最小或最大元素。为了避免最坏情况的发生可以采用以下优化措施
随机选取基准值。三数取中法Median-of-three partitioning从子数组的左端、右端和中间位置分别选取一个元素选择它们的中间值作为基准值。
除此以外从算法本身出发经典快排是利用某个值作为基准值其算法实质在于一个周期内确定这个pivot的下标索引。从这点考虑可以考虑在这个周期内将所有与pivot相等的值的位置都敲定在递归时就不考虑这一批数。
C相应的实现 vectorint partitionOptimized(vectorint array, int left, int right)
{if (left right){return {-1, -1};}int pivot array[right];int lessBound left - 1, moreBound right;int i left;while (i moreBound){if (array[i] pivot){i;}else if (array[i] pivot){swap(array[lessBound], array[i]);}else{// array[i] pivotswap(array[--moreBound], array[i]);}}swap(array[right], array[moreBound]);return {lessBound, moreBound};
}void quickSortOptimized(vectorint array, int left, int right)
{if (left right){return;}vectorint bounds partitionOptimized(array, left, right);quickSortOptimized(array, left, bounds[0]);quickSortOptimized(array, bounds[1], right);
}void quickSort(vectorint array)
{quickSortOptimized(array, 0, array.size() - 1);
}新的算法的最显著的不同之处在于partition的返回值是一个数组保存了小于pivot的边界和大于pivot的边界他们也是新一轮递归的依据。在计算这两个边界时partition内需要将一个数组拆分为小于pivot的部分等于pivot的部分以及大于pivot的部分。此时主要是利用三个指针分别指向小于pivot的部分的边界大于pivot的部分的边界以及当前遍历元素。如果当前元素小于pivot则与之前的思路类似将当前元素与小于边界的下一位调换小于的边界扩大一位继续下一个元素遍历如果当前元素等于pivot继续下一个元素遍历其他不变如果当前元素大于pivot则需要将当前元素与大于边界的下一位进行调换大于的边界减小一位注意此时仍然需要调查被调换元素的大小即不继续一个元素的遍历。
当然虽说是优化但是这个思路也仅仅是在数组中有重复元素时会比经典快排稍微快一些本质上算法复杂度并没有发生改变也没有改变快排依赖数组状况的问题。
利用随机取基准值的方法确实可以令这个问题得到改善但是取随机数本身也是需要一定的指令其产生的消耗也是一个需要考虑和权衡的问题。
