1、基本概念介紹

?

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

?

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

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

?

?

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

?

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

???? ? ? ? ? ? ? ? ? ? ?? 待排序列：?? 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:
	//遞增穩定排序
	static void inc_sort(int keys[], int size);
};
void SISortion:: inc_sort(int keys[], int size){
    //記錄當前要插入的key
    int post_key;
    //從第二個數據開始
    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;
      }
      //打印排序結果
      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);
}
  

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

?

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

?

折半插入排序和直接插入排序的不同點在“查找”上。在有序關鍵字序列中，每次插入的關鍵字采用折半查找的方法來定位。雖然折半查找的時間復雜度為O(logN)，但定位后循環數據后移仍然要花費O(N)的代價。因此時間 復雜度仍然是O(N^2)，空間復雜度為O(1)，排序是穩定的。

    #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)，它也是一種插入排序，但是在時間效率上比前面兩種有較大的改進。

?

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

?

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

?????????

? ?? 很明顯，希爾排序對每一趟增量子序列都是一種直接插入排序。但是每一趟排序中記錄關鍵字都是和同一子序列中前一個記錄的關鍵字進行比較(子序列相鄰關鍵字之間的位置相差一個增量)，因此關鍵字較小的記錄不是一步一步向前挪動，而是根據增量大小跳躍式的前進。當序列基本有序的時候，第三趟增量為1的希爾排序就是直接排序，這時只需要比較和移動少量的記錄即可。

    #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);
}
  

?

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

?

【排序結構1】插入排序