package me.wayne.sort.unstable;

import java.util.List;

import me.wayne.sort.SortUtils;

public class QuickSort {

    /**
     * 快速排序
     * 最差时间复杂度,O(n2),即每次partition的结果是为最大或最小的时候,相当于冒泡排序
     * 最好时间复杂度,O(n*log2n)
     * 空间复杂度O(log2n)~O(n)
     * 思路:每次随机取一个基准数,并将数列分为两部分,一部分比基准数小,另一部分比基准数大
     * 再对两部分进行递归调用
     */
    public static void sort(List<Integer> data) {
        quickSort(data, 0, data.size() - 1);
        System.out.println(data.toString());
    }

    private static void quickSort(List<Integer> data, int start, int end) {
        int index = partition(data, start, end);
        if (index - start > 1) {
            quickSort(data, start, index - 1);
        }
        if (end - index > 1) {
            quickSort(data, index + 1, end);
        }
    }

    private static int partition(List<Integer> data, int start, int end) {
        int i = (start + end) / 2;
        //以中间的值为基准,先将中间的值与末尾的值交换
        SortUtils.swap(data, i, end);

        int index = start;
        for (i = start; i < end; i++) {
            //每次都和基准数比较,比基准数小就往前换
            if (data.get(i) < data.get(end)) {
                SortUtils.swap(data, i, index++);
            }
        }

        //将基准数换到正确的位置
        SortUtils.swap(data, index, end);
        return index;
    }
}

@@ -48,16 +48,40 @@
 il.List;
+%0Aimport java.util.Stack;
 %0A%0Aimport
@@ -383,24 +383,26 @@
 er%3E data) %7B%0A
+//
         quic
@@ -430,24 +430,103 @@
 ize() - 1);%0A
+//        System.out.println(data.toString());%0A        nonRecursionSort(data);%0A
         Syst
@@ -1334,32 +1334,32 @@
 a, index, end);%0A
-
         return i
@@ -1369,11 +1369,670 @@
 x;%0A    %7D
+%0A%0A    private static void nonRecursionSort(List%3CInteger%3E data) %7B%0A        Stack%3CInteger%3E stack = new Stack%3CInteger%3E();%0A%0A        int start = 0, end = data.size() - 1, partition;%0A        stack.push(start);%0A        stack.push(end);%0A%0A        while (!stack.isEmpty()) %7B%0A            end = stack.pop();%0A            start = stack.pop();%0A            partition = partition(data, start, end);%0A            if (partition - start %3E 1) %7B%0A                stack.push(start);%0A                stack.push(partition - 1);%0A            %7D%0A            if (end - partition %3E 1) %7B%0A                stack.push(partition + 1);%0A                stack.push(end);%0A            %7D%0A        %7D%0A%0A    %7D
 %0A%7D%0A

change : add non-recursion quick sort.