Massive Algorithms: QUICKSORT (Java, C++) | Algorithms and Data Structures

快速排序的递归实现与非递归实现
首先我们得明白递归函数其实是需要在栈中保护现场的，故我们可以构建一个保护状态的栈。在快排中，状态其实就是排序的边界，其原理是通过分割将待排序列划分为一个个小片段，然后逐一排序好，所以需要保护的状态其实就是待排小片段的边界。

    private static int partition(int[] nums, int start, int end){

        int tmp = nums[start];

        while(start < end){

            while(nums[end]>=tmp && start<end) end--;

            if(start<end) nums[start++] = nums[end];

            while(nums[start]<=tmp && start<end) start++;

            if(start<end) nums[end--] = nums[start];

}

        nums[start] = tmp;

        return start;

}

    // 递归版快速排序

    public static void quickSort(int[] nums, int start, int end){

        if(start >= end || nums == null || nums.length < 2) return;

        int p = partition(nums, start, end);

        quickSort(nums, start, p-1);

        quickSort(nums, p+1, end);

}

    // 非递归版快速排序

    public static void quickSortIterative(int[] nums){

        if(nums == null || nums.length < 2) return;

        int left = 0;

        int right = nums.length - 1;

        Stack<Integer> stack = new Stack<Integer>();

        stack.push(left);

        stack.push(right);

        while(!stack.isEmpty()){

            int h = stack.pop();

            int l = stack.pop();

            int p = partition(nums, l, h);

            if(p - l > 1){

                stack.push(l);

                stack.push(p-1);

}

            if(h - p > 1){

                stack.push(p+1);

                stack.push(h);

}

}

}

int partition(int arr[], int left, int right)

{

int i = left, j = right;

int tmp;

int pivot = arr[(left + right) / 2];

while (i <= j) {

while (arr[i] < pivot)

i++;

while (arr[j] > pivot)

j--;

if (i <= j) {

tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

i++;

j--;

}

};

return i;

}

void quickSort(int arr[], int left, int right) {

int index = partition(arr, left, right);

if (left < index - 1)

quickSort(arr, left, index - 1);

if (index < right)

quickSort(arr, index, right);

}

Labels