快速排序(java实现)

快速排序的思想

• 在一个无序的数组中，取最后的一个数字为基准值，在经过一次排序后，使得改无效而的数组中，小于基准值的在左侧，等于基准值的在中间，大于基准值的在右侧。
• 假设一个无序数组为
  
  那么他经过排序后的结果应该为：
  
  具体实现过程：
  在排序的时候，我们每次都取最后一个元素为基准值，创建p1指向无序数组元素的前一个位置，创建p2指向无序数组的最后元素的后一个位置。
  
  第一次排序，首先i指向第一个元素，判断当前元素是和基准值的大小
  大小的比较分为三种情况：
  第一种：该元素 < 基准值，则该元素与p1指向的前一个元素交换，p1++，i++
  第二种：该元素 = 基准值，测i++
  第三种：该元素 > 基准值，测该元素与p2指向的后一个元素交换，p2–，i不变
  例如：当前 [i] 的值为4 < 基准值 则符合第一种情况
  
  移动之后，当前的[i] 的值为5 = 基准值 ，则符合第二种情况
  
  移动之后，[i] 的值为 7 ，则符合第三种情况
  
  移动之后，[i] = 5 ，则符合第二种情况
  
  移动之后，[i] = 5 ，符合第二种情况
  
  移动之后，[i] = 3 ，符合第一种情况
  
  移动之后，i == p2 ，结束循环。
• 对于这一次循环来说，开始的基准值为最后一个元素，到循环结束之后，小于基准值的在侧，等于基准值的在中间，大于基准值的在右侧。相当与在这次遍历的过程，我们把等于基准值的一批数固定了位置。搞定了一批数。接下来只需要对左边的和右边的进行排序，重复此过程。最后就会把所有的数的位置固定下来。当所有的数的位置都固定下来了，那么就可以说这个数组使有序的了。
• p1 和 p2 指向的是什么呢，指的是小于基准值 和 大于基准值的范围，当出现符合条件的数，就把该数放到里面去。
• 结束循环的条件： 因为p2 指向的是 大于 基准值的边界，当 i 的下标 等于 p2 的时候，自然就没有继续遍历的必要了。

代码实现（java）

/**
 * 快速排序算法
 */
public class QuickSort {
    public static void quickSort(int[] array){
        if (array == null || array.length < 2) {
            return;     //array为空或者该数组元素为一，没有排序的意义
        }
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int[] array, int l, int r) {
        if ( l >= r){
            return;     //数据不合法，退出程序
        }
        //要向使l --> r中有序，先找到一个基准数,取数组的最后一个数为基准数
        int num = array[r];
        //找到基准数在数组中的位置，使得 < 基准数的在左边 ,等于基准数的在中间, > 基准数的在右边。
        int[] index = quick_sort(array, l, r,num);  //此时中间的 = sum的已经拍好序了
        quickSort(array,l,index[0]);        //使左边的有序
        quickSort(array,index[1],r);        //使右边的有序

    }

    private static int[] quick_sort(int[] array, int l, int r, int num) {
        //找到基准数在数组中的位置，使得 < 基准数的在左边 ,等于基准数的在中间, > 基准数的在右边。
        int p1 = l - 1;
        int p2 = r + 1;
        while (l < p2) {
            if (array[l] < num){
                //1.第一种情况，如果小于num的时候，将该元素与 < 范围的前一个交换，i++
                int temp = array[l];
                array[l] = array[p1 + 1];
                array[p1 + 1] = temp;
                l++;
                p1++;
            }else if (array[l] == num){
                //2.第二种情况，如果[l]==sum的时候，l++
                l++;
            }else {
                //3.第三种情况,如果[l] > sum的时候，[l] 与 > 范围的前一个元素交换
                int temp = array[l];
                array[l] = array[p2 - 1];
                array[p2 - 1] = temp;
                p2--;
            }
        }
        return new int[]{p1,p2};    //此时中间的 = sum的已经拍好序了、
    }

    public static void main(String[] args) {
        int[] array = new int[]{1,5,3,6,3,5,8,10,3};
        quickSort(array);
        for (int i : array) {
            System.out.println(i);
        }
    }
}