十大排序算法（四）--- 快速排序

快速排序算法采用的是分治法的思想(Divide and Conquer), 它把一个待排序的数组，以某个元素或者称为基准(这里记为PIVOT)为界，分为两个子数组，比PIVOT小的全部移到到PIVOT左边，比PIVOT大的全部移动到PIVOT右边。再分别对以PIVOT分开的两个子数组重复该过程，直到无法再分。

快速排序正常情况下时间复杂度为O(nlogn)。最坏情况下为O(n^2)。最坏情况发生在每次排序都需要移动所有剩下待排序的元素，这种情况虽然很少发生，但是为了避免这样的情况可以采用随机选择PIVOT元素的方法来预防。下面描述算法的实现步骤：

1. 随机的从待排序数组中选择一个元素作为PIVOT
2. 将所有比PIVOT小的数放到PIVOT的左边，比PIVOT大的数放到PIVOT的右边。跟PIVOT一样大的数，放到左右都可以。这个步骤称为Partition。这样以PVIOT为界分成了左右两个子数组。
3. 对#2分成两个子数组递归进行#1~#3操作，直到排序完成。

假设我们要对A[5, 3, 6, 1, 2, 8]留个数进行排序，下图展示了排序的过程。

快速排序过程展示

绝大多数情况下，快速排序是高效的，但是快速排序不是稳定的。下面是python的代码实现。有兴趣的同学，也可以用其它编程语言尝试实现一下。

import random

A = [5, 3, 6, 1, 2, 8]

def quick_sorting(data, left, right):

if left >= right : return

mark = random.randint(left, right)

data[left], data[mark] = data[mark], data[left]

mark = left

tmp = data[left]

for i in range(left 1, right 1):

if data[i] < tmp:

mark = 1

data[i], data[mark] = data[mark], data[i]

data[left], data[mark] = data[mark], data[left]

quick_sorting(data, left, mark-1)

quick_sorting(data, mark 1, right)

def main():

right=len(A)-1

left = 0

#Ascending

quick_sorting(A, left, right)

print(A)

if __name__=='__main__':

main()

将上面的代码保存到一个文本文件，后缀名修改为.py。可以用python解释器执行一下，会输出如下结果：

可以看到，排序正确。