八种排序算法之快速排序算法

使用分治策略的快速排序，是一种很好的内排序，经常出现在面试题中，所以如果你想成为一名有优秀的程序员，理解并熟练掌握快速排序是你必须要学会的基本技能之一。

• 快速排序的时间复杂度：
  快速排序的平均时间复杂度为O（n×log（n）），最差时间复杂度为O（n^2）

• 快速排序的基本思想：

1. 把整个待排序序列看成一个数组，从此数组中任意挑选一个数（一般是最左边的元素）作为基准元素。

2. 将待排序元素进行分区，以这个基准元素作为标准，比它大的放在右边，比它小的放在左边。

3. 对左右两个分区依次重复以上操作，直到所有元素完全拍好顺序。

图例：
待排序元素的初始状态

以最左边的元素5作为基准元素，

首先right指针指向3,3<5,因此用元素3补全left指针指向的位置，然后left右移。

此时left指针指向6,6>5,6补全right指针指向的空位，right指针左移。

发现此时，right指向的元素7>5,则 7号元素不移动，right指针左移。

此时right指向2,2<5.元素2移动到left指针指向的位置，left指针右移。

left指针和right指针重合结束本次排序，观察到还是无序状态依次左右分区进行以上操作，即可完成快速排序。