数据结构排序算法笔记

排序

算法种类	最好情况	平均情况	最坏情况	空间复杂度	是否稳定
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	是
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	是
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	否
希尔排序		取决于间隔序列		O(1)	否
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(logn)	否
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	否
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	是
基数排序	O(d(n + r))	O(d(n + r))	O(d(n + r))	O(n + r)	是

---

插入排序

算法思想

• 算法思想: 每次将一个待排序的记录按其关键字大小插入到前面已排好的子序列中，直到全部记录插入完成。
  • 简单的说就是将要排序的前面的大于其的记录右移

算法实现

//直接插入排序
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];            //复制到插入位置
        
        }
}

• 空间复杂度:$O(1)$
• 时间复杂度: 主要来自对比关键字，移动元素。
  • 若有n个元素，则需要n-1趟处理
• 最好时间复杂度:
  • $O(n)$
• 最坏时间复杂度:
  • $O(n^{2})$
• 平均时间复杂度：$O(n^2)$ （最好和最坏加和取半）
• 算法稳定性:
  • 稳定

---

希尔排序

思想

• 希尔排序(Shell Sort)： 先追求表中元素部分有序，再逐渐逼近全局有序。

---

• 希尔排序: 先将待排序表分割成若干形如$L[i,i+d,i+2d,...,i+kd]$的特殊子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到$d=1$为止。

提示: 一般是缩小一半(但是考研五花八门)

算法实现

//希尔排序
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];        //暂存再A[0]
                for(j=i-d;j>0&&A[0]<A[j];j-=d)
                    A[j+d]=A[j];  //记录后移，查找插入的位置
                A[j+d]=A[0];      //插入
            }//if
}

算法性能分析

• 时间复杂度: 和增量序列$d_{1},d_{2},d_{3},...$的选择有关，目前无法用数学手段证明确切的时间复杂度，最坏时间复杂度为$O(n^{2})$，当n在某个范围内时，可达$O(n^{1.3})$

---

冒泡排序

原理

• 从后往前(或从前往后)两两比较相邻元素的值，若为逆序(即$A[i-1]>A[i]$)，则交换它们，直到序列比较完。称这样过程为一趟冒泡排序。

• 注意:

  • 如果某一趟排序过程中未发生交换，则算法可提前结束

算法实现

//交换(每次交换都要移动3次)
void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}

//冒泡排序
void BubbleSort(int A[],int n){
    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]){      //若为逆序
                swap(A[j-1],A[j]);//交换
                flag=true;
            }
        if(flag==false)
            return;    //本趟遍历后没有发生交换，说明表已经有序
    }
}

算法性能分析

• 空间复杂度:$O(1)$
• 冒泡排序是稳定的

---

快速排序

算法思想

• 算法思想: 在待排序表$L[1 ...n]$中任取一个元素pivot作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分$L[1 ...k-1]$和$L[k+1 ...n]$，使得$L[1 ...k-1]$中的所有元素小于pivot，$l[k+1 ...n]$中的所有元素大于等于pivit，则pivot放在了最终未知$L(k)$上，这个过程称为一次划分。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在其最终位置上。

代码实现

//用第一个元素将待排序序列划分成左右两个部分
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);             //划分右子表
    }
}

算法效率分析

• 空间复杂度 = O(递归层数)

• 时间复杂度:

  • 最好时间复杂度=$O(n\log_{2}n)$
  • 最坏时间复杂度=$O(n^{2})$

• 空间复杂度:

  • 最好空间复杂度=$O(\log_{2}n)$
  • 最坏空间复杂度=$O(n)$

• 排序情况:

  1. 最好: 每次选的枢轴元素都能将序列划分成均匀的两部分
  2. 最坏: 若序列原本就有逆序，则时间，空间复杂度最高
     • 可优化：尽量选择可以把数据中分的枢纽元素

• 稳定性: 快速排序是不稳定的

• 注:

  • 408原题中说，对所有尚未确定最终位置的所有元素进行一遍处理称为一趟排序，因此一次划分$\neq$ 一趟排序。
  • 一次划分可以确定一个元素的最终位置，而一趟排序也许可以确定多个元素的最终位置。

注意: 快速排序是所有内部排序算法平均性能最优的排序算法

---

简单选择排序

算法思想

• 选择排序： 每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列。
  • 注意: 两个相同元素，取先找到的

算法实现

//简单选择排序
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++)    //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
                min=j;            //更新最小元素位置
            if(min!=i)
                swap(A[i],A[min]);//封装的swap()函数共移动元素3次
    }
}

//交换
void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}

算法性能

• 稳定性: 不稳定
• 适用性: 既可以用顺序表，也可用链表

---

堆排序

算法思想

• 若n个关键字序列$L[1...n]$满足下面某一条性质，则称为堆(Heap)：
  1. 若满足：$L(i)\geq L(2i)$且$L(i)\geq L(2i+1)$，$(1\le i\le \frac{n}{2})$——大根堆(大顶堆)
  2. 若满足：$L(i)\le L(2i)$且$L(i)\le L(2i+1)$，$(1\le i\le \frac{n}{2})$——小根堆(小顶堆)

---

• 选择排序: 每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。

---

• 建立大根堆:
  • 思路:
    • 把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整。
  • 操作:
    • 检查当前结点是否满足：根$\geq$左右孩子，若不满足，将当前结点与更大的一个孩子互换。
      • i的左孩子—— 2i
      • i的右孩子—— 2i+1
      • i的父结点——$\lfloor \frac{i}{2}\rfloor$
    • 若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整（小元素不断下坠）

代码实现

• 过程: 先建堆，后排序

//建立大根堆
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次
  • 若树高为h，某结点在第i层，则将这个结点向下调整最多只需要下坠h-i层，关键字对比次数不超过2(h-i)
  • n个结点的完全二叉树树高$h=\lfloor\log_{2}n\rfloor+1$
• 推导：
  • 第i层最多有$2^{i-1}$个结点，而只有第$1\sim (h-1)$层的结点才有可能需要下坠调整
  • 将整棵树调整为大根堆，关键字对比次数不超过：

$$\sum\limits^{1}_{i=h-1}2^{i-1}2(h-i)=\sum\limits^{1}_{i=h-1}2^{i}(h-i)=\sum\limits^{h-1}_{j=1}2^{h-j}j\le 2n\sum\limits^{h-1}_{j=1}\frac{j}{2^{j}}\le 4n$$

• 结论: 建堆的过程，关键字对比次数不超过4n，建堆时间复杂度$O(n)$

• 稳定性: 堆排序是不稳定的
• 特点:
  • 基于大根堆的堆排序得到递增序列
  • 基于小根堆的堆排序得到递减序列

堆的插入删除

在堆中插入元素：

---

在堆中删除元素：

---

归并排序

算法思想

• 归并: 把两个或多个已经有序的序列合并成一个
  

• 结论: m路归并，每选出一个元素需要对比关键字m-1次

---

• 在内部排序中一般采用2路归并：
  

• 核心操作: 把数组内的两个有序序列归并为一个

代码实现

int *B(int *)malloc(n*sizeof(int));  //辅助数组B

//A[low...mid]和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++];
    }//for
    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); //对右半部份归并排序
        Merage(A,low,mid,high);  //归并
    }//if
}

算法效率分析

• 特点分析:

  • 2路归并的归并树—— 形态上就是一棵倒立的二叉树
  • 二叉树的第h层最多有$2^{h-1}$个结点，若树高为$h$，则应满足$n\le 2^{h-1}$，即$h-1=\lceil log_{2}n\rceil$

• 结论: n个元素进行2路归并排序，归并趟数$=\lceil log_{2}n\rceil$

• 时间复杂度:$O(n\log_{2}n)$

  • 每趟归并时间复杂度为$O(n)$

• 空间复杂度:$O(n)$，来自与辅助数组B

  • 递归所调用的空间不会超过$\log_{2}n$

---

基数排序

算法思想

• 假设长度为n的线性表中每个结点$a_{j}$的关键字由$d$元组$(k_{j}^{d-1},k^{d-2}_{j},k^{d-3}_{j},...,k_{j}^{1},k_{j}^{0})$组成，其中，$0\le k_{j}^{i}\le r-1(0\le j<n,0\le i\le d-1)$，$r$称为基数

• 基数排序得到递减序列的过程如下：

  • 初始化：设置r个空队列，$Q_{r-1},Q_{r-2},...,Q_{0}$
  • 按照各个关键字权重递增的次序（个，十，百），对d个关键字位分别做分配和收集
  • 分配：顺序扫描各个元素，若当前处理的关键字位$=x$，则将元素插入$Q_{x}$队尾
  • 收集：把$Q_{r-1},Q_{r-2},...,Q_{0}$各个队列中的结点依次出队并链接

• 注意: 基数排序不是基于比较的排序算法

• 基数排序具体操作:
  

算法效率分析

• 基数排序稳定性：
  

应用

• 基数排序擅长解决的问题:
  1. 数据元素的关键字可以方便地拆分为d组，且d较小
  2. 每组关键字的取值范围不大，即r较小
  3. 数据元素个数n较大

---