【排序结构1】插入排序

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才能真正得到有序序列。而且希尔排序是不稳定的。