数据结构-排序

提到排序，鸡皮疙瘩都起来了，排序思想固然是好玩的，但是代码的实现也是无比蛋疼，记忆起来噩梦级别，之后会在这里补充一些排序算法相关的练习题

排序习题

听首歌先，缓解接下来乏味的过程，Lantern是我很喜欢的挪威剧中的配乐

前言

我们根据待排序记录是否全部被放置在内存中，将排序分为内排序和外排序两种，外排序需要在内外存之间多次交换数据才能进行。我们本章主要讲的是内排序的算法

• 我们根据排序过程中借助的主要操作，将内排序分为：

1. 插入排序类

   包括直接插入排序跟希尔排序

2. 选择排序类

   包括简单选择排序和堆排序

3. 交换排序类

   包括冒泡排序跟快速排序

4. 归并排序类

   包括归并排序

---

排序的基本概念与分类

• 内排序与外排序

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行

• 对于内排序来说，排序算法的性能主要是受3个方面影响

1. 时间性能
2. 辅助空间
3. 算法的复杂度

• 我们根据排序过程中借助的主要操作，将内排序分为：插入排序，交换排序，选择排序，归并排序

  排序用到的结构与函数

  #define MAXSIZE 10  /*用于要排序数组个数的最大值，可根据需要修改*/
  typedef struct
  {
      int r[MAXSIZE+1];  /*用于存储要排序数组，r[0]用于哨兵或临时变量*/
      int length;  /*用于记录顺序表的长度*/
  }SqList;

另外，由于排序最常用的操作是数组两元素的交换，我们将它写成函数

/*交换L中数组r的下标为i和j的值*/
void swap(SqList *L,int i,int j)
{
    int temp = L->r[i];
    L->r[i]=L->[j];
    L->r[j]=temp;
}

---

冒泡排序(Bubble Sort)

• 冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止

  冒泡实现在细节上可以有多种变化，我们将分别就3种不同的冒泡实现代码。

  /*对顺序表L作交换排序(冒泡排序初级版)*/
  void BubbleSort0(SqList *L)
  {
      int i,j;
      for(i=1;i<L->length;i++)
      {
          for(j=i+1;i<L->length;j++)
          {
              if(L->r[i] > L->r[j])
              {
                  swap(L,i,j);  
              }
          }
      }
  }

这段代码严格意义上，不算是标准的冒泡排序算法，因为它不满足两两比较相邻记录的冒泡排序思想，它更应该是最最简单的交换排序而已，而且效率很低

以下是正宗的冒泡排序

void BubbleSort(SqList *L)
{
    int i,j;
    for(i=1;i<L->length;i++)
    {
        for(j=L->length-1;j>=i;j--)  /*注意j是从后往前循环*/
        {
            if(L->r[j] > L->r[j+1])  /*若前者大于后者(注意与前者的差异)*/
            {
                swap(L,j,j+1);
            }
        }
    }
}

冒泡排序优化

/*对顺序表L作改进冒泡算法*/
void BubbleSort2(SqList *L)
{
    int i,j;
    Status flag=TRUE;  /*flag用来作为标记*/
    for(i=1;i<L->length && flag;i++)  /*若flag为false则退出循环*/
    {
        flag = FALSE;  /*初始为false*/
        for(j=L->length-1;j>=i;j--)
        {
            if(L->r[j] > L->r[j+1])
            {
                swap(L,j,j+1);
                flag=TRUE;  /*若有数据交换，则flag为true*/
            }
        }
    }
}

冒泡排序法复杂度分析，总时间复杂度为O(n^2^)

---

简单选择排序(Simple Selection Sort)

• 简单选择排序法就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和i个记录交换之

  void SelectSort(SqList *L)
  {
      int i,j;
      for(i=1;i<L->length;i++)
      {
          min = i;  /*将当前下标定义为最小值下标*/
          for(j=i+1;j<=L->length;j++)  /*循环之后的数据*/
          {
              if(L->r[min]>L->r[j])  /*如果有小于当前最小值的关键字*/
                  min=j;  /*将此关键字的下标赋值给min*/
          }
          if(i!=min)  /*若min不等于i，说明找到最小值，交换*/
              swap(L,i,min);  
      }
  }

简单选择排序复杂度仍然为O(n^2^)，尽管如此，但是性能上还是要略优于冒泡排序

---

直接插入排序(Straight Insertion Sort)

• 直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表

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

直接插入排序法的时间复杂度还是O(n^2^)，但是直接插入排序法比冒泡和简单选择排序的性能更好一些.

---

希尔排序(Shell Sort)

void ShellSort(SqList *L)
{
    int i,j;
    int increment=L->length;
    do
    {
        increment=increment/3 + 1;  /*增量序列*/
        for(i=increment+1;i<=L->length;i++)
        {
            if(L->r[i] < L->r[i-increment])
            {  /*需将L->r[i]插入有序增量子表*/
                L->r[0]=L->r[i];  /*暂存在L->r[0]*/
                for(j=i-increment;j>0 && L->r[0] < L->r[j];j-=increment)
                    L->r[j+increment]=L->r[j];  /*记录后移，查找插入位置*/
                L->r[j+increment]=L->r[0]  /*插入*/
            }
        }
    }
    while(increment>1);
}

“增量”的选取非常关键，需要注意增量序列的最后一个增量必须等于1才行

希尔排序的时间复杂度为O(n^3/2^)，终于突破了慢速排序的时代(超越了时间复杂度为O(n^2^)

---

堆排序(Heap Sort)

• 堆是具有下列性质的完全二叉树

1. 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
2. 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

   故根结点一定是堆中所有的结点的最大(小)者

   /*对顺序表L进行堆排序*/
   void HeapSort(SqList *L)
   {
       int i;
       for(i=L->length/2;i>0;i--)  /*把L中的r构建成一个大顶堆*/
           HeapAdjust(L,i,L->length);
           
       for(i=L->length;i>1;i--)
       {
           swap(L,1,i);  /*将堆顶记录和当前未经排序子序列的最后一个记录交换*/
           HeapAdjust(L,1,i-1);  /*将L->r[1..i-1]重新调整未大顶堆*/
       }
   }

弄清楚i的变化是在调整哪些元素后，可以看关键的HeapAdjust(堆调整)函数是如何实现的

/*已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义*/
/*本函数调整L->r[s]的关键字，使L->r[s..m]成为一个大顶堆*/
void HeapAdjust(SqList *L,int s,int m)
{
    int temp,j;
    temp=L->r[s];
    for(j=2*s;j<=m;j*=2)  /*沿关键字较大的孩子结点向下筛选*/
    {
        if(j<m && L->r[j] < L->r[j+1])
            ++j;  /*j为关键字中较大的记录的下标*/
        if(temp>=L->r[j])
            break;  /*rc应插入在位置s上*/
        L->r[s]=L->r[j];
        s=j;
    }
    L->r[s]=temp; /*插入*/
}

for(i=L->length;i>1;i--)
{
    swap(L,1,i);  /*将堆顶记录和当前未经排序子序列的最后一个记录交换*/
    HeapAdjust(L,1,i-1);  /*将L->r[1..i-1]重新调整为大顶堆*/
}

堆排序的时间复杂度为O(nlogn)，这在性能上显然要远远好过于冒泡，简单选择，直接插入的时间复杂度了

---

归并排序(Merging Sort)

void MergeSort(SqList *L)
{
    MSort(L->r,L->r,1,L->length);
}

/*将SR[s..t]归并排序为TR1[s..t]*/
void MSort(int SR[],int TR1[],int s,int t)
{
    int m;
    int 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..]*/
    }
}

/*将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]*/
void Merge(int SR[],int TR[],int i,int m,int n)
{
    int j,k,l;
    for(j=m+1,k=1;i<=m && j<=n;k++)  /*将SR中记录由小到大归并入TR*/
    {
        if(SR[i]<SR[j])
            TR[k]=SR[i++];
        else
            TR[k]=SR[j++];
    }
    if(i<=m)
    {
        for(l=0;l<=m-i;l++)
            TR[k+1]=SR[i+1]  /*将剩余的SR[i..m]复制到TR*/
    }
    if(j<=n)
    {
        for(l=0;l<=n-j;l++)
            TR[k+1]=SR[j+1];  /*将剩余的SR[j..n]复制到TR*/
    }
}

时间复杂度：一趟归并需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行(log2n)次，因此，总的时间复杂度为O(nlogn)，空间复杂度为O(n+logn)

非递归实现归并排序

/*对顺序表L作归并非递归排序*/
void MergeSort2(SqList *L)
{
    int* TR=(int*)malloc(L->length*sizeof(int));  /*申请额外空间*/
    int k=1;
    while(k<L->length)
    {
        MergePass(L->r,TR,k,L->length);
        k=2*k;  /*子序列长度加倍*/
        MergePass(TR,L->r,k,L->length);
        k=2*k;  /*子序列长度加倍*/
    }
}

从代码中，我们能感受到，非递归的迭代做法更加直接了当，从最小的序列开始归并直至完成，不需要像归并的递归算法一样，需要先拆分递归，再归并退出递归

/*将SR[]中相邻长度为s的子序列两两归并到TR[]*/
void MergePass(int SR[],int TR[],int s,int n)
{
    int i=1;
    int j;
    while(i <= n-2*s+1)
    {
        Merge(SR,TR,i,i+s-1,i+2*s-1);  /*两两归并*/
        i=i+2*s;
    }
    if(i<n-s+1)  /*归并最后两个序列*/
        Merge(SR,TR,i,i+s-1,n);
    else  /*若最后只剩下单个子序列*/
        for(j=1;j<=n;j++)
            TR[j]=SR[j];
}

非递归的迭代方法，避免了递归时深度为log2n的栈空间，空间只是用到申请归并临时用的TR数组，因此空间复杂度为O(n)，而且避免递归也在时间性能上有一定的提升，应该说，使用归并排序时，尽量考虑非递归方法。

---

快速排序(Quick Sort)

void QuickSort(SqList *L)
{
    QSort(L,1,L->length);
}

/*对顺序表L中的子序列L->r[low..high]作快速排序*/
void QSort(SqList *L,int low,int high)
{
    int pivot;
    if(low<high)
    {
        pivot=Partition(L,low,high);  /*将L->r[low..high]一分为二，算出枢轴值pivot*/
        QSort(L,low,pivot-1);  /*对低子表递归排序*/
        QSort(L,pivot+1,high);  /*对高子表递归排序*/
    }
}

Partition函数要做的，就是先选取当中一个关键字，然后想尽办法将它放到一个位置，使得它左边的值都比它小，右边值都比它大，我们将这样的关键字称为枢轴(pivot)

/*交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置*/
/*此时在它之前(后)的记录均不大(小)与它*/
int Partition(SqList *L,int low,int high)
{
    int pivotkey;
    pivotkey=L->r[low];  /*用子表的第一个记录作枢轴记录*/
    while(low<high)  /*从表的两端交替向中间扫描*/
    {
        while(low<high && L->r[high] >= pivotkey)
            high--;
        swap(L,low,high);  /*将比枢轴记录小的记录交换到低端*/
        while(low<high && L->r[low] <= pivotkey)
            low++;
        swap(L,low,high);  /*将比枢轴记录大的记录交换到高端*/
    }
    return low;  /*返回枢轴所在位置*/
}

在最优的情况下，快速排序算法的时间复杂度为O(nlogn)

证明过程了解一下

快速排序优化

1. 优化选取枢轴

• 三数取中(median-of-three)法，即选取三个关键字先进行排序，将中间数作为枢纽，一般是取左端，右端，中间三个数，也可以随机选取。这样至少这个中间数不会是最小或最大的数。

  故在Partition函数代码的第3行与第4行之间增加这样一段代码

  int pivotkey;
  int m = low + (high - low)/2;  /*计算数组中间的元素下标*/
  if(L->r[low] > L->r[high])
      swap(L,low,high);  /*交换左端与右端数据，保证左端较小*/
  if(L->r[m] > L->r[high])
      swap(L,high,m);  /*交换中间与右端数据，保证中间较小*/
  if(L->r[m] > L->r[low])
      swap[L,m,low];  /*交换中间与左端数据，保证左端较小*/
  /*此时L，r[low]已经为整个序列左中右三个关键字的中间值*/
  pivotkey = L->[low];  /*用子表的第一个记录作为枢轴记录*/

当然三数取中对小数组来说有很大的概率选择到一个比较好的pivotkey，但是对于非常大的待排序的序列来说还是不足以保证能够选出一个好的pivotkey，因此还有个方法叫九数取中(median-of-nine)

三次三数取中，然后再进行一次三数取中

2.优化不必要的交换

/*快速排序优化算法*/
int Partition1(SqList *L,int low,int high)
{
    int pivotkey;  //这里省略三数取中代码
    pivotkey = L->r[low];  /*用于表的第一个记录作枢纽记录*/
    L->r[0]=pivotkey;  /将枢纽关键字备份到L->r[0]/
    while(low<high)  /*从表的两端交替向中间扫描*/
    {
        while(low<high && L->r[high] >= pivotkey)
            high--
        L->r[low]=L->r[high];  /采用替换而不是交换的方式进行操作/
        while(low<high && L->r[low] <= pivotkey)
            low++;
        L->r[high]=L->r[low];  /采用替换而不是交换的方式进行操作/
    }
    L->r[low]=L->r[0];  /将枢纽数值替换回L.r[low]/
    return low;  /*返回枢轴所在位置*/
}

3.优化小数组时的排序方案

#define MAX_LENGTH_INSERT_SORT 7 /*数组长度阀值*/
/*对顺序表L中的子序列L.r[low..high]作快速排序*/
void QSort(SqList &L,int low,int high)
{
    int pivot;
    if((high-low)>MAX_LENGTH_INSERT_SORT)
    {/*当high-low大于常数时用快速排序*/
        pivot=Partition(L,low,high);  /*将L.r[low..high]一分为二，并算出枢轴值pivot*/
        QSort(L,low,pivot-1);  /*第低子表递归排序*/
        QSort(L,pivot+1,high);  /*对高子表递归排序*/
    }
    else  /*当high-low小于等于常数时用直接插入排序*/
        InsertSort(L);
}

如果数组小还不如直接插入排序来得更快(直接插入是简单排序中性能最好的)

4. 优化递归操作

我们对QSort实施尾递归优化

void QSort1(SqList *L,int low,int high)
{
    int pivot;
    if((high-low)>MAX_LENGTH_INSERT_SORT)
    {
        while(low<high)
        {
            pivot=Partition1(L,low,high);  /*L.r[low..high]一分为二，算出枢轴值*/
            QSort1(L,low,pivot-1);  /*对低子表递归排序*/
            low=pivot+1;  /*尾递归*/
        }
    }
    else
        InsertSort(L);
}

---

总结回顾

从算法的简单性来看，我们将7种算法分为两类：

1. 简单算法：冒泡，简单选择，直接插入
2. 改进算法：希尔，堆，归并，快速

• 从平均情况来看，最后3种改进算法要胜过希尔算法，并远远胜于前3种简单算法
• 从最好情况来看，反而冒泡和直接插入排序更胜一筹，也就是说，如果你的待排序序列总是基本有序，反而不应该考虑4种复杂的改进算法。
• 从最坏情况来看，堆排序和归并排序又强过快速排序以及其他简单排序。

---