快速排序 

基本思想 :  1. 选取数组中 最后一个元素 , 通过遍历, 将大于和小于的元素交换到, 该元素的左右两侧 ; 2. 接着将两侧的元素, 通过上述的方法进行递归处理, 直至 递归到一个元素;

实现思路: 在start元素上 , 设置两个游标 (i ,j).  分如下三种情况, 对游标进行移动 :

       1. 如果该元素 大于 最后一个元素 , 将 j 游标往后移动一位;

       2. 当该元素 小于 最有一个元素时 , 两个游标在同一个位置 ,则将 j, 和 i 位置的元素 同时后移动一位;

       3. 当该元素 小于 最有一个元素时 , 两个游标不在一个位置 ,则将 j, 和 i 位置的元素 进行交换位置后,同时后移动一个位置;

如图 :

思路流程图

代码实现 :

实现代码

时间复杂度:  最坏: O(n2) , 平均: O(nlogn)

空间复杂度: 上面方法是原地排序 O(1)

核心总结 :  1. 递归     2. 分区   主要是原地排序的分区