排序（4）快速排序

快速排序的原理就是以递归的方式进行划分

 

划分：从数组中选择一个数作为枢纽，将数组划分成两部分，一部分小于枢纽，一部分大于枢纽

 

这里列举三种快速排序，第一种是基本的快速排序。第二种优化枢纽选择方式，第三种优化长度较小数组的排序为插入排序。

 

一、选择最右为中枢的快速排序

步骤：

1，选择最右一个为枢纽。

2，划分整个数组。数组变成：[比枢纽小，...，枢纽，比枢纽大，...]

3，比枢纽小的部分递归1,2。

4，比枢纽大的部分递归1,2。

 

 

 

public static int[] data = {3,7,8,0,9,5,4,1,6,2};
	
	/**
	 * 交换位置
	 * @param i
	 * @param j
	 */
	private static void swap(int i, int j){
		int tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}
	/**
	 * 递归
	 * @param leftIndex
	 * @param rightIndex
	 */
	private static void recursion(int leftIndex, int rightIndex){
		if(leftIndex >= rightIndex){
			return;
		}else{
			int pivot = data[rightIndex];	//以最右一个为枢纽
			int pivotIndex = partition(leftIndex, rightIndex, pivot);//以pivot为枢纽进行划分两份，pivotIndex是最终枢纽的位置
			recursion(leftIndex, pivotIndex - 1); //左侧再次递归划分
			recursion(pivotIndex + 1, rightIndex);//右侧再次递归划分
		}
	}
	/**
	 * 
	 * 划分
	 * 以最右一个为枢纽，对“最左” 到“最右-1”进行划分；
	 * 最终划分成两份，左份小于枢纽，右份大于枢纽，枢纽在中间
	 * @param leftIndex
	 * @param rightIndex
	 * @param pivot 枢纽
	 * @return 枢纽索引
	 */
	private static int partition(int leftIndex, int rightIndex, int pivot){
		/** 要划分区是leftIndex到rightIndex - 1。 */
		int left = leftIndex - 1; //要划分区域最左-1
		int right = rightIndex;   //要划分区域最右+1
		while(true){
			while(data[++left] < pivot); //从最左往右遍历，找到一个大的
			while(right > 0 && data[--right] > pivot); //从最右往左遍历，找到一个小的
			if(left >= right){
				break;
			}else{
				swap(left, right);
			}
		}
		swap(left, rightIndex);//枢纽归位
		return left;
	}
	
	public static void main(String[] args) {
		recursion(0, data.length - 1);
		System.out.println(Arrays.toString(data));
	}

 

 

 

 

二、三数据项取中为中枢的快速排序

这种快速排序优化了中枢的选取，但是同时失去了对长度<=3的数组快速排序的能力

步骤：

1，对数组的三个值：第一个值(first)、最后一个值(last)、中间一个值(center)，在对应的三个位置上排序，选中间一个为枢纽；最后枢纽和"最后-1"交换位置（即，将枢纽放在倒数第二个位置），数组变成：[三个较小......，枢纽，三个较大......]

2.1，<=3，手动排序

2.2，>3，划分整个数组。数组变成：[三个较小，比枢纽小......，枢纽，比枢纽大......，三个较大]

3，比枢纽小的部分递归1,2。

4，比枢纽大的部分1,2。

 

 

 

public static int[] data = {3,7,8,0,9,5,4,1,6,2};
	
	/**
	 * 交换位置
	 * @param i
	 * @param j
	 */
	private static void swap(int i, int j){
		int tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}
	
	
	/**
	 * 由于长度小于等于3无法进行快速排序。
	 * 当长度小于等于3时直接手动排序，推出递归
	 * 对<=3的数组手动排序
	 * @param left
	 * @param right
	 */
	private static void manualSort(int left, int right){
		int size = right - left + 1;
		if(size <= 1){
			return;
		}
		if(size == 2){
			if(data[left] > data[right]){
				swap(left, right);
			}
		}else{
			if(data[left] > data[right - 1]){
				swap(left, right - 1);
			}
			if(data[left] > data[right]){
				swap(left, right);
			}
			if(data[right - 1] > data[right]){
				swap(right - 1, right);
			}
		}
	}
	/**
	 * 选择枢纽
	 * @param left
	 * @param right
	 * @return
	 */
	private static int medianOf3(int left, int right){
		/** 从数组的开始，结束，和中间，对着在对应的三个位置上排序，枢纽放在right-1处，并返回枢纽 */
		int center = (right + left) / 2;
		if(data[left] > data[center]){
			swap(left, center);
		}
		if(data[left] > data[right]){
			swap(left, right);
		}
		if(data[center] > data[right]){
			swap(center, right);
		}
		/** 最后把居中的那个放在right-1处，作为枢纽 */
		swap(center, right - 1);//
		return data[right - 1];
	}
	/**
	 * 
	 * 划分
	 * @param leftIndex
	 * @param rightIndex
	 * @param pivot 
	 * @return 
	 */
	private static int partition(int leftIndex, int rightIndex, int pivot){
		/** 
		 * leftIndex经过medianOf3已经是小的了
		 * rightIndex经过medianOf3已经是大的了
		 * rightIndex - 1 是枢纽
		 * 要划分的区域是leftIndex+1到rightIndex-2。
		 */
		int left = leftIndex; 		  //要划分区域最左-1
		int right = rightIndex - 1;   //要划分区域最右+1
		while(true){
			while(data[++left] < pivot); //从最左往右遍历，找到一个大的
			while(data[--right] > pivot); //从最右往左遍历，找到一个小的
			if(left >= right){
				break;
			}else{
				swap(left, right);
			}
		}
		swap(left, rightIndex - 1);//枢纽归位
		return left; //返回枢纽位置
	}
	
	/**
	 * 递归
	 * @param leftIndex
	 * @param rightIndex
	 */
	private static void recursion(int leftIndex, int rightIndex){
		if(rightIndex - leftIndex + 1 <= 3){
			manualSort(leftIndex, rightIndex);//手动排序
		}else{
			int pivot = medianOf3(leftIndex, rightIndex);//选择枢纽 
			int pivotIndex = partition(leftIndex, rightIndex, pivot);//以pivot为枢纽进行划分两份，pivotIndex是最终枢纽的位置
			recursion(leftIndex, pivotIndex - 1); //左侧再次递归划分
			recursion(pivotIndex + 1, rightIndex);//右侧再次递归划分
		}
	}
	
	public static void main(String[] args) {
		recursion(0, data.length - 1);
		System.out.println(Arrays.toString(data));
	}

 

 

三、较小数组改用插入排序的快速排序

 将二中的手动排序改成插入排序，条件改成<10

public static int[] data = {3,7,8,0,9,5,4,1,6,2};
	
	/**
	 * 交换位置
	 * @param i
	 * @param j
	 */
	private static void swap(int i, int j){
		int tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}
	/**
	 * 选择枢纽
	 * @param left
	 * @param right
	 * @return
	 */
	private static int medianOf3(int left, int right){
		/** 从数组的开始，结束，和中间，对着在对应的三个位置上排序，枢纽放在right-1处，并返回枢纽 */
		int center = (right + left) / 2;
		if(data[left] > data[center]){
			swap(left, center);
		}
		if(data[left] > data[right]){
			swap(left, right);
		}
		if(data[center] > data[right]){
			swap(center, right);
		}
		/** 最后把居中的那个放在right-1处，作为枢纽 */
		swap(center, right - 1);//
		return data[right - 1];
	}
	/**
	 * 插入排序
	 * @param left
	 * @param right
	 */
	private static void insertionSort(int left, int right){
		for(int i = left+1; i <= right; i++){  
	        int temp = data[i];  
	        int j = i - 1;  
	        while(j >= left && data[j] >= temp){  
	            data[j + 1] = data[j];  
	            j--;  
	        }  
	        data[j + 1] = temp;  
	    }  
	}
	/**
	 * 
	 * 划分
	 * @param leftIndex
	 * @param rightIndex
	 * @param pivot 
	 * @return 
	 */
	private static int partition(int leftIndex, int rightIndex, int pivot){
		/** 
		 * leftIndex经过medianOf3已经是小的了
		 * rightIndex经过medianOf3已经是大的了
		 * rightIndex - 1 是枢纽
		 * 要划分的区域是leftIndex+1到rightIndex-2。
		 */
		int left = leftIndex; 		  //要划分区域最左-1
		int right = rightIndex - 1;   //要划分区域最右+1
		while(true){
			while(data[++left] < pivot); //从最左往右遍历，找到一个大的
			while(data[--right] > pivot); //从最右往左遍历，找到一个小的
			if(left >= right){
				break;
			}else{
				swap(left, right);
			}
		}
		swap(left, rightIndex - 1);//枢纽归位
		return left; //返回枢纽位置
	}
	
	/**
	 * 递归
	 * @param leftIndex
	 * @param rightIndex
	 */
	private static void recursion(int leftIndex, int rightIndex){
		if(rightIndex - leftIndex + 1 < 10){
			insertionSort(leftIndex, rightIndex);//插入排序
		}else{
			int pivot = medianOf3(leftIndex, rightIndex);//选择枢纽 
			int pivotIndex = partition(leftIndex, rightIndex, pivot);//以pivot为枢纽进行划分两份，pivotIndex是最终枢纽的位置
			recursion(leftIndex, pivotIndex - 1); //左侧再次递归划分
			recursion(pivotIndex + 1, rightIndex);//右侧再次递归划分
		}
	}
	
	public static void main(String[] args) {
		recursion(0, data.length - 1);
		System.out.println(Arrays.toString(data));
	}