java排序算法之快速排序

一、排序算法概述

常用的内部排序方法有：交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、基数排序（一关键字、多关键字）。

所需辅助空间最多：归并排序

所需辅助空间最少：堆排序

平均速度最快：快速排序

不稳定：快速排序，希尔排序，堆排序。

选择排序算法的依据：任何排序算法在数据量小的时候基本体现不出来差距。选择依据有 1.数据的规模；2.数据的类型；3.数据已有的顺序。

1.数据的规模:   当数据规模较小时，选择直接插入排序或冒泡排序。

2.数据的类型:   如全部是正整数，那么考虑使用桶排序为最优。

3.数据已有的顺序:   快排是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快排会浪费大量不必要的步骤。

数据量极小，而且已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理想。而不是所有情况。

二、快速排序时空复杂度

最好时间复杂度O(logn)，最差时间复杂度O(n²)，平均时间复杂度O(nlogn)，空间复杂度O(nlogn)~O(n)，是一种不稳定的排序算法。

三、快速排序原理

基于分治的思想，是冒泡排序的改进型。

四、快速排序思路

快速排序使用分治法策略来把一个序列分为两个子序列，基本步骤为：

1.首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法）；

2.分区过程：分别从数组的两端扫描数组(先右后左)，将把这个数大的数全部放到它的右边，小于或者等于它的数全放到它的左边；

3.递归的方式分别对左右子序列排序，直到各区间只有一个数，当前半部分和后半部分均有序时该数组就自然有序了。

五、快速排序举例说明

以一个数组作为示例，取区间第一个数为基准数。

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

初始时，i = 0; j = 9; temp = a[i] = 72

由于已经将 a[0] 中的数保存到 temp 中，可以理解成在数组 a[0] 上挖了个坑，可以将其它数据填充到这来。

从 j 开始向前找一个比 temp 小或等于 temp 的数。当 j = 8，符合条件，将 a[8] 挖出再填到上一个坑 a[0] 中。

a[0] = a[8]; i++; 这样一个坑 a[0] 就被搞定了，但又形成了一个新坑 a[8]，这怎么办了？简单，再找数字来填 a[8] 这个坑。这次从i开始向后找一个大于 temp 的数，当 i = 3，符合条件，将 a[3] 挖出再填到上一个坑中 a[8] = a[3]; j--;

数组变为：

0	1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

i = 3; j = 7; temp = 72

再重复上面的步骤，先从后向前找，再从前向后找。

从 j 开始向前找，当 j = 5，符合条件，将 a[5] 挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当 i = 5 时，由于 i==j 退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将 temp 填入 a[5]。

数组变为：

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

可以看出 a[5] 前面的数字都小于它，a[5] 后面的数字都大于它。因此再对 a[0…4] 和 a[6…9] 这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结

1．i = L; j = R; 将基准数挖出形成第一个坑 a[i]。

2．j-- 由后向前找比它小的数，找到后挖出此数填前一个坑 a[i] 中。

3．i++ 由前向后找比它大的数，找到后也挖出此数填到前一个坑 a[j] 中。

4．再重复执行 2，3 二步，直到 i==j，将基准数填入 a[i] 中。

六、快速排序基准数确认方法

在最好的情况下，每次我们进行一次分区，我们会把一个序列刚好分为几近相等的两个子序列，这个情况也我们每次递归调用的是时候也就刚好处理一半大小的子序列。这看起来其实就是一个完全二叉树，树的深度为 O(logn)，所以我们需要做 O(logn) 次嵌套调用。但是在同一层次结构的两个程序调用中，不会处理为原来数列的相同部分。因此，程序调用的每一层次结构总共全部需要 O(n) 的时间。所以这个算法在最好情况下的时间复杂度为 O(nlogn)。

事实上，我们总不能保证上面的理想情况。试想一下（最坏情况），假设每次分区后都出现子序列的长度一个为 1 一个为 n-1，那真是糟糕透顶。这一定会导致我们的表达式变成：T(n) = O(n) + T(1) + T(n-1) = O(n) + T(n-1)，这和插入排序和选择排序的关系式真是如出一辙，所以我们的最坏情况是 O(n²)。

上面对时间复杂度进行了简要分析，可见我们的时间复杂度和我们的基准数的选择密不可分。基准数选好了，把序列每次都能分为几近相等的两份，我们的快排就可以高效率完成排序任务；但一旦选择的基准数很差，快排的效率也会很差。基数一般有3种选择方式。

1、固定基准数
上面的那种算法，就是一种固定基准数的方式。如果输入的序列是随机的，处理时间还相对比较能接受。但如果数组已经有序，用上面的方式显然非常不好，因为每次划分都只能使待排序序列长度减一。这真是糟糕透了，快排沦为冒泡排序，时间复杂度为 O(n²)。因此，使用第一个元素作为基准数是非常糟糕的，我们应该立即放弃这种想法。

2、随机基准数
这是一种相对安全的策略。由于基准数的位置是随机的，那么产生的分割也不会总是出现劣质的分割。但在数组所有数字完全相等的时候，仍然会是最坏情况。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n）。所以随机化快速排序可以对于绝大多数输入数据达到 O(nlogn) 的期望时间复杂度。

3、三数取中
虽然随机基准数方法选取方式减少了出现不好分割的几率，但是最坏情况下还是 O(n²)。为了缓解这个尴尬的气氛，就引入了「三数取中」这样的基准数选取方式。

七、快速排序代码

public class QuickSort {
	private static int choiceNum = 0;
	public static void main(String[] args) {
//		int[] arr = { 9, 0, 5, 7, 1, 2, 4, 4, 5, 3 };
		int[] arr = { 1, 2, 4, 5, 7, 4, 5, 3, 9, 0 };
//		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
		System.out.println("排序前数组为："+Arrays.toString(arr));
		quickSort(arr);
		System.out.println("排序后的数组为："+Arrays.toString(arr));
		System.out.println("交换次数：" + choiceNum);
	}
	
	public static void quickSort(int[] a) {
		if (a!=null && a.length > 0) {
			quickSort(a, 0, a.length - 1);
		}
	}

	private static void quickSort(int[] a, int low, int high) {
		// 1,找到递归算法的出口
		if (low >= high) {
			return;
		}
		//三数取中
//		choiceMiddle(a, low, high);
		// 2, 存
		int i = low;
		int j = high;
		// 3,key
		int key = a[low];
		// 4，完成一趟排序
		while (i < j) {
			// 4.1 ，从右往左找到第一个小于key的数
			while (i < j && a[j] >= key) {
				--j;
			}
			// 当基准数大于了 a[j]，则填坑
            if (i < j) {
                a[i] = a[j];
                ++i;
            }
			// 4.2 从左往右找到第一个大于key的数
			while (i < j && a[i] <= key) {
				++i;
			}
			if (i < j) {
                a[j] = a[i];
                --j;
    			choiceNum++;
            }
		}
		a[i] = key;
		// 5, 对key左边的数快排
		quickSort(a, low, i - 1);
		// 6, 对key右边的数快排
		quickSort(a, i + 1, high);
	}
	
	/**
	 * 三数取中
	 * 
	 * @param a
	 * @param low
	 * @param high
	 */
	private static void choiceMiddle(int[] a, int low, int high) {
		if(a.length<4) {
			return;
		}
		// 1,采用三数取中法
		int middle = (low + high) / 2;
		// 保证左端较小
		if (a[low] > a[high]) {
			swap(a, low, high);
		}
		// 保证中间较小
		if (a[middle] > a[high]) {
			swap(a, middle, high);
		}
		// 保证中间最小，右边最大，左边为中值
		if (a[middle] > a[low]) {
			swap(a, low, middle);
		}
	}
	
	private static void swap(int[] a, int low, int high) {
		int temp = a[low];
		a[low] = a[high];
		a[high] = temp;
	}
}


// 排序前数组为：[1, 2, 4, 5, 7, 4, 5, 3, 9, 0]
// 排序后的数组为：[0, 1, 2, 3, 4, 4, 5, 5, 7, 9]
// 交换次数：4

// 若放开choiceMiddle(a, low, high);这行注释，采用三数取中法选取基数，交换次数只有2次。