Java数据结构和算法（九）——高级排序详解编程语言

package com.ys.sort; 
 
public class InsertSort { 
	public static int[] sort(int[] array){ 
		int j; 
		//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的 
		for(int i = 1 ; i < array.length ; i++){ 
			int tmp = array[i];//记录要插入的数据 
			j = i; 
			while(j > 0 && tmp < array[j-1]){//从已经排序的序列最右边的开始比较，找到比其小的数 
				array[j] = array[j-1];//向后挪动 
				j--; 
			} 
			array[j] = tmp;//存在比其小的数，插入 
		} 
		return array; 
	} 
		 
} 

//希尔排序 knuth 间隔序列 3h+1 
public static void shellKnuthSort(int[] array){ 
	System.out.println("原数组为"+Arrays.toString(array)); 
	int step = 1 ; 
	int len = array.length; 
	while(step <= len/3){ 
		step = step*3 + 1;//1,4,13,40...... 
	}	 
	while(step > 0){ 
		//分别对每个增量间隔进行排序 
		for(int i = step ; i < len ; i++){ 
			int temp = array[i]; 
			int j = i; 
			while(j > step-1 && temp <= array[j-step]){ 
				array[j] = array[j-step]; 
				j -= step; 
			} 
			array[j] = temp; 
		}//end for 
		System.out.println("间隔为"+step+"的排序结果为"+Arrays.toString(array)); 
		step = (step-1)/3; 
	}//end while(step>0) 
		 
	System.out.println("最终排序："+Arrays.toString(array)); 
} 

public static void main(String[] args) { 
	int[] array = {4,2,8,9,5,7,6,1,3,10}; 
	shellKnuthSort(array); 
} 

//希尔排序 间隔序列2h 
public static void shellSort(int[] array){ 
	System.out.println("原数组为"+Arrays.toString(array)); 
	int step; 
	int len = array.length; 
	for(step = len/2 ;step > 0 ; step /= 2){ 
		//分别对每个增量间隔进行排序 
		for(int i = step ; i < array.length ; i++){ 
			int j = i; 
			int temp = array[j]; 
			if(array[j] < array[j-step]){ 
				while(j-step >=0 && temp < array[j-step]){ 
					array[j] = array[j-step]; 
					j -= step; 
				} 
				array[j] = temp; 
			} 
		} 
		System.out.println("间隔为"+step+"的排序结果为"+Arrays.toString(array)); 
	} 
} 

package com.ys.high.sort; 
 
public class QuickSort { 
	 
	//数组array中下标为i和j位置的元素进行交换 
	private static void swap(int[] array , int i , int j){ 
		int temp = array[i]; 
		array[i] = array[j]; 
		array[j] = temp; 
	} 
	 
	private static void recQuickSort(int[] array,int left,int right){ 
		if(right <= left){ 
			return;//终止递归 
		}else{ 
			 
			int partition = partitionIt(array,left,right); 
			recQuickSort(array,left,partition-1);// 对上一轮排序(切分)时，基准元素左边的子数组进行递归 
			recQuickSort(array,partition+1,right);// 对上一轮排序(切分)时，基准元素右边的子数组进行递归 
		} 
	} 
	 
	private static int partitionIt(int[] array,int left,int right){ 
		//为什么 j加一个1，而i没有加1,是因为下面的循环判断是从--j和++i开始的. 
		//而基准元素选的array[left],即第一个元素，所以左游标从第二个元素开始比较 
		int i = left; 
		int j = right+1; 
		int pivot = array[left];// pivot 为选取的基准元素（头元素） 
		while(true){ 
			while(i<right && array[++i] < pivot){} 
			 
			while(j > 0 && array[--j] > pivot){} 
			 
			if(i >= j){// 左右游标相遇时候停止， 所以跳出外部while循环 
				break; 
			}else{ 
				swap(array, i, j);// 左右游标未相遇时停止, 交换各自所指元素，循环继续  
			} 
		} 
		swap(array, left, j);//基准元素和游标相遇时所指元素交换，为最后一次交换 
		return j;// 一趟排序完成， 返回基准元素位置(注意这里基准元素已经交换位置了) 
	} 
	 
	public static void sort(int[] array){ 
		recQuickSort(array, 0, array.length-1); 
	} 
	 
	//测试 
	public static void main(String[] args) { 
		//int[] array = {7,3,5,2,9,8,6,1,4,7}; 
		int[] array = {9,9,8,7,6,5,4,3,2,1}; 
		sort(array); 
		for(int i : array){ 
			System.out.print(i+" "); 
		} 
		//打印结果为：1 2 3 4 5 6 7 7 8 9  
	} 
}

	//取数组下标第一个数、中间的数、最后一个数的中间值 
	private static int medianOf3(int[] array,int left,int right){ 
		int center = (right-left)/2+left; 
		if(array[left] > array[right]){ //得到 array[left] < array[right] 
			swap(array, left, right); 
		} 
		if(array[center] > array[right]){ //得到 array[left] array[center] < array[right] 
			swap(array, center, right); 
		} 
		if(array[center] > array[left]){ //得到 array[center] <  array[left] < array[right] 
			swap(array, center, left); 
		} 
		 
		return array[left]; //array[left]的值已经被换成三数中的中位数， 将其返回 
	} 

	private static int partitionIt(int[] array,int left,int right){ 
		//为什么 j加一个1，而i没有加1,是因为下面的循环判断是从--j和++i开始的. 
		//而基准元素选的array[left],即第一个元素，所以左游标从第二个元素开始比较 
		int i = left; 
		int j = right+1; 
		int pivot = array[left];// pivot 为选取的基准元素（头元素） 
		 
		int size = right - left + 1; 
		if(size >= 3){ 
			pivot = medianOf3(array, left, right); //数组范围大于3，基准元素选择中间值。 
		} 
		while(true){ 
			while(i<right && array[++i] < pivot){} 
			 
			while(j > 0 && array[--j] > pivot){} 
			 
			if(i >= j){// 左右游标相遇时候停止， 所以跳出外部while循环 
				break; 
			}else{ 
				swap(array, i, j);// 左右游标未相遇时停止, 交换各自所指元素，循环继续  
			} 
		} 
		swap(array, left, j);//基准元素和游标相遇时所指元素交换，为最后一次交换 
		return j;// 一趟排序完成， 返回基准元素位置(注意这里基准元素已经交换位置了) 
	} 

	//插入排序 
	private static void insertSort(int[] array){ 
		for(int i = 1 ; i < array.length ; i++){ 
			int temp = array[i]; 
			int j = i; 
			while(j > 0 && array[j-1] > temp){ 
				array[j] = array[j-1]; 
				j--; 
			} 
			array[j] = temp; 
		} 
	}