快速排序

一、什么是快速排序

     快速排序同冒泡排序一样，是一种交换排序，通过元素之间的比较和交换达到排序目的。不同的是，冒泡排序每一轮只把一个元素（该轮最大/最小）冒泡到最右端；而快速排序每一轮则是选一个基准元素（ pivot），并让其它比基准元素小的数通过交换放在基准元素左端，而比基准元素大的数则放在基准元素的右端，从而把待排序的数列拆分成两部分，这就是分治法的典型应用。然后不断重复这个过程（递归），待排序的序列就变成了有序序列。

二、基准元素的选择

    通过上述对快速排序思想的了解，可以发现：基准元素的选择很重要。一般情况下，基准元素最简单的就是选择序列的第一个元素，但是如果待排序的序列是一个逆序序列，期望排序成一个顺序序列，每一轮排序选择第一个元素作为基准元素，会出现什么情况呢？如下图：

从上图中可以看出：在这种情况下，每一轮排序只会确定基准元素的位置（第一个元素/最后一个元素），而没有把序列分成较为均匀的两部分，在这种情况下，快速排序需要进行N轮，发挥不了分治法的优势，排序的时间复杂度将会是O(n²)。

要解决上述问题，基准元素的选取我们可以不选取第一个元素，而是采用随机选取基准元素。但是，即便是这样做，也有很小的几率选到数列的最大/最小元素作为基准元素，同样会影响分治的效果，所以快速排序平均时间复杂度是nlog(n)，最坏时间复杂度是O(n²)。

三、快速排序的两种实现方法

     看到这里，我们讨论了基准元素的选择，但是没有讨论快速排序具体的分治算法。现在已有的针对快速排序的分治算法，比较典型的有两种，一种是挖坑法，另一种是指针交换法。下面我们来一一学习这两种算法。

3.1 挖坑法

     什么是挖坑法呢？顾名思义，每一次我们先挖好一个“坑”，然后寻找符合条件的元素填入坑中，填坑的元素的位置又变成新的坑，重复这个过程（挖坑—填坑—挖坑），直到寻找元素的左右指针相交，相交的位置填入基准元素的值，一轮排序结束。用文字说明有些地方说的不够详细，而且有些抽象，下面用图来描述这个过程：

给定原始数列如下，要求从小到大排序：

首先，选择基准元素（这里选第一个元素），记住基准元素的位置index，值pivot，这个位置就是“坑”的位置，然后设置两个指针left和right，分别指向序列的左右两端的端点：

接下来，移动right指针（坑在最左边，则先移动right指针）。如果找到的元素比privot大，则right指针继续向左移动。直到找到小于等于pivot的元素，right指针就停止移动，并把right指针所指的元素填入“坑”中，left指针向右移一位。并且，坑的指针指向right指针所指元素（挖一个新的“坑”）。

在这里，1<4，1填入坑，index指向right所指元素，同时left指针向右移一位：

此时，left左边绿色的区域代表着小于或等于基准元素的区域。

接下来，切换到left指针进行比较。如果left指针所指的元素小于等于pivot，那么left指针继续右移，直到找到一个比prvot大的元素，left指针停止移动，并把这个元素填入坑中，同时right指针左移一位，index指向left指针。

在这里，7>4，所以把7填入坑（index的位置），这时候元素7本来的位置成为了新的坑（index指向left），同时，right向左移动一位：

此时，right右边橙色的区域代表着大于基准元素的区域。

下面按照上述的思路继续排序：

 

8>4，元素位置不变，right左移：

 

2<4，用2来填坑，left右移，切换到left：

 

6>4，用6来填坑，right左移，切换到right：

 

3<4，用3来填坑，left右移，切换到left：

5>4，用5来填坑，right右移。这时候left和right重合在了同一位置：

这时候，把之前的pivot元素，也就是4放到index的位置。此时数列左边的元素都小于或等于4，数列右边的元素都大于4，这一轮交换终告结束。

一轮排序结束，重复上述过程，完成排序。

3.1.1 挖坑法代码

   /**
	 * 
	 * @param arr 待排序的序列
	 * @param left 左指针的位置
	 * @param right 右指针的位置
	 */
	public static void qucik_sort(int[] arr,int left,int right) {
		//递归出口
		if(left >= right) return;
		
		//得到基准元素的位置
		int pivot_index = partition_digHole(arr,left,right);
		
		//对基准元素的左侧待排序序列进行排序
		qucik_sort(arr,left,pivot_index - 1);
		
		//对基准元素的右侧待排序序列进行排序
		qucik_sort(arr,pivot_index + 1,right);
	}
	
	/**
	 * @param arr  待排序的序列
	 * @param left 左指针的位置
	 * @param right 右指针的位置
	 * @return 一轮交换之后基准元素所在位置
	 */
	public static int partition_digHole(int[] arr,int left,int right) {
		int pivot = arr[left];
		int index = left;
		while(right > left) {
			
			//右指针左移，直到找到小于或等于基准元素的元素
			while(right > left) {
				if(arr[right] <= pivot) {
					arr[index] = arr[right];//把找到的元素填坑
					index = right;//坑指针指向右指针所指位置
					left++;//左指针向右移动一位
					break;
				}
				right--;//右指针左移
			}
			
			//左指针右移，直到找到大于基准元素的元素
			while(right > left) {
				if(arr[left] > pivot) {
					arr[index] = arr[left];//把找到的元素填坑
					index = left;//坑指针指向左指针所指位置
					right--;//右指针向左移动一位
					break;
				}
				left++;
			}
		}
		
		//左右指针重合，跳出循环，重合的位置即为基础元素的位置。本轮排序结束
		arr[index] = pivot;
		return index;
	}

3.2 指针交换法

     指针交换法，相对于挖坑法来说，更容易理解，并且元素交换的次数更少：第一次循环，从right指针开始，如果right指针所指向的元素大于pivot，那么right指针左移，直到right指针指向的元素小于或等于pivot，right指针停止移动；切换到left指针，如果left指针指向的元素小于或等于pivot，left指针左移，直到left指针指向的元素大于pivot，left指针停止移动。然后把left和right指针指向的元素互换，并进入第二次循环，循环往复，直到left指针和right指针重合，再把重合的位置的元素与第一个元素互换（因为这里选取的基准元素是序列的第一个元素，所以与第一个元素互换），本轮排序结束

给定原始数列如下，要求从小到大排序：

 

选定第一个元素为基准元素，取出基准元素的值保存在Pivot中，并且设置两个指针left和right，指向数列的最左和最右两个元素：

在当前数列中，1<4，所以right指针直接停止移动，换到left指针，进行下一步行动：

由于left指针一开始指向的是基准元素，判断肯定相等，所以left右移一位。由于7 > 4，left指针在元素7的位置停下。这时候，我们让left和right指向的元素进行交换：

接下来，我们进入第二次循环，重新切换到right向左移动。right先移动到8，8>4，继续左移。由于2<4，停止在2的位置：

切换到left，6>4，停止在6的位置：

元素6和2交换：

进入第三次循环，right移动到元素3停止，left移动到元素5停止：

元素5和3交换：

进入第四次循环，right移动到元素3停止，这时候请注意，left和right指针已经重合在了一起：

当left和right指针重合之时，我们让Pivot元素和left与right重合点的元素进行交换。此时数列左边的元素都小于或等于4，数列右边的元素都大于4，这一轮交换结束：

一轮排序之后，重复上述过程，完成排序。

3.2.1 指针交换法代码

   /**
	 * 
	 * @param arr 待排序的序列
	 * @param left 左指针的位置
	 * @param right 右指针的位置
	 */
	public static void qucik_sort(int[] arr,int left,int right) {
		//递归出口
		if(left >= right) return;
		
		//得到基准元素的位置
		int pivot_index = partition_needleExc(arr,left,right);
		
		//对基准元素的左侧待排序序列进行排序
		qucik_sort(arr,left,pivot_index - 1);
		
		//对基准元素的右侧待排序序列进行排序
		qucik_sort(arr,pivot_index + 1,right);
	}


   /**
	 * 
	 * @param arr 待排序的序列
	 * @param left 左指针的位置
	 * @param right 右指针的位置
	 * @return  一轮排序之后基准元素所在位置
	 */
	public static int partition_needleExc(int[] arr,int left,int right) {
		//基准元素所在位置
		int index = left;
		
		//基准元素的值
		int pivot = arr[left];
		
		//当左、右指针相交则一轮排序结束
		while(right > left) {
			
			//右指针左移，直到找到小于或等于pivot的元素，右指针停止移动
			while(right > left && arr[right] > pivot) {
				right--;
			}
			
			//左指针右移，直到找到大于pivot的元素，左指针停止移动
			while(right > left && arr[left] <= pivot) {
				left++;
			}
			
			//若左右指针还未相交，则交换此时左右指针所指元素
			if(right > left) {
				int temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
			}
		}
		
		//左右指针相交，本轮排序结束，左右指针重合的位置即为基准元素所在的位置
		int temp = arr[left];
		arr[left] = arr[index];
		arr[index] = temp;
		
		return left;
	}

四、注意点

 1、为什么挖坑法是从右指针开始移动？

答：因为本文实现的挖坑法，基准元素选取的是左指针指向的元素，即最开始挖的坑是左指针指向的元素，所以需要从右指针开始寻找元素填入第一个坑中。

2、为什么指针交换法也是从右指针开始移动？

答：也是因为选取的基准元素是左指针指向的元素（即第一个元素），指针交换法最后会把左右指针重合位置的元素和基准元素作交换，如果从左指针开始移动，那么会出现左右指针重合时所指向的元素比基准元素大的情况，与基准元素作交换以后，基准元素左边会出现比它大的元素，这显然是不可以的，所以我们要从右指针开始移动，避免出现上述情况。

五、快速排序的时间复杂度和稳定性分析

通过上面对面快速排序的分析，以及对快速排序进行代码实现，可以看出：

快速排序最好情况下，时间复杂度为：O(nlogn)；

快速排序最坏情况下，时间复杂度为：O(n²)；

快速排序的平均时间复杂度为：O(nlogn)；

快速排序的稳定性：不稳定；