1、排序概述

排序就是将一组杂乱无章的数据按照一定的规律顺次排列起来，即将无序序列排成有序序列(由小到大或者由大到小)的运算。如果参加排序的数据包含多个数据域，那么排序往往是针对某一个数据域而言的。

排序方法的分类可以分为以下几类：

按照存储介质可以分为内部排序和外部排序，内部排序：数据量不大，数据在内存，无需内外存交换数据；外部排序：数据量比较大，数据在外存。外部排序是，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂的多。

按照比较器的个数可以分为：串行排序：单处理机，同一时刻比较一对元素；和并行排序，多处理机，同一时刻比较多对元素。

按照主要操作可以分为：比较排序，用比较的方法，如插入排序，交换排序，选择排序和归并排序等；基数排序，不比较元素的大小，仅仅根据元素本身的取值确定其有序位置。

按照辅助空间可以分为原地排序，辅助空间用量为  O(1)的方法，所占的辅助存储空间与参加排序的数据量大小无关；非原地排序，辅助空间用量超过O(1)的排序方法。

按照稳定性可以分为：稳定排序，能够使任何数值相等的元素，排序之后相对次序不变；非稳定排序，不是稳定排序的方法。排序的稳定性只对数据类型数据排序有意义，例如：

排序方法是否稳定，并不能衡量一个排序算法的优劣。

按照自然性可以分为：自然排序，输入数据越有序，排序的速度越快的排序方法；非自然排序，不是自然排序的方法。

2、插入排序

基本思想是：每一步将一个待排序的对象，按其关键码的大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。即边插入边排序，保证子序列中随时都是排好序的。

插入排序按照插入位置搜索的方法不同，可以分为以下几种类型：直接插入排序是使用顺序法定位插入位置；二分插入排序是使用二分法定位插入位置；希尔排序是使用缩小增量多遍插入排序。

2.1 直接插入排序

直接插入排序的流程如下图所示：

上述查找过程之中，每一次查找都要进行两次比较，即判断 j j j是否越界和比较值的大小，可以在序列的首部，0元素位置增加一个哨兵，从而无需进行越界判断：

直接插入排序的算法流程如下所示：

void InsertSort(SqList &L){
  for(int i = 2; i <= L.Length; ++i){
    if(L.r[i].key < L.r[i-1].key){
      L.r[0] = L.r[i];    //当前元素复制为哨兵
      for(int j = i-1; L.r[0].key < L.r[j].key; --j)
        L.r[j+1] = L.r[j];  //记录后移
      L.r[j+1] = L.r[0];    //插入到正确位置
    }
  }
}

算法复杂度分析：实现排序的基本操作有两个，“比较”序列中两个关键字的大小和“移动”记录。最好的情况下，关键在在记录序列中有序，比较的次数等于：∑i=2n1=n−1，移动的次数为0。最坏情况下，关键字在记录序列中逆序有序，则比较的次数为： ∑i=2n(i−1)=2n(n−1)，移动的次数为 ∑i=2n(i+1)=2(n+4)(n−1)。

顺序插入排序，原始数据越接近有序，排序速度越快。最好情况下，输入数据时逆有序的，时间复杂度为 O O(n2)，平均情况下，耗时差不多是最坏情况的一半。最好情况下的时间复杂度为 O(1)。空间复杂度为O(1)，是一个稳定的排序。

2.2 折半插入排序

查找插入位置时使用折半查找法，叫做折半插入排序。折半插入法的流程如下所示：

void BInsertSort(SqList &L){
  for(i = 2; i <= L.length; ++i){
    L.r[0]=L.r[i];//将当前需要插入的元素放到哨兵位置
    int low = 1, high = i-1;  //采用二分查找法查找插入位置
    while(low<=high){
      mid = (low+high)/2;
      if(L.r[0].key<L.r[mid].key)hight = mid-1;
      else low = mid + 1;
    }//循环结束时，high+1的位置则为插入位置
    for(int j = i-1; j >= high+1; --j) L.r[j+1]=L.r[j];
    L.r[high+1] = L.r[0];//插入到正确位置
  }
}

折半查找比顺序查找快，所以折半插入排序平均性能比直接插入排序快；并且折半插入排序所需要的关键码的比较次数与待排序的对象序列的初始排列无关，仅与对象个数有关。在插入第 i个对象时，需要经过 ⌊log2i⌋+1次关键码的比较，才能确定插入位置。在n比较大时，总关键码的比较次数比直接插入排序的最坏情况好得多，单比最好情况要差。若需要排序对象的初始排序已经基本有序了，则直接插入排序比折半插入排序的时间效率要高。

折半插入排序对象移动次数和直接插入排序相同，依赖于对象的初始排列；减少了比较次数，没有减少移动次数，平均性能优于直接插入排序。折半插入排序的时间复杂度为 O(n^2) ，空间复杂度为  O(1)，是一种稳定的排序方法。

2.3 希尔排序

在之前的直接插入排序和折半插入排序中，比较一次，只移动一步，希尔排序想要比较一次，移动一大步，从而减少移动的时间复杂度。希尔排序的基本思想：先将整个待排序的序列分割成若干个子序列，分别进行直接插入排序。待整个序列中的记录“基本有序”时，再对全体进行一次直接插入排序，所以希尔排序是一个缩小增量的多遍插入排序方法。希尔排序的思想如下所示：

首先呢定义增量序列Dk:DM>DM−1>,...,>D1=1，之后对每个Dk进行 Dk间隔插入排序，示意图如下所示：

希尔排序的增量序列应该是互为质数的。希尔排序的流程如下所示：

void ShellSort(SqList &L, int delta[], int t)
{
  //按照增量序列delta[0,...,t-1]对顺序表L作希尔排序
  for(int k = 0; k < t; ++k)
    ShellInsert(L,delta[k]);  //做一遍增量为delta[k]的插入排序
}
void ShellInsert(SqList &L, int dk){
  for(int i = dk+1; i <=L.length; ++i){
    if(L.r[i].key<L.r[i-dk].key){
      L.r[0]=L.r[i];
      for(int j = i-dk; L.r[0].key < L.r[j].key; j = j - dk){
        L.r[j+dk] = L.r[j];
      }
      L.r[j+dk] = L.r[0];
    }
  }
}

希尔排序的效率与增量序列的取值有关，

希尔排序是一种不稳定的排序算法。希尔排序的空间复杂度为  O(1)。希尔排序的最佳增量序列尚未解决，但增量序列的最后一个增量值必须为1，所有增量之间必须没有除了1之外的其他公因子，同时希尔排序不适宜在链式存储结构上实现。

3、交换排序

3.1 冒泡排序

冒泡排序数据交换排序的一种，交换排序的基本思想：两两比较，如果发生逆序则进行交换，直到所有记录都已经排好序为止。常见的交换排序方法：冒号排序 O(n2)，快速排序 O(nlongn)。

冒泡排序两两元素之间进行比较，若有n个元素，则需要比较n-1趟才能将所有的元素均排列成有序状态。第m趟需要比较n-m次。冒泡排序的流程如下所示：

void Bubble_sort(Sqlist &L)
{
  int n = L.length;
  for(int m = 0; m < n-1; ++m){//总共需要比较n-1趟
    for(int j = 0; j < n-m; ++j){//每一趟需要比较n-m次
      if(L.r[j] > L.r[j+1]){//进行比较
        RedType x = L.r[j];//交换
        L.r[j] = L.r[j+1];
        L.r[j+1] = x;
      }
    }
  }
}

一旦某一趟比较时没有出现元素交换，说明当前序列已经排好序了，就可以直接结束冒泡排序算法。基于这个思想，可以写出下述流程：

void Bubble_sort(Sqlist &L)
{
  int n = L.length;
  bool flag = true;
  for(int m = 0; m < n-1 && flag == true; ++m){//总共需要比较n-1趟
    flag = false;
    for(int j = 0; j < n-m; ++j){//每一趟需要比较n-m次
      if(L.r[j] > L.r[j+1]){//进行比较
        flag = true;
        RedType x = L.r[j];//交换
        L.r[j] = L.r[j+1];
        L.r[j+1] = x;
      }
    }
  }
}

冒泡排序的时间复杂度，最好的情况下(序列本来就是正序的)，需要比较次数为n-1，无需进行移动，这时间复杂度为O(n)。最坏情况下(序列本来是逆序的)，需要比较的次数为 ∑i=1n−1(n−i)=21(n2−n)，移动次数为：发现一次比较逆序就要进行一次交换移动，需要3次赋值，所以移动次数为：3∑i=1n−1(n−i)=23(n2−n)，所以冒泡排序最坏的时间复杂度为：O(n2)。冒泡排序需要额外用到一个辅助空间，所以空间复杂度为 O(1)，冒泡排序是一种稳定的排序。

3.2 快速排序

快速排序的基本思想是一种递归的思想，首先在序列中任意选取一个元素，如第一个作为中心(pivot)；之后将所有比中心元素小的元素放到它前面，将所有比中心元素大的元素放到它后面，这样形成两个子表；之后对于各个子表再重新选择中心元素并依据上述规则进行调整，直到每个子表的元素只剩一个。

交换排序比较重要的部分是寻找中间点pivot的位置，寻找中间点位置的方法是从两头到中间的交替式逼近法：

之后对于每个子表的操作可以采用递归的算法。快速排序算法的流程如下所示：

void main(){
  Qsort(L, 1, L.length);
}
void QSort(SqList &L, int low, int high){
  if(low < high){//若表长大于1
    pivotLoc = Partition(L, low, high);//寻找pivot的位置，将表一份为二
    QSort(L, low, pivotLoc - 1);  //对低子表进行递归排序
    QSort(L, pivotLoc - 1, high); //对高子表进行递归排序
  }
}
int Partition(SqList &L, int low, int high){
  L.r[0] = L.r[low];
  int povotKey = L.r[low].key;
  while(low<high){
    while(low<high && L.r[high].key >= pivotKey) --high;//找一个小于中心点的值从后往前搬
    L.r[low] = L.r[hgih];
    while(low<high && L.r[low] <= pivotKey) ++low;//找一个大于中心点的值从前往后搬
    L.r[high] = L.r[low];
  }
  L.r[low] = L.r[0];
  return low;
}

快速排序的时间复杂度为  O(nlog2n)，其中，递归调用的算法复杂度为O(log2n)，寻找中心点的时间复杂度为  O(n)，快速排序是内排序算法中最好的一个。

快速排序不是原地排序，因为快速排序使用了递归的思想，需要调用系统栈的支持，栈的长度取决于递归调用的深度，在平均情况下需要  O(logn)的栈空间，最快情况下，栈空间可以达到 O(n)。快速排序是一种不稳定的排序方法。

快速排序不适用于对原本有序或者基本有序的记录序列进行排序，这样的序列会使得快速排序的效率近似退化称为冒泡排序。划分元素的选取是影响快速排序时间性能的关键，输入数据的次序越乱，所选划分元素值的随机性越好，排序速度越快，所以快速排序不是自然排序的方法。改变元素的选取方法，最多只能改变算法平均情况下的时间性能，不能改变最坏情况下的时间性能，最坏情况下，快速排序的时间复杂度总是  O(n2)。