# 排序算法分类

规则不同可以分为:插入排序、交换排序、选择排序、归并排序、基数排序
时间复杂度不同:简单排序O(n^2)、先进排序O(nlog2^n)

# 插入排序

基本思想:
每一步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。
即边插入边排序,保证子序列中随时都是排好序的
具体实现的三种不同算法:
直接插入排序(基于顺序查找) | 最简单的排序法
折半插入排序(基于折半查找)
希尔排序(基于逐趟缩小增量)

# 1️⃣直接插入排序

排序过程:整个排序过程为n-1趟插入,即先将序列中第1个ynvirhf成是一个有序序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。

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[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(n^2)
空间复杂度:O(1)
是一种稳定的排序方法

# 2️⃣折半插入排序

在插入r[i]时,利用折半查找法寻找r[i]的插入位置

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 >= height + 1; --j){
      L.r[j+1]=L.r[j];
      L.r[right + 1] = L.r[0];
    }
  }
}

折半插入排序算法分析
减少了比较次数,但没有减少移动次数
平均性能优于直接插入排序
时间复杂度为O(n^2)
空间复杂度为O(1)
是一种稳定的排序方法

# 3️⃣希尔排序

算法思想的出发点:
直接插入排序在基本有序时,效率较高
在待排序的记录个数较少时,效率较高
基本思想:
先将整个待排序记录序列分割成若干子序列,分别进行直接插入排序,待整个序列中的记录”基本有序“时,再对全体记录进行一次直接插入排序
希尔排序技巧:
子序列的构成不是简单地”逐段分割“
将相隔某个增量dk的记录组成一个子序列
让增量dk逐趟缩短(例如依次取5,3,1)
直到dk=1为止
😄优点:
小元素跳跃式前移
最后一趟增量为1时,序列已基本有序
平均性能优于直接插入排序

sort

希尔排序算法主程序

void ShellSort(SqList &L, int dlta[], int t){ // dk的值依次装在dlta中
  // 按增量序列dlta[0...t-1]对顺序表L作shell排序
  for(k=0;k<t;++k){
    ShellInsert(L,dlta[k]); // 增量为dlta[k]的一趟排序
  }
}

void ShellInsert(SqList &L, int dk){
  for(i=dk+1;i <=L.length;++i){
    if(L.r[i].key < L.r[i-dk].key){
      L.r[0]=L.r[i]; // 暂时存在r[0]
      for(j=i-dk;j>0&&(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];
    }
  }
}

算法分析: 时间复杂度是n和d的函数: O(n^1.25)~O(1.6n^1.25)--经验公式
空间复杂度O(1)
是一种不稳定的排序算法
如何选择d序列,目前尚未解决
最后一个增量值必须为1,无除1以后的公因子
不宜在链式存储结构中实现

# 交换排序

基本思想:
两两比较,如果发生逆序则交换,直到所有记录都排好序为止。

# 1️⃣起泡排序O(n^2)

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].key;
        L.r[j].key=L.r[j+1].key;
        L.r[j+1].key=x;
      }
    }
    m--;
  }
}

算法分析:
设对象个数为n
比较次数和移动次数与初始排列有关
最好的情况下:
只需1趟排序,比较次数为n-1,不移动 最坏的情况下:
时间复杂度为O(n^2)
空间复杂度为O(1) 是一种稳定的排序方法

# 2️⃣快速排序O(nlog2^n)

基本思想:
取一个元素(如第一个)为中心
所有比它小的一律放前,比它大的一律放后,形成的左右两个子表;
对各子表重新选择中心元素并依此规则调整,直到每一个子表的元素只剩一个
快速排序的特点:

  1. 每一趟的子表的形成采用从两头向中间交替式逼近法
  2. 由于每趟中对各子表的操作都相似,可以采用递归算法
void main(){
  Qsort(L,1,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[right];
    while(low< high && L.r[low].key <= pivotkey){
      ++low;
    }
    L.r[high] = L.r[low];
  }
  L.r[low]=L.r[0];
  return low;
}

算法分析:
平均计算时间是O(nlog2n)
实验结果表明:就平均计算时间而言,是我们所讨论的所有内部排序方法中最好的一个。
快速排序是递归的,需要有一个栈存放每次递归调用时的参数(新的low和high)
最大递归调用层次数与递归树的深度一致。因此要求存储开销O(nlog2n)
最好:划分后,左右侧子序列长度相同
最坏:从小到大排序,递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列,必须经过n-1趟才能把所有的对象定位,而且第i趟需要经过n-1次关键码比较,才能找到第i个对象的安放位置
快速排序算法分析:
时间效率:O(nlog2n) 每一趟确定的元素程指数增加
空间效率:O(nlog2n) 递归要用到的栈空间
稳定性:不稳定 可选任意元素为支点

# 选择排序

基本思想:
每一趟在后面n-i+1中,选中关键码最小的对象,作为有序序列的第i个记录,简单选择排序示例

# 简单选择排序:

void selectSort(SqList &L){
  for(i = 1;i < L.length; i++){
    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^2)
空间复杂度:O(1) 稳定性:稳定

# 堆排序

如果将序列看成一个完全二叉树,非终端结点的值均小于或大于左右子结点的值。
大顶堆的排序思想: 大顶堆顶点是最大的值,把顶点拿出来和完全二叉树最后一个结点进行交换,把除掉这个节点之外的节点重新调整成大顶堆。
如何在输出堆顶元素后调整,使之成为新堆?

  1. 输出堆顶元素后,以堆中最后一个元素替代之
  2. 大顶堆排序时将根结点与左、右子树根结点比较,并与最大者交换
  3. 重复直至叶子节点,得到新的堆
heap

# 归并排序 (二路归并)

归并:将两个或两个以上的有序表组合成一个新的有序表
2路归并排序过程:
初始序列看成n个有序子序列,每个子序列长度为1
两两合并,得到[n/2]个长度为2或1的有序子序列
再两两合并,重复直至得到一个长度为n的有序序列为止
时间复杂度:O(nlog2n)
空间效率:O(n)
稳定性:稳定

# 基数排序

前面的排序方法主要通过关键字值之间的比较和移动,基数排序不需要关键字之间的比较
关键字排序:

  1. 最高位优先MSD(Most Significant Digit first)
  2. 最低位优先LSD(Least Significant Digit first)
  3. 链式基数排序:用链表作存储结构的基数排序

# 方法1️⃣:最高位优先法

先对最高位关键字k1(如花色)排序,将序列分成若干子序列,每个子序列有相同的值:
然后让每个子序列对次关键字k2(如面值)排序,又分成若干更小的子序列:
最高位优先法
依次重复,直至就每个子序列对最低位关键字kd排序,就可以得到一个有序的序列
十进制数比较可以看作是一个多关键字排序
最高从头再来优先法,如果位数不足可以往前补0
用MSD关键字序列排序
{278,109,063,064,930,589,184,505,269,008,083}
按最高位排序
{063,064,008,083},{109,184},{278,269},{589,505},{930}
最次高位排序
{008},{063,064},{083},{109},{184},{269},{278},{505},{589},{903}
按最低位排序
{008},{063},{064},{083},{109},{184},{269},{278},{505},{589},{903}
最后将所有的子序列依次链接在一起就得到排好的序列

# 方法2️⃣:最低位优先法

首先依据最低位排序码Kd对所有对象进行一趟排序再依据次低位排序码Kd-1对上一次排序结果排序依次重复,直到依据排序码K1最后一趟排序完成,就可以得到一个有序序列。
这种方法不需 要再分组,而是整个对象组都参加排序
最低位优先法
278,109,063,930,184,589,269,008,083
按个位排序
930,063,083,184,278,008,109,589,269
按十位排序
008,109,930,063,169,278,083,184,589 按百位排序
008,063,083,109,169,184,278,589,930

# 方法3️⃣:链式基数排序

先决条件:
-- 知道各级关键字的主次关系 -- 知道各级关键字的取值范围
利用”分配“和”收集”对关键字进行排序:
首先对低位关键字排序,各个记录按照此位关键字的值“分配”到相应的序列里。
按照序列对应的值的大小,从各个序列中将记录“收集”,收集后的序列按照些位关键字有序。
算法分析
n个记录,每个记录有d位关键字,关键字取值范围rd(如十进制为10)。重复执行d趟“分配”与”收集“,每趟对n个记录进行“分配”,对rd个队列进行“收集”
需要增加n+2rd个附加链接指针
链式基数排序算法分析:
时间效率:O(d(n+d)) 空间效率:O(n+rd)
稳定性:稳定
排序算法比较

heap