QuickSort

package Java;

public class QuickSort {
    /**
     * 时间复杂度O(nlogn)
     * 空间复杂度O(logn)递归需要栈的辅助
     * 最坏时间复杂度O(n^2)
     * @param nums
     * @param start
     * @param end
     */

    public static void QuickSort(int[] nums, int start, int end) {
        int i = start;
        int j = end;
        if (start >= end) {
            return;
        }
        int temp = nums[i];
        while (i < j) {
            //从右往左扫描，找到小于temp的值
            while (i < j && nums[j] >= temp) {
                j--;
            }
            //找到小于temp的值，将其赋值给nums[i]，并将i向右移一位。
            if (i < j) {
                nums[i] = nums[j];
                i++;
            }
            //从左往右扫描，直到找到大于temp的值
            while (i < j && nums[i] <= temp) {
                i++;
            }
            //找到大于temp的值，将其赋值给nums[j]，并将j往左移一位。
            if (i < j) {
                nums[j] = nums[i];
                j--;
            }
        }
        //最后是temp的值
        nums[i] = temp;
        //递归将temp左边的数组排序
        QuickSort(nums, start, i - 1);
        QuickSort(nums, i + 1, end);
        //递归将temp右边的数组排序
    }


    public static void main(String[] args) {
        int[] nums = {6,89,2,11,3,79,51,19,87};
        QuickSort(nums, 0, nums.length - 1);

        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}