洛谷-1177 快速排序模闆（java）

用傳統的快速排序，由于後面的資料量過大會導緻遞歸的時候棧溢出。是以需要改進下。

每次把要排序的資料分成兩半，使其左邊一半小于等于key，右邊一半大于等于key（key是數組中的一個數，可以随機抽取），這樣，隻需要log2n次就可以處理完，每次周遊一次數組，總體複雜度nlog2n。

package _5_21;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int []a;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		a= new int[n];
		for(int i=0;i<n;i++) {
			a[i] = sc.nextInt();
		}

		sort(0,n-1);
		
		for(int i=0;i<n;i++) {
        	if(i==n-1) {
        		System.out.println(a[i]);
        	}else {
        	System.out.print(a[i]+" ");
        	}
        }
	}

	private static void sort(int l, int h) {
		// TODO Auto-generated method stub
		int i = l;
		int j = h;
		int k = a[(l+h)/2];
		while(i<=j) {
			while(a[j]>k) {
				j--;
			}
			while(a[i]<k) {
				i++;
			}
			if(i<=j) {
				int t = a[i];
				a[i] = a[j];
				a[j] = t;
				i++;j--;
			}
		}
		if(l<j) sort(l,j);
		if(i<h) sort(i,h);
	}
	

}

           

嗯，哭死在廁所就可以了