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

╰半夏微凉° 2022-06-09 00:42 254阅读 0赞

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));
    	}
    }