【数据结构】课堂复习笔记6——排序

学习的网课是青岛大学-王卓的数据结构与算法基础系列课程，可在bilibili上观看。并配合zjut课堂笔记整理，仅用于学习和复习

七、排序

7.1 排序概述

  • 内部排序和外部排序
    • 若待排序记录都在内存中，称为内部排序
    • 若待排序记录一部分在内存，一部分在外存，则称为外部排序。
  • 规则不同：
    • 插入排序
    • 交换排序
    • 选择排序
    • 归并排序
  • 稳定性：A和B的关键字相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。
  • 时间复杂度：
    • 简单排序
    • 先进排序

记录序列以顺序表存储

# define MAXSIZE 20        //设记录不超过20个
typedef  int  KeyType ;       //设关键字为整型量（int型）
typedef  struct {                  //定义每个记录（数据元素）的结构
    KeyType      key ;            //关键字 
    InfoType      otherinfo;    //其它数据项
}RedType ;
typedef  struct {                          //定义顺序表的结构
  RedType  r [ MAXSIZE +1 ];   //存储顺序表的向量
 //r[0]一般作哨兵或缓冲区
  int length ;                                 //顺序表的长度
}SqList ;

7.2 插入排序

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

7.2.1 直接插入排序

顺序查找法

void InsertSort(SqList ＆L)
 {
    int i,j;
   for(i=2;i<=L.length;++i)
     if( L.r[i].key<L.r[i-1].key)//将L.r[i]插入有序子表
       { L.r[0]=L.r[i]; // 复制为哨兵
          L.r[i]=L.r[i-1];
          for(j=i-2; L.r[0].key<L.r[j].key;--j)
                L.r[j+1]=L.r[j]; // 记录后移 
         L.r[j+1]=L.r[0]; //插入到正确位置
       }
 }

算法分析：

  • 最好情况下：
    • 每趟只需比较 1 次，不移动
    • 总比较次数为 n-1
  • 最坏情况下：第 i 趟比较i次，移动i+1次
    • 时间复杂度：

7.2.2 折半插入排序

void  BInsertSort ( SqList &L )
 { for ( i = 2;  i <= L.length ; ++i )
    {  L.r[0] = L.r[i]; low = 1 ; high = i-1 ;
       while ( low <= high )       
          {  m = ( low + high ) / 2 ; 
             if  (  L.r[0].key < L.r[m]. key  )  high = m -1 ;
            else  low = m + 1; 
           }
       for ( j=i-1; j>=high+1; - - j ) L.r[j+1] = L.r[j];
       L.r[high+1] = L.r[0];
     }
  }  // BInsertSort

算法分析：

  • 折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。
  • 它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第 i 个对象时，需要经过次关键码比较，才能确定它应插入的位置 。
    • 当 n 较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差
    • 在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少
  • 折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列
  • 减少了比较次数，但没有减少移动次数
    • 平均性能优于直接插入排序
    • 时间复杂度：
    • 空间复杂度为
    • 稳定的排序

7.2.3 希尔排序

先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

void   ShellSort(SqList &L，int dlta[ ]，int t){
        //按增量序列dlta[0…t-1]对顺序表L作Shell排序
   for(k=0；k<t；++k)
    　ShellInsert(L，dlta[k])；
　 　//增量为dlta[k]的一趟插入排序
}  // ShellSort

void   ShellInsert(SqList &L，int dk) {
      
for(i=dk+1；i<=L.length； ++ i)
    if(r[i].key < r[i-dk].key) {         
       r[0]=r[i]；
       for(j=i-dk; j>0 &&(r[0].key<r[j].key); j=j-dk)
               r[j+dk]=r[j]；
        r[j+dk]=r[0]；
   }
}

算法分析：

  • 如何选择最佳d序列，目前尚未解决
  • 最后一个增量值必须为1，无除1以外的公因子
  • 不宜在链式存储结构上实现
    • 空间复杂度为 O(1)
    • 是一种不稳定的排序方法

7.3 交换排序

7.3.1 冒泡排序

void main() 			 
{	int a[11];		/*a[0]不用，之用a[1]~a[10]*/
    int i,j,t;
    printf("\nInput 10 numbers: \n");
    for(i=1;i<=10;i++)	scanf("%d",&a[i]);	printf("\n");
    for(j=1;j<=9;j++)
        for(i=1;i<=10-j;i++)
          if(a[i]>a[i+1])  {t=a[i];a[i]=a[i+1];a[i+1]=t;} //交换
    for(i=1;i<=10;i++)	printf("%d ",a[i]);   
}
  • 优点：
    • 每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素：一旦下趟没有交换，还可提前结束排序
void bubble_sort(SqList &L)
 { int m,i,j,flag=1;   RedType x;
   m=n-1;
   while((m>0)&&(flag==1))
   {  flag=0;
      for(j=1;j<=m;j++)
         if(L.r[j].key>L.r[j+1].key)
          {  flag=1;
             x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x; //交换
           }//endif
      m--;
    }//endwhile
 }
  • 时间复杂度为
  • 空间复杂度为
  • 是一种稳定的排序方法
  • 最坏情况下：需 n-1趟排序，第i趟比较n-i次，移动3(n-i)次

7.3.2 快速排序

void main ( )
 {   QSort ( L, 1, L.length ); }

void QSort ( SqList &L，int low,  int  high ) 
{  if  ( low < high ) 
    {  pivotloc = Partition(L, low, high ) ;
        Qsort (L, low, pivotloc-1) ; 
        Qsort (L, pivotloc+1, high ) 
     }
}

int Partition ( SqList &L，int low,  int  high ) 
{  L.r[0] = L.r[low];   pivotkey = L.r[low].key;
   while  ( low < high ) 
    { while ( low < high && L.r[high].key >= pivotkey )  --high;
                 L.r[low] = L.r[high];
      while ( low < high && L.r[low].key <= pivotkey )  ++low;
                 L.r[high] = L.r[low];
     }
    L.r[low]=L.r[0]; 
    return low;
}

算法分析：

  • 可以证明，平均计算时间是
    • 实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。
  • 快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的low和high）
    • 最大递归调用层次数与递归树的深度一致，因此，要求存储开销为。
  • 空间效率：（）递归要用到栈空间
  • 不稳定

7.4 选择排序

7.4.1 简单选择排序

void SelectSort(SqList &K)
 { 
    for (i=1; i<L.length; ++i)
    { //在L.r[i..L.length] 中选择key最小的记录
        k=i;     
        for( j=i+1;j<=L.length ; j++)
            if ( L.r[j].key <L.r[k].key) k=j; 
        if(k!=i) L.r[i]←→L.r[k];            
    }  
}

算法分析：

  • 移动次数：
    • 最好情况：0
    • 最坏情况：3(n-1)
  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 不稳定

7.4.2 堆排序

满足： 或

如果将序列看成一个完全二叉树，非终端结点的值均小于或大于左右子结点的值。

  • 堆的调整：
    • 输出堆顶元素后，以堆中最后一个元素替代之
    • 将根结点与左、右子树根结点比较，并与小者交换
    • 重复直至叶子结点，得到新的堆
  • 算法分析：
    • 时间效率：
    • 空间效率：
    • 稳 定 性：不稳定
    • 适用于n 较大的情况

7.5 归并排序

归并：将两个或两个以上的有序表组合成一个新有序表

  • 算法分析：
    • 时间效率：
    • 空间效率：
    • 稳定

7.6 基数排序

算法分析：

  • 时间效率：
  • 空间效率：
  • 稳 定 性：稳定