快速排序的递归与非递归实现-向日葵屋

快速排序的递归与非递归实现

import java.util.Arrays;
import java.util.Stack;
class QuickSort 
{
    public static void quickSort(int[] array)
    {
        if (array==null||array.length==0)
        {
            return;
        }
        //递归算法
        //quickSortCore(array,0,array.length-1);
        //非递归
        quickSortCore2(array,0,array.length-1);
    }
    public static void quickSortCore(int[] array, int p, int r)
    {
        if (p<r)
        {
            int q=partition(array, p,r);
            quickSortCore(array,p,q-1);
            quickSortCore(array,q+1,r);
        }
    }
    public static int partition(int[] array, int p, int r)
    {
        int x=array[r];
        int i=p;
        int j=i;
        while (i<r)
        {
            if(array[i]<x)
            {
                swap(array,i,j);
                j++;
            }
            i++;
        }
        swap(array,r,j);
        return j;
    }
    public static void swap(int[] array, int i,int j)
    {
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
    //非递归，用循环？用栈记录？记录什么？记录当前划分序列的下标起始点
    public static void quickSortCore2(int[] array, int start, int end)
    {
        Stack<Integer> stack=new Stack<Integer>();
        stack.push(start);
        stack.push(end);
        while (!stack.empty())
        {
            //后进先出
            int r=stack.pop();
            int p=stack.pop();
            //划分的终止条件
            if (p>=r)
            {
                continue;
            }
            int q=partition(array,p,r);
            stack.push(p);
            stack.push(q-1);
            stack.push(q+1);
            stack.push(r);
        }
    }
    public static void main(String[] args) 
    {
        int[] array={2,5,8,4,7,3,6};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}