数据结构10——排序

排序(插入排序、交换排序、选择排序、归并排序、分配排序)

排序算法的稳定性：假定待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍保持不变，则称这种排序算法是稳定的；否则，称为不稳定。

排序的分类

根据排序数据在内存中还是外存中：

  内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中

  外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程要在内外存之间多次交换数据才能得到排序的结果

根据排序过程中所进行的基本操作分：

  基于比较：基本操作——关键码的比较和记录的移动，其最差时间下限已经被证明为O(nlog2 n)；

  不基于比较：根据关键码的分布特征。比如桶式排序、基数排序(多关键字排序)

  基于比较的内排序：(插入排序、交换排序、选择排序、归并排序)

  不基于比较的内排序：(分配排序、桶式排序、基数排序)

排序算法的性能

  时间复杂性：基本操作

    内排序过程中的基本操作：

        比较：关键码之间的比较

        移动：记录从一个位置移动到另一个位置

  空间复杂性：辅助存储空间

    辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法需要的其他存储空间

  插入类排序(每次将一个待排序的记录按期关键码的大小插入到已经排好序的有序序列中，直到全部记录排好序为止)

方法：直接插入排序、希尔排序

直接插入排序：平均时间复杂度O(n^2)空间复杂度O(1)

void  insertSort (int  r[ ], int n){	
   for (i=2; i<=n; i++)   { 
       r[0]=r[i]; j=i-1;
       while (r[0]<r[j]) {  
           r[j+1]=r[j];	j=j-1;}
       r[j+1]=r[0];}}
r[0]的作用：(1)进入循环之前暂存r[i]的值，使得不至于因记录的后移而丢失r[i]的内容(2)在查找插入位置的循环中充当哨兵

希尔排序：时间性能在O(n^2)和O(nlog2 n)之间（当n在某个特定范围内，希尔排序所需要的比较次数和记录的移动次数约为O(n^1.3)）

void Shellsort(int r[],int n){
  for (d=n/2; d>=1; d=d/2){
     for (i=d+1; i<=n; i++) {
	     r[0]=r[i];           
	     j=i-d;                
	     while (j>0 && r[0]<r[j]) { 
          	r[j+d]=r[j]; 
	          j=j-d; }
	      r[j+d]=r[0]; }}}

交换类排序(在待排序序列中选两个记录，将他们的关键码相比较，如果反序(即排列顺序与排序后的次序正好相反)，则交换他们的存储位置)

方法：冒泡排序、快速排序

起泡排序(冒泡排序):平均时间复杂度O(n^2)

void BubbleSort(int r[ ], int n)
{	
    exchange=n; 	
    while (exchange) {
        bound=exchange; //bound记录无序区的最后一个记录
        exchange=0；  
        for (j=1; j<bound; j++)
            if (r[j]>r[j+1]) {
            int tmp;tmp=r[j];r[j]=r[j+1];r[j+1]=tmp;
// r[j]←→r[j+1]；
	      exchange=j； } }}

如何提高起泡排序的性能：(在排序过程中交替改变扫描方向——双向起泡排序)

int temp;
int    exchange1,exchange2;
int bound1,bound2;
exchange1=n-1; 
exchange2=0; 
while (exchange1) {
    exchange1=0;  
    bound1=exchange1;
    bound2=exchange2;
    for (int j=bound2; j<bound1; j++) 
        if (r[j]>r[j+1]){
	temp=r[j];
	r[j]=r[j+1];
	r[j+1]=temp;
	exchange1=j; 
	}
    bound1=exchange1;    
for ( j=bound1; j>bound2; j--) 
	    if (r[j]<r[j+1]) {
		  temp=r[j];
		  r[j]=r[j+1];
		  r[j+1]=temp;
		  exchange2=j; 
	   }
		bound2=exchange2;
	}

快速排序：平均时间复杂度：O(nlog2 n)

int Partition(int r[ ], int first, int end)
{	
    i=first; j=end;         //初始化
    r[0]=r[i];
     while (i<j)	
    {  
      while (i<j && r[0]<= r[j]) j--；  //右侧扫描
       if (i<j) { 
          r[i]=r[j];   i++;  //将较小记录交换到前面
       }
       while (i<j && r[i]<= r[0]) i++；  //左侧扫描
       if (i<j) {
          r[j]=r[i];   j--;  //将较大记录交换到后面
       }
    }
    r[i]=r[0];
    retutn i;    //i为轴值记录的最终位置
}
void QuickSort (int  r[ ], int first, int end ){   //在序列 first~end中递归地进行快速排序
    if (first < end) {				//first==end是递归出口	
          pivotpos = Partition (r, first, end );    
          QuickSort (r, first, pivotpos-1);
          QuickSort (r, pivotpos+1, end );
   }
}

选择排序

方法：简单选择排序、堆排序

简单选择排序：平均时间复杂度:O(n^2)空间复杂度：O(1)稳定性：不稳定

void  selectSort ( int  r[ ], int n)
{   
    for ( i=1; i<n; i++) 
    {  
        index=i; 		
        for (j=i+1; j<=n; j++) 
           if  (r[j]<r[index])  index=j;
        if (index!=i)  
         int tmp;tmp=r[j];r[j]=r[j+1];r[j+1]=tmp;// r[i]<==>r[index]; 	 
    }
} 

堆排序：时间复杂度:O(n)稳定性：不稳定

  堆调整算法：

void sift ( int r[ ], int k, int m ){ //要筛选结点的编号为k，堆中最后一个结点的编号为m 
    i=k;  j=2*i;  temp=r[i];  //将筛选记录暂存
    while (j<=m )           //筛选还没有进行到叶子
    {
        if (j<m && r[j]<r[j+1]) j++;  //左右孩子中取较大者
        if (temp>r[j]) break; 
        else {
             r[i]=r[j];   i=j;   j=2*i;
        }
     }
     r[i]=temp;   //将筛选记录移到正确位置
}

堆排序算法：

void  HeapSort ( int  r[], int n)
{
    for (i=n/2; i>=1; i--)      //初建堆
       sift(r, i, n) ;     
    for (i=1; i<n; i++ )
    {
       r[1]←→r[n-i+1];        //移走堆顶
       sift(r, 1, n-i);               //重建堆
    }
}	

归并排序：(将若干有序序列逐步归并，最终得到一个有序序列)

  二路归并排序：平均时间复杂度O(nlog2 n)空间复杂度O(n)

    将两个有序序列合成一个有序序列算法：

void Merge (int r[ ], int r1[ ], int s, int m, int t )
{
    i=s;   j=m+1;   k=s;
    while (i<=m && j<=t)
    {   
        if (r[i]<=r[j])  r1[k++]=r[i++];
        else  r1[k++]=r[j++]; 
     }
     if (i<=m)  while (i<=m)              //收尾处理
                           r1[k++]=r[i++];    //前一个子序列
     else  while (j<=t)
                  r1[k++]=r[j++];             //后一个子序列
} 	

一趟归并排序算法：

void  MergePass (int  r[ ], int  r1[ ], int  n, int  h)
{
     i=1;		//第一个子序列的第一个元素
     while (i≤n-2h+1)                //情况1
     {
           Merge (r, r1, i, i+h-1, i+2*h-1);
           i+=2*h;
      }
      if (i＜n-h+1) Merge (r, r1, i, i+h-1, n);   //情况2
      else for (k=i; k<=n; k++)    //情况3
                 r1[k]=r[k];
}

递归实现算法：

void msort(int a[], int r[], int s, int t){
    if(s==t) 
         return;              //如果只有一个数字则返回，无须排序
    int mid=(s+t)/2;
    msort(s,mid);                //分解左序列
    msort(mid+1,t);            //分解右序列
    int i=s, j=mid+1, k=s;   //接下来合并
    while(i<=mid && j<=t)  {
          if(a[i]<=a[j]) {
                r[k]=a[i];     k++; i++;
           }
          else {
               r[k]=a[j];  k++; j++;
          }
    }  
          while(i<=mid) {     //复制左边子序列剩余
           r[k]=a[i]; k++; i++;
       }
       while(j<=t)  {  //复制右边子序列剩余  
        
            r[k]=a[j]; k++; j++;
        }
        for(int i=s; i<=t; i++)
              a[i]=r[i];  
        return 0;
} 

分配排序：时间复杂度可达到线性阶O(n);

方法：桶式排序（单关键字排序）、链式基数排序（多关键字排序）