1、基本概念介紹

?

(1) 如果待排序列中有兩個(gè)相同的關(guān)鍵字 Ki = Kj，其順序是Ki在Kj之前。如果經(jīng)過排序之后，Ki 和 Kj的順序顛倒了，則說明這個(gè)排序方法是 不穩(wěn)定 的。否則則是 穩(wěn)定 排序。

?

(2) 在內(nèi)存中就可以完成的排序過程，稱為 內(nèi)部排序 。如果待排數(shù)據(jù)量很大，內(nèi)存不夠容納全部數(shù)據(jù)，在排序過程中必須對外存進(jìn)行訪問，則叫做 外部排序 。

???? 實(shí)際上，由于數(shù)據(jù)量級別不同。排序的方法會有很大的改變，思考排序效率的角度也不一樣。這個(gè)專題系列未經(jīng)特殊注明，都屬于內(nèi)部排序方法。

?

?

2、直接插入排序? O(N^2)

?

????? 將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而得到一個(gè)新的，記錄數(shù)增1的有序表。下面通過一個(gè)例子來說明這個(gè)排序流程：

???? ? ? ? ? ? ? ? ? ? ?? 待排序列：?? 49， 38 ， 65 ， 97， 76 ， 13， 27 ，49

?

??????????????????????????? 插入49：?? 49

??????????????????????????? 插入38：?? 38， 49

??????????????????????????? 插入65：?? 38， 49，? 65

??????????????????????????? 插入97：?? 38， 49，? 65，? 97

??????????????????????????? 插入76：?? 38， 49，? 65，? 76，? 97

??????????????????????????? 插入13：?? 13， 38，? 49，? 65，? 76，? 97

??????????????????????????? 插入27：?? 13， 27，? 38，? 49，? 65，? 76， 97

??????????????????????????? 插入49：?? 13， 27，? 38，? 49，? 49，? 65， 76， 97

    #include<iostream.h>
/******************************
 * 直接插入排序 Straight Insertion Sort *
 ******************************/
class SISortion{
public:
	//遞增穩(wěn)定排序
	static void inc_sort(int keys[], int size);
};
void SISortion:: inc_sort(int keys[], int size){
    //記錄當(dāng)前要插入的key
    int post_key;
    //從第二個(gè)數(shù)據(jù)開始
    for(int i=1;i<size;i++){
        post_key=keys[i];
	     int j;
	     //將比post_key要大的前面所有的key依次后移一位
             for(j=i-1;j>=0;j--){
                  if(post_key<keys[j])
		      keys[j+1]=keys[j];
		  else
		      break;
	     }
	     //將post_key插入到合適位置
	     keys[j+1]=post_key;
      }
      //打印排序結(jié)果
      for(int k=0;k<size;k++)
	    cout<<keys[k]<<" ";
      cout<<endl;
}
//Test SISortion
void main(){
	int raw[]={49,38,65,97,76,13,27,49};
	int size=sizeof(raw)/sizeof(int);
	SISortion::inc_sort(raw,size);
}
  

很顯然，直接插入排序算法的 時(shí)間復(fù)雜度為O(N^2) 。但是不需要額外的存儲空間，因此 空間復(fù)雜度為O(1) 。而且直接插入排序是 穩(wěn)定 的。

?

3、折半插入排序? O(N^2)

?

折半插入排序和直接插入排序的不同點(diǎn)在“查找”上。在有序關(guān)鍵字序列中，每次插入的關(guān)鍵字采用折半查找的方法來定位。雖然折半查找的時(shí)間復(fù)雜度為O(logN)，但定位后循環(huán)數(shù)據(jù)后移仍然要花費(fèi)O(N)的代價(jià)。因此時(shí)間 復(fù)雜度仍然是O(N^2)，空間復(fù)雜度為O(1)，排序是穩(wěn)定的。

    #include<iostream.h>
/******************************
?* 折半插入排序 Binary Insertion Sort   *
 ******************************/
class BISortion{
public:
	static void inc_sort(int keys[],int size);
};

void BISortion :: inc_sort(int keys[],int size){
	
	int post_key;
	for(int i=1;i<size;i++){
		post_key=keys[i];
		//折半查找
		int low=0,high=i-1;
		while(low<=high){
			int middle=(low+high)/2;
			if(post_key<keys[middle])
				high=middle-1;
			else low=middle+1;
		}
		//移動位置
		for(int j=i-1;j>=high+1;j--)
			keys[j+1]=keys[j];
		keys[high+1]=post_key;
	}

	for(int k=0;k<size;k++){
		cout<<keys[k]<<" ";
	}
	cout<<endl;

}
//Test BISortion
void main(){
	int keys[]={49,38,65,97,76,13,27,49};
	int size=sizeof(keys)/sizeof(int);
	BISortion::inc_sort(keys,size);
}
  

?

4、希爾排序(N*logN)

?

? ?? 希爾排序(Shell's Sort)又稱縮小增量排序(Diminishing Increment Sort)，它也是一種插入排序，但是在時(shí)間效率上比前面兩種有較大的改進(jìn)。

?

???? 對本身就是“正序”的關(guān)鍵字序列，直接插入排序的時(shí)間復(fù)雜度將降低到O(n)。由此可以設(shè)想，對"基本有序"的序列進(jìn)行直接插入排序，效率將大大提高。希爾排序方法就是基于這個(gè)思想提出來的，其基本思想就是：先將整個(gè)待排序列分割成若干個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，在對全體記錄進(jìn)行一次直接插入排序。

?

??? 我們用下圖的例子來看看希爾排序

?????????

? ?? 很明顯，希爾排序?qū)γ恳惶嗽隽孔有蛄卸际且环N直接插入排序。但是每一趟排序中記錄關(guān)鍵字都是和同一子序列中前一個(gè)記錄的關(guān)鍵字進(jìn)行比較(子序列相鄰關(guān)鍵字之間的位置相差一個(gè)增量)，因此關(guān)鍵字較小的記錄不是一步一步向前挪動，而是根據(jù)增量大小跳躍式的前進(jìn)。當(dāng)序列基本有序的時(shí)候，第三趟增量為1的希爾排序就是直接排序，這時(shí)只需要比較和移動少量的記錄即可。

    #include<iostream.h>
/******************
?* 希爾排序 Shell Sort   *
 ******************/
class ShellSort{
public:
    //希爾遞增排序
    static void inc_sort(int keys[],int size);
};

void ShellSort :: inc_sort(int keys[],int size){
  int increment=size; //增量
  do{
	increment=increment/3+1; //增量逐步減少至1
        int post_key;
	for(int i=increment;i<size;i++){
		if(keys[i]<keys[i-increment]){
			post_key=keys[i];
			for(int j=i-increment;j>=0&&post_key<keys[j];j=j-increment){
				keys[j+increment]=keys[j];
			}
			keys[j+increment]=post_key;
		}
	}
	cout<<"一趟希爾排序(增量="<<increment<<")：";
	for(int k=0;k<size;k++)
		cout<<keys[k]<<" ";
	cout<<endl;
   }while(increment>1);
}

void main(){
	int raw[]={49,38,65,97,76,13,27,49};  
	int size=sizeof(raw)/sizeof(int);  
	ShellSort::inc_sort(raw,size);
}
  

?

???? 希爾排序的性能是個(gè)很復(fù)雜的問題，主要與增量的取值有關(guān)。到目前為止，還沒有人求的最好的增量結(jié)果。但是大量數(shù)據(jù)實(shí)驗(yàn)表明， 布爾排序的時(shí)間復(fù)雜度趨近于O(N*logN) 。但不管增量如何取值，最后一趟希爾排序的增量必須為1才能真正得到有序序列。 而且希爾排序是不穩(wěn)定的。

?

【排序結(jié)構(gòu)1】插入排序