快速排序

简介

大家好！我是Tony,一个热爱技术，希望运用技术改变生活的的追梦男孩。今天花了30分钟手撸了快速排序

import java.util.Random;
public class MainSort {

    private static int[] inputEmptyCase = {};
    private static int[] inputCase0 = {4,2,6,5,3,8,3};
    private static int[] inputCase1 = {1};

    private static void println(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }

    public static void main(String[] args) {
        MainSort mainSort = new MainSort();
        int[] sortedResult = mainSort.quickSort(inputCase0);
        println(sortedResult);
    }

    public int[] quickSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }

        int start = 0;
        int end = nums.length - 1;
        return _quickSort(nums,start,end);
    }

    private int[] _quickSort(int[] nums,int start,int end) {
        if (start >= end) {
            return nums;
        }
        int flagIndex = partion(nums,start,end);
        if (flagIndex > start) {
            _quickSort(nums,start,flagIndex-1);
        }

        if (end > flagIndex) {
            _quickSort(nums,flagIndex+1,end);
        }
        return nums;
    }

    private int partion(int[] nums,int startIndex,int endIndex) {
        int start = startIndex;
        int end = endIndex;
        int FlagIndex = random(start,end);
        //先将旗帜移动到末尾
        swap(nums,FlagIndex,end);

        while (start < end) {
            while (nums[start] <= nums[end] && start < end) start++;
            if (start < end) swap(nums,start,end);
            while (nums[end] >= nums[start] && start < end) end--;
            if (end > start) swap(nums, start, end);
        }

        return start;
    }

    private void swap(int[] nums,int aIndex,int bIndex) {
        int temp = nums[aIndex];
        nums[aIndex] = nums[bIndex];
        nums[bIndex] = temp;
    }

    private int random(int startIndex,int endIndex) {
        if (startIndex < endIndex) {
            int length = endIndex - startIndex;
            Random random = new Random();
            int offset = random.nextInt(length);
            return startIndex + offset;
        }
        return startIndex;
    }

}