Java快速排序-学习笔记1

效率可观的快速排序实现代码：

 

 

import java.util.Arrays;

public class QuickSort2 {

	public static void main(String[] args) {

		int size = 5000;
		int[] array = new int[size];
		int[] array2 = new int[size];
		for (int j = 0; j < size; j++) {
			int r = (int) (Math.random() * 1000);
			array[j] = r;
			array2[j] = r;
		}

		long s1 = System.currentTimeMillis();
		Arrays.sort(array);
		for (int i : array) {
			System.out.print(i + "\t");
		}
		long e1 = System.currentTimeMillis();

		System.out.println("");

		long s2 = System.currentTimeMillis();
		QuickSort2.quickSort(array2, 0, array2.length - 1);
		for (int i : array2) {
			System.out.print(i + "\t");
		}
		long e2 = System.currentTimeMillis();

		System.out.println("");
		System.out.println((e1 - s1) + "-----" + (e2 - s2));
	}

	public static int partition(int[] arr, int low, int high) {
		int key = arr[low];
		while (low < high) {
			while (low < high && arr[high] >= key) {
				--high;// 从右向左搜索
			}
			arr[low] = arr[high];

			while (low < high && arr[low] <= key) {
				++low;// 从左向右搜索
			}
			arr[high] = arr[low];
		}
		arr[low] = key;
		return low;
	}

	public static void quickSort(int[] arr, int start, int end) {
		if (start <= end - 1) {
			int loc = partition(arr, start, end);// 对原数据进行一次划分
			quickSort(arr, start, loc - 1);// 从右往左搜索排序
			quickSort(arr, loc + 1, end);// 从左往右搜索排序
		}
	}
}