网站建设项目验收报告,做网站麻烦吗,深圳网页技术开发公司,2016最新wordpress模板下载基本概念
快速排序是一种基于交换的排序算法#xff0c;该算法利用了分治的思想。
整个算法分为若干轮次进行。在当前轮次中#xff0c;对于选定的数组范围[left, right]#xff0c;首先选取一个标志元素pivot#xff0c;将所有小于pivot的元素移至其左侧#xff0c;大于…基本概念
快速排序是一种基于交换的排序算法该算法利用了分治的思想。
整个算法分为若干轮次进行。在当前轮次中对于选定的数组范围[left, right]首先选取一个标志元素pivot将所有小于pivot的元素移至其左侧大于pivot的则移动至其右侧记录下最终pivot所处的位置pivot_pos。然后再利用递归分别对左侧区间[left, pivot_pos - 1]和右侧区间[pivot_pos 1, left]执行相同操作依次类推最终对整个数组完成排序。 以数组[16, 1, 2, 25, 9, 2, 5]为例在递归实现中其排序过程中交换策略如下图所示。当pivot_pos与i相等时不需要交换之所以先将pivot_pos再交换的原因是此时i指向的是小于pivot的元素而pivot_pos是小于标志元素范围的右边界如图如果pivot_pos 1 i则直接将这个右边界扩大1即可而无需交换。如果不是则将pivot_pos 1以指向这个大于pivot的元素并将其与小于pivot的array[i]进行交换从而扩大右边界。下面给出了递归实现的示例代码。
int partition(int *array, int left, int right) {// * 默认选定首个元素为划分元素int pivot_pos left, pivot_val array[left];// * 遍历将小于划分元素的值交换至其左侧for (int i left 1; i right; i) {if (array[i] pivot_val) {pivot_pos 1;if (pivot_pos ! i) {swap(array[i], array[pivot_pos]);}}}array[left] array[pivot_pos];array[pivot_pos] pivot_val;return pivot_pos;
}// * 递归版快速排序 O(nlogn)
void quickSort(int *array, int left, int right) {if (left right) {int pivotpos partition(array, left, right);quickSort(array, left, pivotpos - 1);quickSort(array, pivotpos 1, right);}
}算法分析
时间复杂度
最好情况每次划分均得到等长的两个子序列 O ( n l o g n ) O(nlogn) O(nlogn)最坏情况每次划分得到的子序列只比上一层长度少1 O ( n 2 ) O(n^2) O(n2)平均情况 O ( n l o g n ) O(n log_n) O(nlogn)
此外快速排序是一种不稳定的排序算法。
技巧应用
面试题 17.14. 最小K个数 - 力扣LeetCode 设计一个算法找出数组中最小的k个数。以任意顺序返回这k个数均可。 示例 输入 arr [1,3,5,7,2,4,6,8], k 4 输出 [1,2,3,4] 提示 0 len(arr) 100000 0 k min(100000, len(arr)) 请注意上面这个题不要求返回的顺序。我们可以用快速排序对该数组进行排序操作。考虑一下快速排序的流程是先对整体数组进行划分然后再依次对划分元素的左侧和右侧进行划分逐层递归。当划分元素的位置等于k或k 1时[0, k - 1]实际上已经是数组前k小的数了没有必要继续对数组做完全排序因此可以将pivotpos k || pivotpos k 1作为递归出口。
示例代码如下
class Solution {
// 采用STL迭代器组合表示待排序的范围range
private:using Iter vectorint::iterator;Iter partition(Iter left, Iter right) {Iter pivot_pos left;int pivot_val *left;for (Iter i left 1; i right; i) {if (*i pivot_val) {pivot_pos 1;if (pivot_pos ! i) {iter_swap(pivot_pos, i);}}}iter_swap(left, pivot_pos);return pivot_pos;}void quicksort(Iter left, Iter right, Iter tar) {if (left right) {Iter pivot_pos partition(left, right);if (pivot_pos tar 1) {quicksort(left, pivot_pos, tar);}if (pivot_pos tar) {quicksort(pivot_pos 1, right, tar);}// 仅当等于tar或者tar1时// 才可判定pivot_pos的左侧范围为前k小或前k1小}}public:vectorint smallestK(vectorint arr, int k) {if (arr.empty() || k 0) return {};quicksort(arr.begin(), arr.end(), arr.begin() k - 1);vectorint rtn(arr.begin(), arr.begin() k);return rtn;}
};拓展
在快速排序算法中一个关键操作就是选择基准点Pivot元素将被此基准点分开成两部分。
最经常使用的就是选择一个区间的首元素或者尾元素如本文所给出的示例。但是当数组部分有序时这样做通常会使算法陷入坏情况从 O ( n l o g n ) O(nlog_n) O(nlogn) 劣化到 O ( n 2 ) O(n^2) O(n2)。
研究人员为此设计了一个快速排序的变体选择首、尾、中间元素之中的中位数作为基准依次避免特殊情况下算法劣化到 O ( n 2 ) O(n^2) O(n2)。但是即便性能有所提升但是仍然有机会针对这种算法设计出一些特殊构造数组以延长排序时间。这可能会造成服务器计算时间过程进而为拒绝服务攻击提供可乘之机。
大卫·穆塞尔在1997年提出了内省排序算法introsort。旨在改善上述情况。introsort的主要步骤如下
快速排序最初使用快速排序对数组进行排序。递归深度检查在递归过程中检查当前的递归深度。如果深度超过 2 l o g n 2 logn 2logn则切换到堆排序。堆排序当递归深度过深时使用堆排序对当前子数组进行排序。插入排序在数组小于一定阈值通常是16或更小时使用插入排序进行排序以提高小数组排序的效率。
使用这种组合算法可以在正常快速排序算法的平均和最坏情况下将时间复杂度均保持为 n l o g n nlogn nlogn。
C STL算法库中的sort函数在早期版本LWG713之前未对最坏情况的时间复杂度做要求那个时候的标准库使用普通qsort实现就符合要求。在此之后标准对最坏情况的时间复杂度进行了修正后面的标准库实现版本使用的就是introsort算法。 LWG-xxx : 由 ISO C 标准委员会的图书馆工作组LWG跟踪的某个特定问题编号。
