第八章-排序

8.1 排序的基本概念

• 可视化算法
• 排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程
• 算法的稳定性：key相同，排序时$R_j$在$R_i$之前，排序后仍然 --> 稳定

8.2 插入排序

1.直接插入排序 Insert Sort

• 
• 代码实现

void InsertSort(ElemType A[], int n) {
int i, j;
for (i = 2; i <= n; i++)    //A[2]到A[n]依次插入到前面已排序序列
    if (A[i] < A[i - 1]) {
        A[0] = A[i];    //哨兵
        for (j = i - 1; A[0] < A[j]; j--)   //从后往前查找待插入位置
            A[j + 1] = A[j];    //向后挪位
        A[j + 1] = A[0];    //复制到插入位置
    }
}

2.折半插入排序

• 
• 代码

void InsertSort(ElemType A[], int n) {
    int i;j;low;high;mid;
    for (i = 2; i <= n; i++) {    //依次将A[2]到A[n]插入前面已排序序列
      A[0] = A[1];    //A[i]暂存到A[0]
      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--){
        //把high后面的元素后移
          A[j+1] = a[j];
      }
      A[high+1] = A[0];
    }
}

3.希尔排序 Shell Sort （缩小增量排序）

• 
• 代码

void ShellSort(ElemType A[],int n)
{
  //A[0]是暂存单元；j<=0时，到达插入位置
  for (dk = n/2;dk >= 1;dk = dk/2)    //步长变换
    for(i = dk+1;i<=n;++i)
      if(A[i]<A[i-dk]){   //A[i]插入有序增量子表
        A[0] = A[i];    //暂存在A[0]
          for(j = i-dk;j>0&&A[0]<A[j];j-=dk)
            A[j+dk] = A[j];   //记录后移，查找插入的位置
          A[j+dk] = A[0];
      }
}

8.3 交换排序

4.冒泡排序 Bubble Sort

• 
• 代码

void BubbleSort (ElemType A[], int n)
{
  for(int i =0;i<n-1;i++)//趟数
  {
    flag = false;
    for(j = n-1;j>i;j--)    //一趟冒泡排序
      if(A[j-1]>A[j]){
        swap(A[j-1],A[j]);
        flag = true;
      }
      if(flag == false)
        return;
 }

5.快速排序 Quick Sort

• 
• 代码

void QuickSort(ElemType A[],int low,int high)
{
  if(low<high){
    int pivotpos = Partition(A,low,high);   //划分
    QuickSort(A,low,pivotpos);    //依次对子表递归
    QuickSort(A,pivotpos+1,high);
  }
}

int Partition(ElemType A[],int low,int high)
{
  //一趟划分
  ElemType pivot = A[low];    //左一元素为枢轴划分
  while(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;   //返回枢轴最终位置
}

8.4 选择排序

6.简单选择排序

• 
• 代码

void SelectSort(ElemType A[],int n)
{
  for(i=0;i<n-1;++i){   //n-1趟
    min = i;    //记录最小元素位置
    for(j = i+1;j<n;j++)
      if(A[j]<A[min]) min = j;
    if(min !=i) swap(A[i],A[min]);
  }
}

7.堆排序

• 

• 大根堆（大顶堆）

  • 根$\geq$左右

• 小根堆（小根堆）

  • 根$\leq$左右

• 代码

//建立大根堆
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];//将被筛选结点放入最终位置
}

8.5 归并排序和基数排序

8.归并排序 Merge Sort

• 
• 代码

ElemType *B = (ElemType *)malloc((n+1)*sizeof(ElemType))
void Merge(ElemType A[],int low,int mid,int high)
{
    //表的A[low...mid]和A[mid+1...high]各自有序
    for(int k=low;i<=high;i++)
      B[k]=A[k];    //A复制到B中
    for(int i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)
    {
        if(B[i]<B[j])   //比较B的左右两段
          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(a,mid+1,high);    //右划分
        Merge(a,low,mid,high);    //归并
    }
}

9.基数排序 Radix Sort

• 

8.6 各种内部排序算法的比较及应用

• 内部排序算法的比较

排序算法	空间效率	时间效率	稳定性	备注
插入排序	$O(1)$	最好$O(n)$ 平均$O(n^2)$ 最坏$O(n^2)$	稳定	比较依赖初始状态
折半插入排序	$O(1)$	最好$O(n)$ 平均$O(n^2)$ 最坏$O(n^2)$	稳定	比较次数约为 $O(n\log_2n​)$
希尔排序	$O(1)$	大约为 $O(n^{1.3})$	❌
冒泡排序	$O(1)$	最好$O(n)$ 平均$O(n^2)$ 最坏 $O(n^2)$	稳定
快速排序	最好$O(log_2n)$ 平均$O(log_2n)$ 最坏$O(n)$	最好$O(log_2n)$ 平均$O(log_2n)$ 最坏$O(n)$	❌	和划分是否对称有关 在所有内部排序算法中平均性能最优
简单选择排序	$O(1)$	$O(n^2)$	❌	与初始状态无关
堆排序	$O(1)$	$O(log_2n)$	❌
归并排序	$O(n)$	$O(log_2n)$	稳定
基数排序	$O(r)$	$O(d(n+r))$	稳定	r 为基数，d 为趟数，n 为元素个数

• 内部排序算法的应用 - 选取排序方法需要考虑的因素 - 排序算法小结

8.7 外部排序

• 
• 1.外部排序的基本概念
  • 将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换
• 2.外部排序的总时间 = 内部排序所需的时间 + 外存信息读写的时间 + 内部归并所需的时间

外部排序过程中的时间代价主要考虑访问磁盘的次数,即IO次数 为减少平衡归并中外存读写次数所采取的方法:增大归并路数和减少归并段个数

• 外部排序的方法
• 多路平衡归并与败者树
• 置换-选择排序（生成初始归并段）
• 最佳归并树