快速排序总结

核心：

• 每次以left index作为基准数字
• 先从右向左找第一个比基准数字小的数，再从左向右找比基准数字大的数。这样最后leftPoint == rightPoint 时，nums[rightPoint] 总是比基准数字小或者就是基准数字，可以放心的交换，保证交换后的nums[left] 不大于基准数字
• 和基准数字相同的数不用管，经过递归后，总能交换到基准数字附近
• 每递归一次，就能保证基准数字在准确的index上，并且左边的数不大于基准数字，右边的数不小于基准数字
• 归并排序的目的是先让小范围数组有序，再让大范围数组有序

package com.company;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
	    int[] nums= new int[]{6,4,2,6,7,4,8,9,3,1};
	    quickSort(nums, 0, nums.length);
        System.out.println(Arrays.toString(nums));
    }

    public static void quickSort(int[] nums, int left, int right) {
        if(left >= right) {
            return;
        }
        int standard = nums[left];
        int leftPoint = left;
        int rightPoint = right-1;
        while(leftPoint<rightPoint) {
            while (nums[rightPoint] >= standard && leftPoint<rightPoint){
                rightPoint--;
            }
            while (nums[leftPoint] <= standard && leftPoint<rightPoint) {
                leftPoint++;
            }
            if(leftPoint < rightPoint) {
                int temp = nums[leftPoint];
                nums[leftPoint] = nums[rightPoint];
                nums[rightPoint] = temp;
            }
        }
        nums[left] = nums[leftPoint];
        nums[leftPoint] = standard;
        quickSort(nums, left, leftPoint);
        quickSort(nums, leftPoint+1, right);
    }


}