排序算法二（歸并排序、快速排序、希爾排序）


作者：xcbeyond
瘋狂源自夢(mèng)想，技術(shù)成就輝煌！微信公眾號(hào)：《程序猿技術(shù)大咖》號(hào)主，專(zhuān)注后端開(kāi)發(fā)多年，擁有豐富的研發(fā)經(jīng)驗(yàn)，樂(lè)于技術(shù)輸出、分享，現(xiàn)階段從事微服務(wù)架構(gòu)項(xiàng)目的研發(fā)工作，涉及架構(gòu)設(shè)計(jì)、技術(shù)選型、業(yè)務(wù)研發(fā)等工作。對(duì)于Java、微服務(wù)、數(shù)據(jù)庫(kù)、Docker有深入了解，并有大量的調(diào)優(yōu)經(jīng)驗(yàn)。 






   
一、歸并排序：（MergeSort） 

   將數(shù)組分成兩半，先對(duì)每一半分別排序，然后把有序的兩半歸并（merge）為一個(gè)有序的數(shù)組。

  • 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 數(shù)組起始下標(biāo)
	 * @param last 數(shù)組末尾下標(biāo)
	 */
	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）

  在當(dāng)前無(wú)序區(qū)R[1..H]中任取一個(gè)數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無(wú)序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無(wú)序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當(dāng)R[1..I-1]和R[I+1..H]均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過(guò)程，直至所有無(wú)序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?

  • 1





排序過(guò)程：
初始關(guān)鍵字 ［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
最后的排序結(jié)果 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);//“基準(zhǔn)”值位置
			
			quickSort(array,first,pIndex-1);
			quickSort(array,pIndex+1,last);
		}
	}
	/**
	 * 一次劃分，找到基準(zhǔn)的位置
	 * @param array
	 * @param first
	 * @param last
	 * @return  基準(zhǔn)的位置
	 */
	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）

  先將要排序的一組數(shù)按某個(gè)增量d（n/2,n為要排序數(shù)的個(gè)數(shù)）分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行直接插入排序，然后再用一個(gè)較小的增量（d/2）對(duì)它進(jìn)行分組，在每組中再進(jìn)行直接插入排序。當(dāng)增量減到1時(shí)，進(jìn)行直接插入排序后，排序完成。

  • 1

排序過(guò)程：

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

取步長(zhǎng)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｝

對(duì)每個(gè)自序列進(jìn)行直接插入排序，順序調(diào)入各個(gè)自序列對(duì)應(yīng)排序元素，得到第一趟排序結(jié)果：

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｝。對(duì)每個(gè)自序列進(jìn)行直接插入排序，順序調(diào)入各個(gè)自序列對(duì)應(yīng)排序元素，得到第二趟排序結(jié)果：

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

此時(shí)，序列基本“有序”，對(duì)其直接進(jìn)行插入排序，得到最終結(jié)果：

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

Java程序代碼：

package 排序算法;
 
import java.util.Arrays;
 
/**
 * 希爾排序：有步長(zhǎng)的直接插入排序
 * @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;//步長(zhǎng)
		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; 
 
		}
	}

      }