快速排序优化（快速排序优化版）
本文目录一览：
快速排序特点
快速排序（Quicksort）是对冒泡排序的一种改进，由东尼·霍尔在1960年提出。 快速排序是指通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。
分类
排序算法
数据结构
不定
最坏空间复杂度
根据实现的方式不同而不同
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
从数列中挑出一个元素，称为“基准”（pivot），
重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
在简单的伪代码中，此算法可以被表示为：
function quicksort(q)
{
var list less, pivotList, greater
if length(q) ≤ 1
return q
else
{
select a pivot value pivot from q
for each x in q except the pivot element
{
if xpivot then add x to less
if x ≥ pivot then add x to greater
}
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
}
原地（in-place）分区的版本
上面简单版本的缺点是，它需要的额外存储空间，也就跟归并排序一样不好。额外需要的存储器空间配置，在实际上的实现，也会极度影响速度和缓存的性能。有一个比较复杂使用原地（in-place）分区算法的版本，且在好的基准选择上，平均可以达到空间的使用复杂度。
function partition(a, left, right, pivotIndex)
{
pivotValue = a[pivotIndex]
swap(a[pivotIndex], a[right]) // 把pivot移到结尾
storeIndex = left
for i from left to right-1
{
if a[i]= pivotValue
{
swap(a[storeIndex], a[i])
storeIndex = storeIndex + 1
}
}
swap(a[right], a[storeIndex]) // 把pivot移到它最後的地方
return storeIndex
}
这是原地分区算法，它分区了标示为"左边（left）"和"右边（right）"的序列部分，借由移动小于的所有元素到子序列的开头，留下所有大于或等于的元素接在他们后面。在这个过程它也为基准元素找寻最后摆放的位置，也就是它回传的值。它暂时地把基准元素移到子序列的结尾，而不会被前述方式影响到。由于算法只使用交换，因此最后的数列与原先的数列拥有一样的元素。要注意的是，一个元素在到达它的最后位置前，可能会被交换很多次。
一旦我们有了这个分区算法，要写快速排列本身就很容易：
procedure quicksort(a, left, right)
if rightleft
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)
这个版本经常会被使用在命令式语言中，像是C语言。
快速排序
快速排序是二叉查找树（二叉搜索树）的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中，而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数，但是顺序不同。对于排序算法的稳定性指标，原地分区版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。
MySQL 排序优化
2.1 排序方式
数据量小则在内存排序, 数据量大则使用磁盘排序
内存排序 : 直接使用"快速排序"
磁盘排序 : 先将数据分块, 对每个独立的块使用"快速排序", 并将各个块的排序结果存在磁盘上, 然后将各个排好序的块进行合并(merge), 最后返回排序结果
2.2 排序算法
3. 注意点 :
快速排序到底有多快？
上期为大家介绍了快速排序（Quicksort），有很多同学会问： 快排是不是比之前几种排序都要快？它到底有多快？ ，那就让我们一起来做个小实验测试一下吧！
目前给大家介绍过了6种排序：冒泡排序、选择排序、
插入排序、希尔排序、归并排序、快速排序，并且在上期讲 快速排续 时给出了快排的优化方案：对于大数据集排序先使用 快排 ，当分区达到一定小的时候使用 插入排序 ，有同学就有疑惑：为什么当分区达到一定小时要用 插入排序 ，这样真的会变快吗？
冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序
随机生成一个数据集，数据个数从10，100，1000依次递增到10万个
比较每个排序算法所用时长，多次测试，减少误差
首先对 随机数 进行排序，看看哪个排序方法较快；然后再对“ 基本有序 ”的数据集排序，再比较这几种排序方法用时。
使用randint随机生成整数
数据集生成的基本思路：先生成一个有序数列，然后将少量数据插入有序数列中，这里取 0.1*n 个乱序插入到 0.9*n 个有序数列中。
时间单位是秒，多次测试结果基本差不多，这里猪哥随机选取依次测试结果， 全场敷冰进行，请勿模仿 ：
冒泡排序耗时：2.4080276489257812e-05
选择排序耗时：1.9311904907226562e-05
插入排序耗时：1.5020370483398438e-05
希尔排序耗时：1.5974044799804688e-05
归并排序耗时：2.8848648071289062e-05
快速排序耗时：1.9073486328125e-05
冒泡排序耗时：0.000782012939453125
选择排序耗时：0.0004570484161376953
插入排序耗时：0.00039076805114746094
希尔排序耗时：0.00018095970153808594
归并排序耗时：0.0003409385681152344
快速排序耗时：0.00017905235290527344
冒泡排序耗时：0.08327889442443848
选择排序耗时：0.03776884078979492
插入排序耗时：0.04986977577209473
希尔排序耗时：0.0034036636352539062
归并排序耗时：0.005920886993408203
快速排序耗时：0.0021750926971435547
冒泡排序耗时：8.781844854354858
选择排序耗时：3.438148021697998
插入排序耗时：4.186453819274902
希尔排序耗时：0.05663800239562988
归并排序耗时：0.06386470794677734
快速排序耗时：0.02335190773010254
冒泡排序耗时：900.5480690002441
选择排序耗时：879.1669909954071
插入排序耗时：428.66180515289307
希尔排序耗时：0.967015266418457
归并排序耗时：1.4872560501098633
快速排序耗时：0.3050980567932129
再经过几小时等待后，我仿佛闻到一股烧焦的味道，真香～
冒泡排序耗时：2.288818359375e-05
选择排序耗时：1.9788742065429688e-05
插入排序耗时：1.3113021850585938e-05
希尔排序耗时：1.5974044799804688e-05
归并排序耗时：2.9087066650390625e-05
快速排序耗时：1.811981201171875e-05
冒泡排序耗时：0.0004851818084716797
选择排序耗时：0.0004131793975830078
插入排序耗时：0.00013065338134765625
希尔排序耗时：0.00015997886657714844
归并排序耗时：0.00032019615173339844
快速排序耗时：0.00015974044799804688
冒泡排序耗时：0.05040717124938965
选择排序耗时：0.03394508361816406
插入排序耗时：0.009570121765136719
希尔排序耗时：0.0029370784759521484
归并排序耗时：0.005821943283081055
快速排序耗时：0.0022530555725097656
冒泡排序耗时：5.24026083946228
选择排序耗时：3.340329885482788
插入排序耗时：0.8101489543914795
希尔排序耗时：0.04622912406921387
归并排序耗时：0.05988883972167969
快速排序耗时：0.023930788040161133
无
我们从两种数据结果看，冒泡几乎都是最慢的
我们看到在随机数排序结果中，只有当 n=10 时，快排反而比较慢，而插入和希尔排序相对较快，这是因为插入排序和希尔排序都属于插入类型的排序，而快排和冒泡属于交换类排序，数据量少时交换所消耗的资源占比大。
在基本有序数据排序结果中，当n=10和n=100中都是插入排序消耗时间更短，因为数据基本有序，所以需要插入的次数比较少，尽管插入排序需要一个一个比较，但因为数据量不大，所以比较所消耗的资源占比不会太大。
快排果然还是名副其实的快，我们看到当数据集达到十万级别时，冒泡排序已经用时800多秒，而快排只用了0.3秒，相信随着数据量的增大，它们之间的差距也会越来越大。
之前我们讲过快排优化方案：对于大数据集排序先使用 快排 ，使数据集达到 基本有序 ，然后当分区达到一定小的时候使用 插入排序 ，因为插入排序对少量的基本有序数据集性能优于快排！
快速排序法在什么情况下最不利于发挥其长处
快速排序分为两个步骤，一是枢轴的选取，二是依据枢轴划分序列。
当选取的枢轴划分出来的两个序列在元素数量上有明显倾斜时，不利于发挥其长处。在划分出来的序列
元素个数相等或相近的时候其优势较为明显。
例如：在枢轴选取算法设定为序列首元素时，若首元素是该序列的最大或最小元素，即序列基本有序
时，此时划分的两个序列会出现一个序列包含枢轴外的所有元素，另一个序列不包含任何元素的情况，
则此时显然很不利于快速排序算法发挥其长处。
一般情况可以通过修改枢轴的选取算法来优化其性能。
数据结构中快速排序算法的不足以及改进？
一般快速排序算法都是以最左元素作为划分的基准值，这样当数据元素本身已经完全有序（不管正序或者逆序）时，每一趟划分只能将一个元素分割出来，其效率很低：时间复杂度O(n^2)，空间复杂度为O(n)
所以改进方法就是找寻合适的基准值，保证不至于在关键字有序或者接近有序时发生这个情况，一般可以使用三者取中（就是待划分序列的头元素、尾元素、中间元素三者的中间值）、或者随机选择等方法，这样即使关键字完全有序，也可以保证时间复杂度O(nlogn)，空间复杂度O(logn)
关于快速排序优化和快速排序优化版的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注云尚网络www.ysfad.net。
相关文章
发表评论
暂时没有评论，来抢沙发吧~