快速排序算法

Quick sort algorithm

/**
 * 快速排序算法 java实现
 * @param arr 待排序数组
 * @author youqi
 */
public void quickSort(int[] arr) {
	if (arr == null || arr.length < 1)
		return;
	quickSort(arr, 0, arr.length - 1);
}

private void quickSort(int[] arr, int start, int end) {
	//记录初始状态
	int i = start;
	int j = end;

	//选择第一个为key
	int key = arr[start];

	while (start < end) {
		//从后向前搜索比key小的数
		while (arr[end] >= key && end > start)
			end--;
		
		//避免不必要的交换
		if (arr[end] < key)
			swap(arr, start, end);

		//从前往后搜索比key大的数
		while (arr[start] <= key && start < end)
			start++;

		if (arr[start] > key)
			swap(arr, start, end);
	}
	
	//start > i 说明start以前还存在待排序的元素
	if (start > i)
		quickSort(arr, i, start - 1);

	//end < j 说明end以后还有待排序的元素
	if (end < j)
		quickSort(arr, end + 1, j);

}

private void swap(int[] arr, int a, int b) {
	arr[a] = arr[a] ^ arr[b];
	arr[b] = arr[a] ^ arr[b];
	arr[a] = arr[a] ^ arr[b];
}