quick.java

来自「演示各种排序算法,并且演示java中类,对象,继承等用法.」· Java 代码 · 共 40 行

package sort_source;

public class Quick extends Bubble{
	// 快速排序
	public  void quick_sort(int[] data) {
		quickSort(data, 0, data.length - 1);
	}

/*	private static void swap(int[] a, int one, int two) {
		int temp = a[one];
		a[one] = a[two];
		a[two] = temp;
	}*/
	private  void quickSort(int[] data, int i, int j) {
		int pivotIndex = (i + j) / 2;
		// swap
		swap(data, pivotIndex, j);

		int k = partition(data, i - 1, j, data[j]);
		swap(data, k, j);
		if ((k - i) > 1)
			quickSort(data, i, k - 1);
		if ((j - k) > 1)
			quickSort(data, k + 1, j);

	}
	private  int partition(int[] data, int l, int r, int pivot) {
		do {
			while (data[++l] < pivot)
				;
			while ((r != 0) && data[--r] > pivot)
				;
			swap(data, l, r);
		} while (l < r);
		swap(data, l, r);
		return l;
	}

}