快速排序的递归非递归算法

一.递归算法

public static void kuaipai(int[] a,int left,int right){
		if(left>right){
			return ;
		}
		int i=left,j=right;
		int tmp=a[left];
		while(i<j){
			while(tmp<=a[j]&&i<j){
				j--;
			}
			while(tmp>=a[i]&i<j){
				i++;
			}
			if(i<j){
				int t=a[j];
				a[j]=a[i];
				a[i]=t;
			}
		}
		a[left]=a[i];
		a[i]=tmp;
		kuaipai(a,left,j-1);
		kuaipai(a,j+1,right);
	}

二.非递归算法
利用栈后进先出的原理存放左右索引

public static void kuaipai2(int[] num){
	        int start = 0;  
	        int end = num.length - 1;  
	        int middle = 0;  
	        Stack<Integer> index = new Stack<Integer>();  
	        index.push(start);  
	        index.push(end);  
	        while (!index.isEmpty()) {  
	  
	            end = index.pop();  
	            start = index.pop();  
	            int i = start;  
	            int j = end;  
	            int pivot = num[i]; 
	            while (i < j) {  
	                while (i < j && num[j] >= pivot)  
	                    j--;  
	                num[i] = num[j];  
	                while (i < j && num[i] <= pivot)    
	                    i++;  
	                num[j] = num[i];  
	            }  
	            num[i] = pivot;  
	            middle = i;  
	            if (middle - 1 > start) {  
	                index.push(start);  
	                index.push(middle - 1);  
	            }  
	            if (middle + 1 < end) {  
	                index.push(middle + 1);  
	                index.push(end);  
	            }  
	        }  
	        
	    }