算法-快速排序(1)

快排算法的特点

实用性强。

很多实际的项目中使用了快排算法。但通常对算法都进行了调整（tuning），比如Java.util.Arrays类中的sort函数就使用了快排算法，但使用了双参考值（Dual-Pivot Quicksort）等一些改进措施。由于快排算法为递归算法，可以用循环代替递归函数调用，改进性能。 

可以将数组中的数据直接交换位置实现排序，所以理论上不需要额外的空间。

时间复杂度

平均情况：O(nlgn)

最坏情况：O(n*n)，发生在当数据已经是排序状态时

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）

算法步骤：

1 从数列中挑出一个元素，称为 “基准”（pivot），

2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

（图片从网上下载的，图中的基元选择的是最后一个元素，代码实现选第一个元素）

 

public class QuickSort {

	public static void main(String[] args) {
		int arr[] = { 10, 1, 56, 45, 2, 9, 33, 10 };
		quickSort(arr, 0, arr.length - 1);
		for (int a : arr) {
			System.out.println(a);
		}

	}

	private static void quickSort(int[] array, int start, int end) {
		if (start > end) {
			return;
		}
		// 初始化保存基元，i,j
		int key = array[start];
		int i = start, j;
		for (j = start + 1; j <= end; j++) {

			// 如果此处元素小于基元，则把此元素和i+1处元素交换，并将i加1，如大于或等于基元则继续循环
			if (array[j] < key) {
				int temp = array[j];
				array[j] = array[i + 1];
				array[i + 1] = temp;
				i++;
			}

		}
		// 交换i处元素和基元
		array[start] = array[i];
		array[i] = key;
		// 递归调用
		quickSort(array, start, i - 1);
		quickSort(array, i + 1, end);
	}
}