算法:高级排序2-快速排序

2018-08-22

高级排序2-快速排序

"排序-quickSort"

思路

0.每次执行前判断要排序的目标数组长度是否小于等于三，如果小那就不去执行快速排序，而是三个值交换位置即可。
1.每次选择三个值排序这三值是(第一个位置，中间位置，最后一个位置)。
2.选择中间位置作为枢纽，并把它的值交换到倒数第二个位置。
3.进行划分算法获得被划分的索引位置
3.1.左扫描从第二个位置开始把所有小于枢纽值的交换到扫描索引那里。
3.2.同时进行右扫描从倒数第三个位置(因为倒数第一个已经是大于枢纽，倒数第二个是枢纽)，所有大于枢纽值的交换到扫描索引位置。
3.3.一直扫描到左右索引交替时把枢纽值(倒数第二个位置的值)交换到左扫描索引位置，并返回划分位置。
4.获得划分位置后得到左右两个子数组，左边是0到划分索引-1位置，右边是划分索引+1到数组末端，继续从0步骤开始递归操作。

QuickSort.java 具体实现


public class QuickSort {
	static long array[]=new long[]{9,5,4,55,16,115,200,10,8,6,22,44,1,2,3,0,7,12,13,20,50,44,31};
	//交换索引值
	static void swap(int i,int j){
		long temp=array[i];
		array[i]=array[j];
		array[j]=temp;
	}
	static void print(){
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]+" ");
		}
	}
	//小于等于三时手动排序三个值
	static void manualSort(int left,int right,int size){
		if(size<=1){
			return;
		}else if(size==2){
			if(array[left]>array[right]){
				swap(left,right);
			}
		}else{
			if(array[left]>array[right]){
				swap(left,right);
			}
			if(array[left]>array[right-1]){
				swap(left,right-1);
			}
			if(array[right-1]>array[right]){
				swap(right-1,right);
			}
		}
	}
	//获取枢纽值作为划分，并把该枢纽值交换到倒数第二个位置
	static long getPivot(int left,int right){
		int center=(right+left)/2;
		if(array[left]>array[center]){
			swap(left,center);
		}
		if(array[left]>array[right]){
			swap(left,right);
		}
		if(array[center]>array[right]){
			swap(center,right);
		}
		long pivot=array[center];
		swap(center,right-1);
		return pivot;
	}
	//获取划分索引位置
	static int getPartitionIndex(int left,int right,long pivot){
		int leftScan=left;
		int rightScan=right-1;
		while(true){
			while(array[++leftScan]<pivot);
			
			while(array[--rightScan]>pivot);
			
			if(leftScan>=rightScan){
				break;
			}else{
				swap(leftScan,rightScan);
			}
		}
		swap(leftScan,right-1);
		return leftScan;
	}
	
	static void quickSort(int left,int right){
		int size=right-left+1;			//1
		if(size<=3){
			manualSort(left,right,size);
		}else{
			long pivot=getPivot(left,right);		//2
			int partitionIndex=getPartitionIndex(left,right,pivot);	//3
			quickSort(left,partitionIndex-1);		//4
			quickSort(partitionIndex+1,right);		
		}
	}
	
	public static void main(String[] args) {
		quickSort(0,array.length-1);
		
		print();//打印输出排序好的值
	}
}