掌握排序算法面试法宝，不会代码也能薪资过万

1、简介

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由 C.A.R.Hoare 在 1962 年提出。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，一次达到整个数据变成有序序列。

2、算法原理

设要排序的数组是 A[0],A[1]…A[n-1]，首先取任意一个数据（通常选用数组的第一个）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，整个过程称为一趟快速排序。

值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是：

• 设置两个变量 left, right 用来表示数组元素索引，排序开始的时候：left=0, right=n-1

• 以第一元素作为关键数据，赋值给 key，即 key=A[0]

• 从 right 开始向前搜索，即由后开始向前搜索（right–)，找到第一个小于 key 的值 A[right]，将 A[right] 和 A[left] 互换。

• 从 left 开始向后搜索，即由前开始向后搜索(left++), 找到第一个大于 key 的 A[left], 将 A[left] 和 A[right] 互换；

• 重复第 3,4 步，直到 left=right，注意判断和搜索是同时进行的，也即是每次改变 left, right 都要进行判断。

3、排序演示

假设用户输入了如下数组： 创建变量 left=0(指向第一个数据)，right=5(指向最后一个数据)，k=6（赋值为第一个数据的值）。

要把所有比 k 小的数移到 k 的左面，开始寻找比 6 小的数，从 right 开始，从右往左找，不断递减变量 right 的值，找到第一个索引 3 的数据比 6 小，于是把数据 3 移到下标 0 的位置，把索引为 0 的数据 6 移到下标 3 的位置，完成第一次比较，结果如下： 此时，left=0, right=3 k=6

开始进行第二次比较，这次从左边开始找。递增变量 left，发现索引 2 的数据是一个比 k 大的，于是用索引 2 的数据 7 和 right 指向的下标 3 的数据 6 做交换，结果如下： 此时，left=2, right=3, k=6

称上面两次比较为一个循环。

接着，再递减变量 right, 不断重复进行上面的循环比较。

在本例中，进行一次循环，就发现 left 和 right 碰头了：他们都指向了下标 2。于是第一遍比较结束。凡是 k(=6)的左边的数都比它小，凡是右边的数都比它大。

如果 left 和 right 没有碰头的话，就递增 left 找大的，还没有，就再递增 right 找小的，如此反复，不断循环，注意判断和寻找是同时进行的。然后，对 k 两边数据，再分组分别进行上述过程，直到不能再分为止。

注意：第一遍快速排序不会直接得到最终结果，只会把比 k 大和比 k 小的数分到 k 的两边。

python 代码实现

实现上面的过程

#!/usr/bin/python  
# -*- coding: utf-8 -*-  

l = [6, 2, 7, 3, 8, 9]
left = 0
right = 5
key = l[0]
#  从右边找起找到比key小的值，然后与l[key]互换
while left = key:
    right -= 1

l[right], l[left] = l[left], l[right]

print('第一次从右往左交换：')
print('left=%s' % left, 'right=%s' % right)
print(l)

#  从左边找到比key大的值，然后与l[right]互换
while left