学步园

这算法原理知道，但代码写起来总是丢三落四，这回写出来备份。。。

 

import java.util.*;

public class QSort {
	static int partition(int[] a, int l, int r) {
		int tmp = a[l];
		while (l < r) {
			//注意：a[r] >= tmp 以及 a[l] <= tmp 中 = 不能丢，否则有相同数字的话死循环
			while (l < r && a[r] >= tmp) r--;
			a[l] = a[r];
			while (l < r && a[l] <= tmp) l++;
			a[r] = a[l];
		}
		a[l] = tmp;
		return l;
	}
	static void quickSort(int[] a, int l, int r) {
		if (l < r) {
			int privot = partition(a, l, r);
			quickSort(a, l, privot-1);
			quickSort(a, privot+1, r);
		}
	}
	static void print(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
		Random rand = new Random();
		int[] a = new int[25];
		for (int i = 0; i < a.length; i++) {
			a[i] = rand.nextInt(100);
		}
		print(a);
		quickSort(a, 0, a.length-1);
		print(a);
	}
}