快排-java实现

快排是一种高效的排序方式，时间复杂度为n*log(n)，一次递归需要比较n次，递归的深度为log(n)，最坏的情况下，时间复杂度为(1/2)*n*(n-1)，已排序的数组，每次比较的次数为(n-1)+(n-2)+……+1

代码实现如下：

package com.syj.test.sort;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by syj on 2018/12/11.
 *
 * @dsc 快排算法介绍 http://blog.51cto.com/flyingcat2013/1281614
 * https://blog.csdn.net/IT_ZJYANG/article/details/53406764
 *
 */
public class QuickSort {


    public static void main(String[] args) {
        int arr[] = {3,7,2,9,1,4,6,8,10,5};
        int low = 0;
        int high = arr.length-1;
        qsort(arr, low, high);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 将数组拆分，递归进行二分查找
     * @param arr
     * @param low
     * @param high
     */
    private static void qsort(int[] arr, int low, int high) {
        if (low < high) {
            int position = partion(arr, low, high);
            qsort(arr, low, position-1);
            qsort(arr, position+1, high);
        }
    }

    /**
     * 按照最右侧的元素为基准，返回基准值在low~high范围中的位置
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static int partion(int[] arr, int low, int high) {
        int baseVal = arr[high];

        while (low < high) {
            //从左侧开始查找大于基准值的元素，并移到右侧
            while (low < high && arr[low] <= baseVal) {
                low++;
            }
            arr[high] = arr[low];
            //从右侧开始查找小于基准值的元素，并移到左侧
            while (low < high && arr[high] >= baseVal) {
                high--;
            }
            arr[low] = arr[high];
        }
        //将基准值移到中位
        arr[low] = baseVal;
        //返回中间位置
        return low;
    }
}