快速排序

算法简介

快速排序是（Quick sort）是对冒泡排序的一种改进，是非常重要且应用比较广泛的一种高效率排序算法。

算法思路

快速排序是通过多次比较和交换来实现排序，在一趟排序中把将要排序的数据分成两个独立的部分，对这两部分进行排序使得其中一部分所有数据比另一部分都要小，然后继续递归排序这两部分，最终实现所有数据有序。

大致步骤如下：

1.首先设置一个分界值也就是基准值又是也称为监视哨，通过该分界值将数据分割成两部分。
2.将大于或等于分界值的数据集中到右边，小于分界值的数据集中到左边。一趟排序过后，左边部分中各个数据元素都小于分界值，而右边部分中各数据元素都大于或等于分界值，且右边部分个数据元素皆大于左边所有数据元素。
3.然后，左边和右边的数据可以看成两组不同的部分，重复上述1和2步骤
当左右两部分都有序时，整个数据就完成了排序。

算法过程

例如一组数据[4,7,1,5,3,8,2,6]

1.首先选择4为基准，i从7开始往后遍历，j从6开始往前遍历。

2.i从前往后寻找大于基准4的元素，j从后往前寻找小于基准4的元素。

3.第一次寻找停止后i和j的位置如下[4,7,1,5,3,8,2,6]（绿色为i,红色为j）然后将i和j代表的元素进行交换。

4.得到如下结果[4,2,1,5,3,8,7,6]，重复2，3两步。

5.当i大于等于j时（指下标），跳出此次循环，将基准元素（首元素）与j指向的元素进行交换，完成第一次划分。

得到结果如下[3,2,1,4,5,8,7,6]

6.第一次划分后得到两个有序区，左边均小于基准，右边均大于基准。然后在两个区域内递归调用如上算法，最终完成排序。

代码实现