快速排序

2020-03-30

快速排序

从序列中选择一个轴点元素，我们一般把0号位置的元素当成轴点元素
利用轴点元素，将序列分割成两个子序列
- 将小于轴点的元素放在轴点的左边
- 将大于轴点的元素放在轴点的右边
- 等于轴点的元素放在左边或者右边都可以
然后再对子序列进行上述的操作，直到不能再分割位置（即子序列中只剩下一个元素）

很明显，快速排序的本质就是：逐渐的将每一个元素都变成轴点元素，当然，也就排好序了。我们不必关心每一步是怎样进行的，即我们只用管第一次选择的轴点元素，然后进行递归调用就行。

快速排序中的end初始位置默认指向最后一位元素

这与我们之前在插入排序和归并排序中的不一样，当然，这是我们故意设计的。我们还是可以对[begin,end)位置元素进行快速排序，递归调用，只需要在开始的时候将end指针左移一位。 quick

我们构造[begin,end）位置的轴点元素，如上图所示。

首先我们先备份出begin位置的元素，以免被破坏
这时候我们选择从右边开始扫描，比较end位置元素与轴点元素大小如果end>pivot 此时只需要让end指针往左移一位，然后继续比较。
当出现end < pivot时，我们将end元素覆盖到begin位置，让begin指针往右移动一位。然后从左往右扫描
在最开始的时候，我们有介绍到，如果碰到与轴点元素相等的元素，我们可以不作处理。但是为了方便，我们需要做出调整。当碰到与轴点元素相等时，我们交换扫描方向.

快速排序与归并排序都有类似之处，即他们都是递归操作

public class QuickSort {
	
	
	
	
	/**
	 * 
	 * 对[begin,end)范围内的元素进行快速排序
	 */
	private void sort(int begin,int end,int arr[]) {
		if(end-begin<2) return ;
		//确定轴点位置
		int mid=pivotIndex(begin,end,arr);
		//对子序列进行快速排序，递归调用
		sort(begin,mid,arr);
		sort(mid+1,end,arr);
		
	}
	
	/**
	 * 
	 * 构造出[begin,end)范围的轴点元素
	 * @return 返回轴点元素的位置， 即当begin=end的位置
	 */
	private  int pivotIndex(int begin,int end,int arr[]) {
		//首先备份begin位置的元素
		
		int pivot=arr[begin];
		//由于此时end为最后一个元素的下一个位置，我们需要将end往前挪动一位
		end--;
		while(begin<end) {
			//从右往左
			while(begin<end) {
        //右边元素>轴点元素
				if(arr[end]>pivot) {
					end--;
				}
				else {
          //右边元素<=轴点元素
					arr[begin]=arr[end];
					begin++;
					break;
				}
			}
			//从左往右
			while(begin<end) {
				if(pivot>arr[begin]) {
					begin++;
				}else {
					arr[end]=arr[begin];
					end--;
					break;
				}
			}
		}
    //将轴点元素放在最终的位置
		arr[begin]=pivot;
		//此时begin=end ,返回轴点元素的位置
		return begin;
	}
	
	public static void main(String[] args) {
		int arr[]={1,6,2,8,19,23,54,21,17};
		
		new QuickSort().sort(0, arr.length, arr);
		
		for(Integer nums:arr) {
			System.out.println(nums);
		}
	}
}

代码如上所示，快速排序到这里就已经实现啦！！！

快速排序的时间复杂度

我们将确定轴点位置元素的过程理解为一次遍历操作，为O(n)的时间复杂度，那么与归并排序类似

T(n)=2*T(n/2)+O(n) 我们也可以推算出来快速排序的时间复杂度为O(nlogn).

当然，这是最好的情况下，即左右两边元素都是均匀的情况下，时间复杂度为O(nlogn)。

想象一下最坏的情况，即轴点元素极度不均匀的情况下，

T(n)=T(n-1)+O(n) 此时时间复杂度为O(n^2)。这样看来，我们并没有归并排序那样优秀，毕竟归并排序的平均时间复杂度都是O(nlogn)。

此时我们将提供一种快速排序的优化实现.

快速排序优化

为了降低最坏情况的出现概率，我们一般采取随机选择轴点元素

即我们在构造轴点元素时，随机选择一个元素与begin位置进行交换

public class QuickSort_优化 {

	
	/**
	 * 
	 * 对[begin,end)范围内的元素进行快速排序
	 */
	
	
	private void sort(int begin,int end,int arr[]) {
		if(end-begin<2) return ;
		//确定轴点位置
		int mid=pivotIndex(begin,end,arr);
		//对子序列进行快速排序，递归调用
		sort(begin,mid,arr);
		sort(mid+1,end,arr);
		
	}
	
	/**
	 * 
	 * 构造出[begin,end)范围的轴点元素
	 * @return 返回轴点元素的位置， 即当begin=end的位置
	 */
	private  int pivotIndex(int begin,int end,int arr[]) {
		//随机选择一个元素跟begin位置进行交换
		//由于math.random随机生成[0,1)的数，这样我们可以产生[begin,end)的数
		int index=begin+(int)Math.random()*(end-begin);
		//此时我们交换begin和index位置的元素
		int temp=arr[begin];
		arr[begin]=arr[index];
		arr[index]=temp;
		//首先备份begin唯一的元素
		int pivot=arr[begin];
		//由于此时end为最后一个元素的下一个位置，我们需要将end往前挪动一位
		end--;
		while(begin<end) {
			
			//从右往左
			while(begin<end) {
				if(arr[end]>pivot) {
					end--;
				}
				else {
					arr[begin]=arr[end];
					begin++;
					break;
				}
			}	
			//从左往右
			while(begin<end) {
				if(pivot>arr[begin]) {
					begin++;
				}else {
					arr[end]=arr[begin];
					end--;
					break;
				}	
			}	
		}
		arr[begin]=pivot;
		//此时begin=end ,返回轴点元素的位置
		return begin;	
	}
}

经过优化过后，会降低出现最坏情况的概率。至此，快速排序也就成功了！