数据结构第八章排序

2023-03-11

字数统计: 3.3k | 阅读时长≈ 13 分钟

系列链接
第一章概述	第二章线性表	第三章栈与队列	第四章串
第五章树与二叉树	第六章图	第七章查找	第八章排序

🔥基本概念

排序稳定性：序列中两个相同关键字的元素在排序之后，之前在左边的关键字还在左边，右边的还在右边，即相对位置不变，这就是稳定的排序
不稳定的排序不一定比稳定的排序算法差，这取决于需求
排序分为内部排序（数据都在内存中）和外部排序（数据很多无法都放在内存里）。内部排序追求时间复杂度和空间复杂度低，外部排序追求磁盘读写次数少

🔥内部排序

✍插入排序

思路：依次将待排序的数据（记录）按关键字大小插入到之前已经排好序的子序列当中。是以类似顺序查找的方式插入

//直接插入排序
void InsertSort(int A[],int n){
  int i,j,temp;
  for(i=1;i<n;i++)        //各元素前插到已经排好序的序列中
    if(A[i]<A[i-1]){      //若A[i]关键字小于前驱
      temp=A[i];      //temp暂存A[i]
      for(j=i-1;j>=0 && A[j]>temp;--j)      //检查所有前面已经排好的元素，倒查保证稳定性
        A[j+1]=A[j];      //所有大于temp的元素向后挪
      A[j+1]=temp;      //复制到插入的位置
    }
}
//直接插入排序（带哨兵）
void InsertSort(int A[],int n){
  int i,j;
  for(i=2;i<=n;i++)        //依次将A[2]到A[n]前插到已经排好序的序列中
    if(A[i]<A[i-1]){      //若A[i]关键字小于前驱，将A[i]插入有序表
      A[0]=A[i];      //复制为哨兵，A[0]不存放元素
      for(j=i-1;A[0]<A[j];--j)      //向前查找待插入的位置
        A[j+1]=A[j];      //向后挪
      A[j+1]=A[0];      //复制到插入的位置
    }
}

优化——折半插入排序，前插的时候进行类似折半查找地判断然后插入，提高效率

void InsertSort(int A[],int n){
  int i,j,low,high,mid;
  for(i=2;i<=n;i++){
    A[0]=A[i];
    low=1;high=i-1;
    while(low<=high){
      mid=(low+high)/2;     //中间点
      if(A[mid]>A[0])   high=mid-1;   //查左半边
      else low=mid+1;     //查右半边
    }
    for(j=i-1;j>=high+1;--j)
      A[j+1]=A[j];      //后移
    A[high+1]=A[0];
  }
}

可以对链表进行插入排序，操作指针比较多，时间复杂度差不多

✍希尔排序

（ShellSort）思路：先实现局部的有序，再逐步逼近完全有序
先将排序表分割成若干个子表L[i,i+d,i+2d,…,i+kd]（每个子表都是原序列的等间隔元素），对每个子表进行插入排序。然后缩小d，如此往复直到d=1为止

举例如下（蓝色是未排序，绿色已排序）：

第二趟d由4变2：

最后一趟就结束：

//希尔排序
void ShellSort(int A[],int n){
  int d,i,j;
  //A[0]是暂存单元，不是哨兵，j<=0时插入位置已到
  for(d=n/2;d>=1;d=d/2)   //步长变化
    for(i=d+1;i<=n;++i)
      if(A[i]<A[i-d]){    //需要将A[i]插入有序增量子表
        A[0]=A[i];      //暂存
        for(j=i-d;j>0 && A[0]<A[j];j-=d)
          A[j+d]=A[j];        //数据后移，查找插入位置
        A[j+d]=A[0];      //插入
      }
}

希尔排序时间复杂度和d有关，但是最差也能和插入排序齐平，是一个不稳定的排序算法，仅适用顺序表

✍交换排序

基于交换的排序

冒泡排序

属于交换排序。思路：按顺序（从前往后或者从后往前）进行两两比较和交换（逆序时交换），直到任意两个元素都比较完（排列组合）。c语言入门的重点算法，就不用过多叙述。

void BubbleSort(int A[],int n){
  int temp;       //交换的中间变量
  for(int i=0;i<n-1;i++){
    bool flag=false;    //是否发生交换
    for(int j=n-1;j>i;j--)    //一趟冒泡
      if(A[j-1]>A[j]){    //若逆序
        temp = A[j-1];
        A[j-1] = A[j];
        A[j] = temp;
        flag = true;
      }
    if(flag==false)
      return;       //本趟遍历后没有交换，就说明已经有序，可以提早结束
  }
}

冒泡排序是稳定的，也可以用于链表

快速排序

也属于交换排序，是一种性能很好的排序
思路：进行多次划分，每次划分选择一个元素（枢轴元素，一般从头开始）将其他元素中比它大（或等）的放在一边，比它小的放在另一边，就能直接确定该元素的准确位置。
举例如下：选择第一个元素，low和high两个指针放在两边，逐步向中间移动，随着元素位置划分，空位不断发生变化
最后low和high重合，这个空位就是该元素的最终位置
最后该枢轴元素左右各产生了一个子表，继续对两个表分别重复上述操作，最后就能实现排序

//用一个元素将待排序的序列分为左右两个部分
int Partition(int A[],int low,int high){
  int pivot=A[low];       //第一个元素作为枢轴
  while(low<high){      //用low、high搜索枢轴最终位置
    while(low<high && A[high]>=pivot) --high;
    A[low]=A[high];     //比枢轴小的元素移动到左端
    while(low<high && A[low]<=pivot)  ++low;
    A[high]=A[low];     //比枢轴大的元素移到右端
  }
  A[low]=pivot;       //枢轴元素存放的最终位置
  return low;
}
//快速排序
void QuickSort(int A[],int low,int high){
  if(low<high){   //递归跳出的条件
    int pivotpos=Partition(A,low,high);   //划分
    QuickSort(A,low,pivotpos-1);    //划分左子表
    QuickSort(A,pivotpos+1,high);   //划分右子表
  }
}

快速排序如果没次划分都能分出很均匀的左右子表，那么效率将最高，原本就已经排好序的序列反而是最费时的情况
因此想要优化算法，就可以在头中尾选出三个数，取其中中间值作为枢轴，很大程度地避免选到极端的值
快速排序是不稳定的

✍选择排序

每步都找到未排序序列中的最值进行排序。

简单选择排序

属于选择排序，思路：在每趟排序中选择最小的值放到前面的有序序列。方法很简单清晰

void SelectSort(int A[],int n){
  for(int i=0;i<n-1;i++){   //一共n-1趟
    int min=i;    //记录最小元素位置
    for(int j=i+1;j<n;j++)      //在后面未排序的元素选择最小的
      if(A[j]<A[min])   min=j;      //更新最小元素的索引
    if(min!=i)   swap(A[i],A[min])；    //交换函数
  }
}

简单选择排序适用于顺序表和链表，是不稳定的

堆排序

也属于选择排序
堆（heap）：

大根堆：完全二叉树中所有子树的根结点都大于其左右孩子
小根堆：完全二叉树中所有子树的根结点都小于其左右孩子

显然排成堆的形式就很容易排序。所以堆排序的思想就是把序列先变成堆，然后进行排序。
基于大根堆进行排序的步骤：

将序列排成完全二叉树，对其中索引小于n/2的元素（非终端结点）进行判断，若有不符合大根堆条件的根结点，则将其与更大的那个孩子对换位置。如此往复
上面的小元素下沉之后可能破坏下面的大根堆结构，只要再多次重复，让小元素下沉到应该的位置。最终获取到大根堆
接着，每趟将堆顶元素放到排好的有序子序列，并将待排序元素序列再进行1、2操作形成大根堆。如此往复，大根堆缩小，直到全部完成

//建立大根堆
void BuildMaxHeap(int A[],int len){
  for(int i=len/2;i>0;i--)      //从后往前调整所有非终端结点
    HeadAdjust(A,i,len);
}
//将以k为根的子树调整成大根堆
void HeadAdjust(int A[],int k,int len){
  A[0]=A[k];        //A[0]暂存子树根结点
  for(int i=2*k;i<=len;i*=2){   //沿key较大的子结点向下筛选
    if(i<len && A[i]<A[i+1])
      i++;                    //取key大的子结点下标
    if(A[0]>=A[i])  break;    //筛选接束
    else{
      A[k]=A[i];        //A[i]调整到父结点
      k=i;            //修改k值，以便继续向下筛选
    }
  }
  A[k]=A[0];      //筛选的结点值放入最终位置
}
//堆排序
void HeapSort(int A[],int len){
  BuildMaxHeap(A,len);    //初始化堆
  for(int i=len;i>1;i--){   //n-1趟的交换和建堆过程
    swap(A[i],A[1]);      //堆顶元素和堆底互换
    HeadAdjust(A,1,i-1);      //剩余待排序元素整理成堆
  }
}

堆排序看似操作繁琐复杂，但是时间复杂度很低，空间复杂度只有常数级。
堆排序是不稳定的

✍归并排序

归并：把两个有序序列合并成一个
思路（以2个序列为例）：对于两个有序序列，对比最小值的大小，将小的放入最终序列。继续对比新的两个最小值，如此往复即可。当其中一个序列空了，可以将剩下的序列整个丢进最终序列。完成排序
上述方法称为2路归并，即将两个序列归并。多路归并需要比较多个关键字
对于一个初始序列，可以一次将元素两两归并，对新的子序列再两两归并，直到全部归并。如下：

int *B=(int *)malloc(n*sizeof(int));    //辅助数组B
//A[low...high]和A[mid+1...high]各自有序，将其归并
void Merge(int A[],int low,int mid,int high){
  int i,j,k;
  for(k=low;k<=high;k++)
    B[k]=A[k];        //将A中所有元素复制到B
  for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){
    if(B[i]<=B[j])
      A[k]=B[i++];    //将较小值复制到A
    else
      A[k]=B[j++];
  }
  while(i<=mid)     A[k++]=B[i++];
  while(j<=high)    A[k++]=B[j++];
}
//递归思想归并排序
void MergeSort(int A[],int low,int high){
  if(low<high){
    int mid=(low+high)/2;   //从中间划分
    MergeSort(A,low,mid);   //从左半部分归并排序
    MergeSort(B,mid+1,high);   //从右半部分归并排序
    Merge(A,low,mid,high);    //归并
  }
}