快速排序(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 x<pivot 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 right>left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)
这个版本经常会被使用在命令式语言中,像是C语言。
快速排序
快速排序是
二叉查找树(二叉搜索树)的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中,而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数,但是顺序不同。对于排序算法的稳定性指标,原地分区版本的
快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。