【排序算法】快速排序

源代码：https://gitee.com/AgentXiao/DataStructAndAlgorithm

一、简单介绍
快速排序是冒泡排序的改进版，是最好的一种内排序，使用到了分治和递归。
二、和冒泡排序的比较
冒泡排序的比较是发生在相邻的数中的，每次交换只能上移或者下移一个单元，因此比较和移动的次数多；而快速排序采用的是分治法，这个方法的基本思想是：
1、选定一个基准值（一般选择第一个数）
2、进行分区，将小于基准数的数放在左区，将大于等于基准数的数放在右区
3、对左右区的数重读第一和第二步，知道各个区间只剩下一个数为止。
三、分区图示（能够在纸上边画边说出分区的原理）
四、程序的实现（上级程序、手写程序）

import java.util.Arrays;

/**
 * @ClassName QuickSort
 * @Description 快速排序
 * @Author xwd
 * @Date 2018/10/12 18:00
 */
public class QuickSort {
    public static void main(String[] args) {
        //1、给出无序数组
        int[] arr = {85,64,56,91,23,56,56,21,22,47};
        //2、输出无序数字
        System.out.println(Arrays.toString(arr));
        //3、排序：快速排序。为了方便用户使用，只传入一个数组名
        quickSort(arr);
        //4、输出有序数组
        System.out.println(Arrays.toString(arr));
    }

    /**
     * @MethodName quickSort
     * @Descrition 快速排序
     * @Param [arr]
     * @return void
     */
    public static void quickSort(int[] arr) {
        //指定初始的low和high指针
        int low = 0;
        int high = arr.length - 1;
        quickSort(arr,low,high);
    }

    /**
     * @MethodName quickSort
     * @Descrition 使用递归完成快速排序
     * @Param [arr, low, high]
     * @return void
     */
    private static void quickSort(int[] arr, int low, int high) {
        if(low < high){
            //分区操作，将数组分为左右两个区,返回分区界限的索引值
            int index = partition(arr,low,high);
            //对左边分区进行快速排序
            quickSort(arr,low,index-1);
            //对右边分区进行快速排序
            quickSort(arr,index+1,high);
        }
    }
    /**
     * @MethodName partition
     * @Descrition 分区操作
     * @Param [arr, low, high]
     * @return int
     */
    private static int partition(int[] arr, int low, int high) {
        //指定指针
        int i = low;
        int j = high;
        //指定基准值
        int temp = arr[i];
        //循环实现分区
        while (i < j){
            //从右向左遍历，如果出现比基准值小的数则进行填坑，否则索引下降
            while (arr[j] >= temp && i < j){
                j--;
            }
            //填坑，左边索引向右移动一个位置
            if(i < j){
                arr[i] = arr[j];
                i++;
            }
            //从左向右遍历，如果出现大于等于基准值的数，则填坑，否则索引上升
            while (arr[i] < temp && i < j){
                i++;
            }
            //填坑，右边索引向左移动一个位置
            if(i < j){
                arr[j] = arr[i];
                j--;
            }
        }
        //使用基准值填坑
        arr[i] = temp;//arr[j] = temp;
        return i;//return j;
    }
}

五、其他注意事项
1、当选取的基准值为边界值时，为最坏的情况，时间复杂度为O(n2);当选区的基准值恰好为中间值时，为最好的情况，时间复杂度为O(n lbn)。
2、空间复杂度O(1*lb n)=O(lb n),使用了递归，需要使用到的空间变多
3、快速排序是一种不稳定排序