数据结构与算法：快速排序

数据结构与算法

对冒泡排序的一种改进，用到了分治法的思想，基本思想是将要排序的数据分割成独立的两个部分，其中一部分的所有数据要比另外一部分的所有数据都要小，不断递归，直至有序

1、设立一个分界值，这个分界值将数组分成左右两部分
2、大于等于分界值的数据放在分界值右边，小于分界值的数据放在分解值左边（从小到大排序的情况下），此时，分界值左边的数全部小于分界值右边的数
3、同时，分界值左右两边的数据又可以独立分割，左右两边的数据又可以各取一个分界值，大于等于分界值的数放右边，小于分界值的放左边。。。
4、重复上述过程，即递归，直到数组排好序。。。

1、找一个基准值，用两个指针分别指向数组的头部和尾部
2、先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，记录指针所在位置
3、再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，记录指针所在位置
4、交换当前左边指针位置和右边指针位置的元素
5、重复2,3,4步骤，直到左边指针大于右边指针时停止，或者左边指针到大最右端，右边指针到大最左端。

第一轮：

第二轮：

接下来将拆出来的数组合起来

public class QuickSort { //比较大小 private static boolean less(Comparable a, Comparable b){ return a.compareTo(b)<0; } //交换两个数位置 private static void exchange(Comparable[] a, int i, int j){ Comparable t = a[i]; a[i] = a[j]; a[j] = t; } public static void sort(Comparable[] a){ int lo = 0; int hi = a.length - 1; sort(a,lo,hi); } private static void sort(Comparable[] a, int lo, int hi){ //安全性校验 if(hi<=lo){ return ; } //将数组分成左子组和右子组 int partition = partition(a, lo, hi); //返回的是分组的分界值所在的索引， //让左子组有序 sort(a, lo, partition-1); //让右子组有序 sort(a, partition+1, hi); } public static int partition(Comparable[] a, int lo, int hi){ //确定分界值 Comparable key = a[lo]; //定义两个指针，分别指向待切割元素的最小索引处以及最大索引的下个位置 int left = lo; int right = hi+1; //切分 while(true){ //从右往左扫描，移动right指针，找到一个比分界值小的元素 while(less(key,a[--right])){ //如果右边指针到了lo位置，则停止 if (right == lo) { break; } } //从左往右扫描，移动left指针，找到一个比分界值大的元素 while(less(a[++left],key)){ //如果左边指针到了hi位置，则停止 if(left == hi){ break; } } //判断left>=right，是，扫描完毕，否，交换两者位置上的值 if(left>=right){ break; }else{ exchange(a,left,right); } } //交换基准值（这里的基准值为数组第一个数） exchange(a,lo,right); return right; }}

就~挺费脑子的。。。哈哈哈，弄懂了就好，有误望指出，有更好的方法欢迎评论区分享，一起进步呀。