数据结构内部排序算法笔记
in 学习笔记 with 0 comment

数据结构内部排序算法笔记

in 学习笔记 with 0 comment

数据结构也快要结课了,在复习的时候发现排序算法挺多而且很多并不熟悉,所以决定写一篇博客复习一下这些算法。
先列一下排序算法的目录吧:
目录

以下所指的数据类型为:

  typedef int KeyType;
  typedef struct{
      KeyType key;
      InfoType otherinfo;    //其他数据项
  }RedType;
  
  typedef struct{
      RedType r[MAXSIZE+1];  //r[0]闲置或作哨兵
      int length;
  }SqList;

一、插入排序

直接插入排序

思想: 将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。即:先将第一个记录看作有序的,然后从第二个记录起和第一个比较、插入,这样就得到了一个有两个记录的有序表;然后再将第三个记录和已得到的有序表进行比较、插入......一直到整个序列有序。
算法:

  void InsertSort(SqList &L){
      //对顺序表L进行直接插入排序
      for(int 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];            //插入到正确位置
          }
      }
  } 

分析: 时间复杂度为O(n2),比较次数最少为n-1次(不需要移动),最多为(n+2)(n-1)/2次(记录为逆序的时候),最多移动次数也达到最大值
(n+4)(n-1)/2。直接插入排序是稳定的,适用于n较小的情况。

希尔排序

思想: 先将整个排排序的序列分割成若干个序列(并不是连续的几个记录,而是相隔dk的记录)分别进行直接插入排序,完成后再将全体记录进行排序。过程是:先取dk作为增量,将记录分为{R[1],R[1+dk],R[1+2dk},...},{R[2],R[2+dk,R[2+2dk],...]}....,再将每个序列进行直接插入排序,一趟后每个小序列有序;待每个序列有序后,再次取更小的dk,重复上述过程,直至dk减到1(dk不是连续的数,应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况)为止。
算法:

  void ShellInsert(SqList &L,int dk){
      //对顺序表L进行一趟希尔插入排序。
      //相对于直接插入排序:
      //  前后记录位置的增量是dk,不是1;
      //  r[0]是暂存单元,不是哨兵。当j<=0时,插入位置已找到。
      for(int i=dk+1;i<=L.length;i++){
          if(L.r[i].key<L.r[i-dk].key){ //需将L.r[i]插入到有序增量子表中
              L.r[0]=L.r[i];              //暂存在L.r[0]中
          int j=i-dk;
          for(j=i-dk;(j>0)&&(L.r[0].key<L.r[j].key);j-=dk){
              L.r[j+dk]=L.r[j];         //记录后移
              L.r[j+dk]=L.r[0];           //插入,不可将r[j+dk]改为r[i]
          }
      }
  }
  
  void ShellSort(SqList &L,int dlta[],int t){
      //按增量序列dlta[0..t-1]对顺序表L作希尔排序,t为排序的趟数
      for(int k=0;k<t;k++){
          ShellInsert(L,dlta[k]);  //一趟增量为dlta[k]的插入排序
      }
  }

分析: 希尔排序的时间复杂度与增量序列的选取有关,目前还没有人求得一种最好的增量序列。希尔排序时间复杂度的下界是n(log2n)。希尔排序没有快速排序算法快O(n(logn)),因此中等大小规模表现良好,对规模非常大的数据排序不是最优选择。但是比O(n2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单.此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏的情况下执行的效率会非常差。希尔排序是非稳定的。

折半插入排序

思想: 折半插入排序是对插入排序算法的一种改进,由于排序算法过程中,就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列,这样我们不用按顺序依次寻找插入点,可以采用折半查找的方法来加快寻找插入点的速度。过程是:在将一个新元素插入已排好序的数组的过程中,寻找插入点时,将待插入区域的首元素设置为a[low],末元素设置为a[high],则轮比较时将待插入元素与a[m],其中m=(low+high)/2相比较,如果比参考元素小,则选择a[low]到a[m-1]为新的插入区域(即high=m-1),否则选择a[m+1]到a[high]为新的插入区域(即low=m+1),如此直至low<=high不成立,即将此位置之后所有元素后移一位,并将新元素插入a[high+1]。
算法:

  void BInsertSort(SqList &L){
      //对顺序表L作折半插入排序
      for(int i=2;i<=L.length;++i){
          L.r[0]=L.r[i];             //将L.r[i]暂存到L.r[0]
          int low=1;
          int high=i-1;
          while(low<=high){          //在r[low..high]中折半查找有序插入的位置
              int m=(low+high)/2;      //折半
              if(L.r[0].key<L.r[m].key) high=m-1;  //插入点在低半区
              else low=m+1;                        //插入点在高半区
          }//while
          for(int j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];  //记录后移
          L.r{high+1]=L.r[0]                             //插入
      }//for
  }

分析: 折半插入排序所需附加存储空间和直接插入排序相同(一个),仅减少了关键字间的比较次数,而记录移动次数不变,因此折半插入排序的时间复杂度仍为O(n2)。

二、快速排序

思想: 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字都比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。过程是:假设待排序的序列为{L.r[s],L.r[s+1],...,L.r[t]},首先任意选取一个记录(通常选第一个记录L.r[s])作为枢轴(pivot),将所有关键字比它小的记录都安置在它的位置之前,将所有关键字比它大的都放置在它之后,枢轴记录最后所落的位置为i作分界线,将原序列分割为{L.r[s],L.r[s+1],...,L.r[i-1]}和{L.r[i+1],L.r[i+2],...,L.r[t]}。这个过程称为一趟。做法是:设两个指针low和high,枢轴记录的关键字为pivotkey,1、先从high开始向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录交换,2、然后从low开始向后搜索找到第一个关键字大于pivotkey的记录和枢轴记录交换;重复这两步直至low=high为止。
算法:

  void Partition(SqList &L,int low,int high){
      //交换顺序表L中子表L.r[low..high]的记录,使枢轴记录到位,并返回其所在位置,
      //此时在它之前(后)的记录均小于(大于)它。
      L.r[0]=L.r[low]                  //用子表的第一个记录作枢轴记录
      int 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;                      //返回枢轴位置
  }

分析: 快速排序的平均时间为T(n)=knlnn(平均时间复杂度为O(nlogn)),n为待排序序列中记录的个数,k为某个常数,就平均时间而言,快速排序是目前被认为是最好的一种内部排序方法。最坏情况时间复杂度为O(n2),辅助存储空间O(logn)。快速排序也是不稳定的。

三、选择排序

简单选择排序

思想: 每一趟在n-i+1(i=1,2,...,n-1)个记录中选出关键字最小的记录,并与第i个记录交换之。一趟的操作为令i从1至n-1,进行n-1趟选择排序操作。
算法:

  void SelectSort(SqList &L){
      for(int i=1;i<L.length;i++){    //选择第i小的记录,并交换到位
          j=SlectMinKey(L,i);           //在L.r[i...L.length]间选择关键字最小的值
          if(i!=j){                     //与第i个记录交换
              int temp=L.r[i];
              L.r[i]=L.r[j];
              L.r[j]=temp;
          }
      }
  }

分析: 简单选择排序是不稳定的排序,记录移动的次数最小是0,最大是3(n-1),关键字之间的比较次数为n(n-1)/2,时间复杂度是O(n2)。

树形选择排序

思想: 首先对n个记录的关键字进行两两比较,然后再n/2个较小的关键字之间再进行两两比较,如此反复直至找到最小关键字的记录为止。
算法:

分析: 除最小关键字之外,每选择一个次小的关键字仅需要进行log2n次比较,时间复杂度为O(nlogn),但是有辅助存储空间大和最大值进行多余比较的缺点。

堆排序

定义: 左右子树都不小于结点小(小根堆)或者都不大于结点(大根堆)。
思想: 若在输出堆顶的最小值之后,使得剩余n-1个元素的序列重又建成一个堆,则得到n个元素中的次小值,如此反复即可得到一个有序序列。
算法:

  typedef SqList HeapType;   //堆采用顺序表存储表示
  
  void HeapAdjust(HeapType &H,int s,int m){
      //已知H.r[s...m]中记录的关键字除H.r[s].key外均满足堆的定义,本函数调整H.r[s]的关键字,使H.r[s...m]成为一个大根堆
      int rc=H.r[s];
      for(int j=2*s;j<=m;j*=2){     //沿关键字较大的孩子结点向下筛选
          if(j<m&&H.r[j].key<H.r[j+1].key)  ++j;      //j为关键字较大的记录的下标
          if(rc.key>=H.r[j].key) break;               //rc应插入在位置s上
          H.r[s]=H.r[j];
          s=j;
      }
      H.r[s]=rc;                                    //插入
  }
  
  void HeapSort(HeapType &H){
      for(int i=H.length/2;i>0;--i){    //把H.r[1...L.length]建成大根堆
          HeapAdjust(H,i,H.length);
      }
      for(int i=H.length;i>1;--i){      //将堆顶记录与当前未经排序子序列H.r[1...i]中最后一个记录互相交换
          int temp=H.r[1];
          H.r[1]=H.r[i];
          H.r[i]=temp;
          HeapAdjust(H,1,i-1);            //将H.r[1...i-1]重新调整为大根堆
      }
  }

分析: 只需要一个辅助存储空间,每个待排序的记录仅占一个存储空间。对于记录较少的文件并不值得提倡,最坏的情况下时间复杂度也为O(nlogn),也是不稳定的。

四、归并排序

思想: 将两个或两个以上的有序表合成一个新的有序表。一趟归并排序的操作是调用n/2h次算法Merge将SR[1..n]中前后相邻且长度为h的有序段进行两两归并,得到前后相邻、长度为2h的有序段,并存放在TR[1..n]中。
算法:

  void Merge (RcdType SR[],RcdType TR[],int i,int m,int n){ 
      int j,k;
      for (j=m+1,k=i;i<=m&&j<=n;++k) {   
          if(SR[i].key<=SR[j].key) TR[k] = SR[i++];
          else TR[k] = SR[j++];
      }
      if (i<=m){
          while(k<=n&&i<=m) TR[k++]=SR[i++];
      }
      if (j<=n){ 
          while(k<=n&&j<=n) TR[k++]=SR[j++];
      }
  } // Merge

  void MSort(RcdType SR[],RcdType &TR1[],int s,int t){
      //将SR[s..t]归并排序为TR1[s...t]
      if(s==t) TR1[s]=SR[s];
      else{
          m=(s+t)/2;             //将SR[s..t]平分为SR[s..m]和SR[m+1..t]
          MSort(SR,TR2,s,m);     //递归的将SR[s..m]归并为有序的TR2[s..m]
          MSort(SR,TR2,m+1,t);   //递归的将SR[m+1..t]归并为有序的TR2[m+1..t]
          Merge(TR2,TR1,s,m,t);  //将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
      }
  }
  
  void MergeSort(SqList &L){  //归并排序
        MSort(L.r,L.r,1,L.length);
  }

分析:归并排序是稳定的,所需辅助空间和待排记录等数量,时间复杂度为O(nlogn),需要进行log2n趟。

五、基数排序

顺序基数排序

思想:基数排序起源于箱(桶)排序,设置若干个箱子(桶),依次扫描待排序的记录,A[1],A[2],…,A[n],把关键字为k的记录放在第k个箱子里,按序号将非空的箱子里的记录收集起来。但如果如果关键字位数太大,这样做空间复杂性和时间复杂性都太大。具体操作是先设待排记录A的关键字最大是figure位的正整数。然后1、从最低位(个位)开始,扫描关键字的pass位,把等于0的插入Q[0],…,等于9的插入Q[9]。2、将Q[0],…,Q[9]中的数据依次收集到A[]中。最后pass+1直到figure,重复执行1,2两步。
算法:

  int RADIX(int k,int p){
      //取关键字k 的第p位,p从1开始
      return((k/pow10(p-1))%10);
  }

  void radixsort(int figure, QUEUE &A){
      QUEUE Q[10];
      records data;
      int pass,r,i; //pass用于位数循环,r取位数
      for(pass=1;pass<=figure;pass++){
          for(i=0;i<=9;i++){
              MAKENULL(Q[i]);           //把10个队列置空
              while(!EMPTY(A)) {
                 data=FRONT(A);           //取A中元素dada,
                 DEQUEUE(A);
                 r=RADIX(data.key,pass);  //计算data的关键字的第pass位的值r
                 ENQUEUE(data,Q[r]);      //放入队列Q[r]中
              }//while
          }//for
      }//for
  }//radixsort

分析: 基数排序是稳定的,设关键字位数为d,则时间复杂性为O(dn),考虑到d是一个常数,时间复杂性为O(n),空间复杂性O(n)。

各种排序算法的比较

放一张老师的课件:
内部排序算法比较

Responses