数据结构—排序总结

      

数据结构—排序

     数据结构这本书自己已经翻了好几遍,每次看都有不一样的收获,这几天花了些时间重新看了一下排序这一方面,虽然总的来说排序就那么几种,但是每一种排序代表了一种思想，还是要花时间认真看看的。
     下面主要就是就是我学习的收获，下面贴的代码也主要是数据结构（严蔚敏）书上的,都是通过自己测试过的，通过写书上的代码也算是加深了一点认识吧!常用的内部排序算法主要分为五类：插入、交换、选择、归并、基数排序。这里也只分析内部排序不涉及到外部排序。
一、插入排序
在一个已经排好序的序列中，将未被排进的元素按照原先的规定插入到指定位置
1、直接插入排序
我觉得这是比较简单的排序方法，它的基本基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

void InsertSort(SqList &L)
{ /* 对顺序表L作直接插入排序。*/
  int i,j;
  for(i=2;i<=L.length;++i)
    if LT(L.r[i].key,L.r[i-1].key) /* "<",需将L.r[i]插入有序子表 */
    {
      L.r[0]=L.r[i]; /* 复制为哨兵 */
      for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)
 L.r[j+1]=L.r[j]; /* 记录后移 */
      L.r[j+1]=L.r[0]; /* 插入到正确位置 */
    }
}

2、折半插入排序
这种插入排序是上一种排序的改进，因为是已经确定了前部分是有序序列，所以在查找插入位置的时候可以用折半查找的方法进行查找，提高效率，但是时间复杂度还是O(n²)

void BInsertSort(SqList &L)
{ /* 对顺序表L作折半插入排序。*/
  int i,j,m,low,high;
  for(i=2;i<=L.length;++i)
  {
    L.r[0]=L.r[i]; /* 将L.r[i]暂存到L.r[0] */
    low=1;
    high=i-1;
    while(low<=high)
    { /* 在r[low..high]中折半查找有序插入的位置 */
      m=(low+high)/2; /* 折半 */
      if LT(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]; /* 插入 */
  }
}

3、2-路插入排序
2-路插入排序是在折半插入排序的基础上再改进的，其目的是减少排序过程中移动记录的次数，但需要n个记录的辅助空间

void P2_InsertSort(SqList &L)
{ /* 2_路插入排序 */
  int i,j,first,final;
  RedType &d;
  d=(RedType*)malloc(L.length*sizeof(RedType)); /* 生成L.length个记录的临时

空间 */
  d[0]=L.r[1]; /* 设L的第1个记录为d中排好序的记录(在位置[0]) */
  first=final=0; /* first、final分别指示d中排好序的记录的第1个和最后1个记录的位

置 */
  for(i=2;i<=L.length;++i)
  { /* 依次将L的第2个～最后1个记录插入d中 */
    if(L.r[i].key<d[first].key)
    { /* 待插记录小于d中最小值，插到d[first]之前(不需移动d数组的元素) */
      first=(first-1+L.length)%L.length; /* 设d为循环向量 */
      d[first]=L.r[i];
    }
    else if(L.r[i].key>d[final].key)
    { /* 待插记录大于d中最大值，插到d[final]之后(不需移动d数组的元素) */
      final=final+1;
      d[final]=L.r[i];
    }
    else
    { /* 待插记录大于d中最小值，小于d中最大值，插到d的中间(需要移动d数组的元素)*/ 
      j=final++; /* 移动d的尾部元素以便按序插入记录 */
      while(L.r[i].key<d[j].key)
      {
        d[(j+1)%L.length]=d[j];
        j=(j-1+L.length)%L.length;
      }
      d[j+1]=L.r[i];
    }
  }
  for(i=1;i<=L.length;i++) /* 把d赋给L.r */
    L.r[i]=d[(i+first-1)%L.length]; /* 线性关系 */
}

4、希尔排序
又称缩小增量排序法。把待排序序列分成若干较小的子序列，然后逐个使用直接插入排序法排序，最后再对一个较为有序的序列进行一次排序，主要是为了减少移动的次数，提高效率。原理应该就是从无序到渐渐有序，要比直接从无序到有序移动的次数会少一些

void ShellInsert(SqList &L,int dk)
{ /* 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比， */
  /* 作了以下修改： */
  /* 1.前后记录位置的增量是dk,而不是1; */
  /* 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。*/
  int i,j;
  for(i=dk+1;i<=L.length;++i)
    if LT(L.r[i].key,L.r[i-dk].key)
    { /* 需将L.r[i]插入有序增量子表 */
      L.r[0]=L.r[i]; /* 暂存在L.r[0] */
      for(j=i-dk;j>0&&LT(L.r[0].key,L.r[j].key);j-=dk)
        L.r[j+dk]=L.r[j]; /* 记录后移，查找插入位置 */
      L.r[j+dk]=L.r[0]; /* 插入 */
    }
}

二、交换排序
通过交换逆序元素进行排序的方法
1、冒泡排序
冒泡排序也是一种很简单的排序，主要操作就是反复扫描待排序序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。第一趟，从第一个数据开始，比较相邻的两个数据，（以升序为例）如果大就交换，得到一个最大数据在末尾；然后进行第二趟，只扫描前n-1个元素，得到次大的放在倒数第二位。以此类推，最后得到升序序列。如果在扫描过程中，发现没有交换，说明已经排好序列，直接终止扫描。所以最多进行n-1趟扫描

void bubble_sort(int a[],int n)
{ /* 将a中整数序列重新排列成自小至大有序的整数序列(起泡排序) */
  int i,j,t;
  Status change;
  for(i=n-1,change=TRUE;i>1&&change;--i)
  {
    change=FALSE;
    for(j=0;j<i;++j)
      if(a[j]>a[j+1])
      {
        t=a[j];
        a[j]=a[j+1];
        a[j+1]=t;
        change=TRUE;
      }
  }
}

2、快速排序
快速排序的时间复杂度达到O(nlgn)，被公认为最快的排序方法之一。在所有同数量级O(nlgn)的排序当中，其平均性能最好。它其实是冒泡排序的改进，当一列数据基本有序的时候，快速排序将为蜕化为冒泡排序，时间复杂度为O(n平方）。基本思想是取一个数作为中间数，比它小的都排左边，比它大的都排右边（如果是从大到小排序的话，就反过来），再对每一边用同样的思路进行递归求解。快速排序是不稳定的排序方式。

int Partition(SqList &L,int low,int high)
{ /* 交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位， */
  /* 并返回其所在位置，此时在它之前(后)的记录均不大(小)于它。*/
  RedType t;
  KeyType pivotkey;
  pivotkey=L.r[low].key; /* 用子表的第一个记录作枢轴记录 */
  while(low<high)
  { /* 从表的两端交替地向中间扫描 */
    while(low<high&&(*L).r[high].key>=pivotkey)
      --high;
    t=L.r[low]; /* 将比枢轴记录小的记录交换到低端 */
    L.r[low]=L.r[high];
    L.r[high]=t;
    while(low<high&&L.r[low].key<=pivotkey)
      ++low;
    t=L.r[low]; /* 将比枢轴记录大的记录交换到高端 */
    L.r[low]=L.r[high];
    L.r[high]=t;
  }
  return low; /* 返回枢轴所在位置 */
}
void QSort(SqList &L,int low,int high)
{ /* 对顺序表L中的子序列L.r[low..high]作快速排序。*/
  int pivotloc;
  if(low<high)
  { /* 长度大于1 */
    pivotloc=Partition(L,low,high); /* 将L.r[low..high]一分为二 */
    QSort(L,low,pivotloc-1); /* 对低子表递归排序，pivotloc是枢轴位置 */
    QSort(L,pivotloc+1,high); /* 对高子表递归排序 */
  }
}
void QuickSort(SqList &L)
{ /* 对顺序表L作快速排序。*/
  QSort(L,1,L.length);

三、选择排序
1、简单选择排序
简单选择排序思路也很简单，主要操作就是第一趟时，从第一个记录开始，通过n – 1次关键字的比较，从n个记录中选出关键字最小的记录，并和第一个记录进行交换。第二趟从第二个记录开始，选择最小的和第二个记录交换。以此类推，直至全部排序完毕。。时间复杂度也是 O(n^2)，是不稳定的排序方式

int SelectMinKey(SqList L,int i)
{ /* 返回在L.r[i..L.length]中key最小的记录的序号 */
  KeyType min;
  int j,k;
  k=i; /* 设第i个为最小 */
  min=L.r[i].key;
  for(j=i+1;j<=L.length;j++)
    if(L.r[j].key<min) /* 找到更小的 */
    {
      k=j;
      min=L.r[j].key;
    }
  return k;
}
void SelectSort(SqList &L)
{ /* 对顺序表L作简单选择排序。*/
  int i,j;
  RedType t;
  for(i=1;i<L.length;++i)
  { /*  选择第i小的记录，并交换到位 */
    j=SelectMinKey(&L,i); /* 在L.r[i..L.length]中选择key最小的记录 */
    if(i!=j)
    { /* 与第i个记录交换 */
      t=L.r[i];
      L.r[i]=L.r[j];
      L.r[j]=t;
    }
  }
}

2、堆排序
堆排序是一种常用到的排序方法，主要操作时把待排序记录的关键字存放在数组r[1…n]中，将r看成是一刻完全二叉树的顺序表示，每个节点表示一个记录，第一个记录r[1]作为二叉树的根，一下个记录r[2…n]依次逐层从左到右顺序排列，任意节点r[i]的左孩子是r[2i]，右孩子是r[2i+1]，双亲是r[i/2向下取整]。然后对这棵完全二叉树进行调整建堆,堆排序的时间复杂度是O(nlgn)，也是最快的排序方法之一，在最坏的情况下，其时间复杂度还是O(nlgn)，相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需要一个记录大小供交换用的辅助存储空间。堆排序也是不稳定的排序。

void HeapAdjust(HeapType &H,int s,int m) 
{ /* 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数 */
  /* 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) */
  RedType rc;
  int j;
  rc=H.r[s];
  for(j=2*s;j<=m;j*=2)
  { /* 沿key较大的孩子结点向下筛选 */
    if(j<m&&LT(H.r[j].key,H.r[j+1].key))
      ++j; /* j为key较大的记录的下标 */
    if(!LT(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)
{ /* 对顺序表H进行堆排序。*/
  RedType t;
  int i;
  for(i=H.length/2;i>0;--i) /* 把H.r[1..H.length]建成大顶堆 */
    HeapAdjust(H,i,H.length);
  for(i=H.length;i>1;--i)
  { /* 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 */
    t=H.r[1];
    H.r[1]=H.r[i];
    H.r[i]=t;
    HeapAdjust(H,1,i-1); /* 将H.r[1..i-1]重新调整为大顶堆 */
  }
}

四、归并排序
归并排序的主要思想是假设初始序列右n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2向上取整 个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列。在此基础上，在对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列。如此重复，直至得到一个长度为n的有序序列为止。与快速排序相比，归并排序的最大特点是：它是一种稳定的排序方法

void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
  int j,k,l;
  for(j=m+1,k=i;i<=m&&j<=n;++k) /* 将SR中记录由小到大地并入TR */
    if LQ(SR[i].key,SR[j].key)
      TR[k]=SR[i++];
    else
      TR[k]=SR[j++];
  if(i<=m)
    for(l=0;l<=m-i;l++)
      TR[k+l]=SR[i+l]; /* 将剩余的SR[i..m]复制到TR */
  if(j<=n)
    for(l=0;l<=n-j;l++)
      TR[k+l]=SR[j+l]; /* 将剩余的SR[j..n]复制到TR */
}
void MSort(RedType SR[],RedType TR1[],int s, int t)
{ /* 将SR[s..t]归并排序为TR1[s..t]。*/
  int m;
  RedType TR2[MAXSIZE+1];
  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] */
  }
}

四、基数排序
基数排序
基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零,然后从最低位开始, 依次进行一次稳定排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列,由于实现起来比较复杂,我还没写出来实现的代码，有兴趣的可以自己实现一下