排序算法二（归并排序、快速排序、希尔排序）


作者：xcbeyond
疯狂源自梦想，技术成就辉煌！微信公众号：《程序猿技术大咖》号主，专注后端开发多年，拥有丰富的研发经验，乐于技术输出、分享，现阶段从事微服务架构项目的研发工作，涉及架构设计、技术选型、业务研发等工作。对于Java、微服务、数据库、Docker有深入了解，并有大量的调优经验。 






   
一、归并排序：（MergeSort）

   将数组分成两半，先对每一半分别排序，然后把有序的两半归并（merge）为一个有序的数组。
1

如：【38,16,27,39,12,27】

Java代码：

package 排序算法;
 
import java.util.Arrays;
 
/**
 * 归并排序
 * @author xcbeyond
 * @date 2012-6-21 上午11:33:15
 */
public class mergeSort {
	public static void main(String[] args) {
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		mergeSort(a,0,a.length-1);
		
		System.out.println(Arrays.toString(a));
	}
	/**
	 * 归并排序
	 * @param array
	 * @param first 数组起始下标
	 * @param last 数组末尾下标
	 */
	public static void mergeSort(int[] array,int first,int last) {
		if(first<last) {
			int mid = (first+last)/2;
			mergeSort(array,first,mid);
			mergeSort(array,mid+1,last);
			merge(array,first,mid,last);
		}
	}
	private static void merge(int[] array, int first, int mid, int last) {
		int[] tempArray = new int[array.length];
		int first1 = first;
		int last1 = mid;
		int first2 = mid + 1;
		int last2 = last;
		
		int index  = first;
		
		while((first1<=last1) && (first2 <= last2)) {
			if(array[first1]<array[first2]) {
				tempArray[index] = array[first1];
				first1 ++ ;
			}
			else {
				tempArray[index] = array[first2];
				first2 ++ ;
			}
			index++;
		}
		
		while(first1<=last1) {
			tempArray[index] = array[first1];
			first1++;
			index++;
		}
		while(first2<=last2) {
			tempArray[index] = array[first2];
			first2++;
			index++;
		}
		
		for (index = first; index <= last; index++) {
			array[index] = tempArray[index];
		}
		
	}
	
}

二、快速排序：（quickSort）

  在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
1

排序过程：
初始关键字 ［49 38 65 97 76 13 27 49］
一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］
二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］
三趟排序之后 13 27 38 49 49 ［65］76 97
最后的排序结果 13 27 38 49 49 65 76 97

程序代码：

package 排序算法;
 
import java.util.Arrays;
 
public class QuickSort {
	public static void main(String[] args) {
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		quickSort(a,0,a.length-1);
		
		System.out.println(Arrays.toString(a));
	}
	/**
	 * 快速排序
	 * @param array
	 * @param first
	 * @param last
	 */
	public static void quickSort(int[] array,int first,int last) {
		int pIndex ;
		if(first<last) {
			pIndex = partition(array,first,last);//“基准”值位置
			
			quickSort(array,first,pIndex-1);
			quickSort(array,pIndex+1,last);
		}
	}
	/**
	 * 一次划分，找到基准的位置
	 * @param array
	 * @param first
	 * @param last
	 * @return  基准的位置
	 */
	private static int partition(int[] array,int first,int last) {
		int p =array[first];
		
		while(first<last) {
			while(first<last && array[last]>=p)
				last--;
			array[first] = array[last];
			
			while(first<last && array[first]<=p)
				first++;
			array[last] = array[first];
		}
		array[first] = p;
		return first;
	}
	
}

三、希尔排序：（shellSort）

  先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。
1

排序过程：

待排序序列：39，80，76，41，13，29，50，78，30，11，100，7，41，86

取步长d分别为5，3，1

d=5 39，80，76，41，13，29，50，78，30，11，100，7，41，86

        |-------------------------------|-----------------------------|

                |------------------------------|------------------------------|

                        |-----------------------------|------------------------------|

                                 |----------------------------|------------------------------|

                                          |-------------------------------|

各自序列分别为：｛39，29，100｝｛80，50，7｝｛76，78，41｝｛41，30，86｝｛13，11｝

对每个自序列进行直接插入排序，顺序调入各个自序列对应排序元素，得到第一趟排序结果：

d=3 29，7，41，30，11，39，50，76，41，13，100，80，78，86

         |-----------------|-----------------|-----------------|------------------|

                 |----------------|------------------|-----------------|------------------|

                        |------------------|-----------------|-------------------|
1
2
3
4
5

各自序列分别为：｛29，30，50，13，78｝｛7，11，76，100，86｝｛41，39，41，80｝。对每个自序列进行直接插入排序，顺序调入各个自序列对应排序元素，得到第二趟排序结果：

d=1 13，7，39，29，11，41，30，76，41，50，86，80，78，100

此时，序列基本“有序”，对其直接进行插入排序，得到最终结果：

7，11，13，29，30，39，41，41，50，76，78，80，86，100

Java程序代码：

package 排序算法;
 
import java.util.Arrays;
 
/**
 * 希尔排序：有步长的直接插入排序
 * @author xcbeyond
 * @date 2012-7-8 上午11:27:32
 */
public class ShellSort {
	public static void main(String[] args) {
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		shellSort(a);
		
		System.out.println(Arrays.toString(a));
	}
	
	public static void shellSort(int[] array){
		int temp; 
		int d =array.length;//步长
		while(true){ 
			d= d/2; 
		
			for(int i=0;i<d;i++){ 
				for(int j=i+d;j<array.length;j+=d){ 
					int k=j-d; 
					temp=array[j]; 
					for(;k>=0&&temp<array[k];k-=d){ 
						array[k+d]=array[k]; 
					} 
					array[k+d]=temp; 
				} 
			} 
		if(d==1) 
			break; 
 
		}
	}

      }