快速排序

快速排序的原理：

选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。

一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。

找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。

直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。

接着分别比较左右两边的序列，重复上述的循环。

实现代码：

/**
 * 快速排序<br/>
 * <ul>
 * <li>从数列中挑出一个元素，称为“基准”</li>
 * <li>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，
 * 该基准是它的最后位置。这个称为分割（partition）操作。</li>
 * <li>递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。</li>
 * </ul>
 * 
 * @param numbers 待排序数组
 * @param low 数组最小下标
 * @param high 数组最大下标
 */
public void quickSort(int[] numbers, int low, int high) {
	int start = low;
        int end = high;
        int key = numbers[low];

	while (end > start) {
		// 从后往前比较
		while (end > start && numbers[end] >= key) // 如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
			end--;
		if (numbers[end] <= key) {
			int temp = numbers[end];
			numbers[end] = numbers[start];
			numbers[start] = temp;
		}
		// 从前往后比较
		while (end > start && numbers[start] <= key)// 如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
			start++;
		if (numbers[start] >= key) {
			int temp = numbers[start];
			numbers[start] = numbers[end];
			numbers[end] = temp;
		}
		// 此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
	}
	// 递归
	if (start > low) {
		// 左边序列。第一个索引位置到关键值索引-1
		quickSort(numbers, low, start - 1);
	}
	if (end < high) {
		// 右边序列。从关键值索引+1到最后一个
		quickSort(numbers, end + 1, high);
	}
}

在序列中元素很少时，快速排序效率将比较低，不如插入排序，因此一般在序列中元素很少时使用插入排序，这样可以提高整体效率。