排序

算法的稳定性：若序列中含两相同关键字，在对序列排序之后，这两关键字的相对位置保持不变，则称该算法稳定，反之不稳定

插入排序

算法思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中的合适位置，该位置要求左侧关键字全部小于待插入关键字，右侧关键字全部大于该关键字，直到全部记录插入完成。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


//不带哨兵的实现方式，带哨兵的话可以不用使用temp变量，用a[0]暂存数据
void InsertSort(int *a,int n){
      int i,j,temp;
      for(i=1;i<n;i++){
          if(a[i]<a[i-1]){
              temp=a[i];
              for(j=i-1;j>=0&&a[j]>temp;--j){  //所有大于temp的元素向后挪位
                  a[j+1]=a[j];
              }
              a[j+1]=temp;
          }
      }
  }

空间复杂度O(1)
最好情况：时间复杂度O(n)，共n-1次处理，每次只需要对比关键字一次不用移动元素
最坏情况:时间复杂度为O(n^2^)
算法稳定性：稳定

优化—-折半插入排序

先用折半查找找到应该插入的位置，再移动元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


//带哨兵实现
void  InsertSort(int *a, int n){
    int i,j,high,mid,low;
    for(i = 2;i<=n;i++){
        a[0] = a[i];
        low = 1;
        high = i-1;
        while(low<=high){
            mid = (high-low)/2;
            if(a[mid]>a[0]) high = mid-1; //a[mid]过大，在mid左半区间查找
            else low = mid+1; //如果a[mid]==a[0]，则为了保证稳定性，仍应在mid右半区间查找
        }
        for(j = i-1;j>=high+1;j--){
            a[j+1] = a[j];
        }
        a[high+1] = a[0];
    }
}

希尔排序

先将待排序表分割成若干形如$L[i,i+d,i+2d,…,i+kd]$的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1。
- 希尔本人建议每次将增量d缩小至其一半
最后进行一次插入排序即可完成整个流程。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void ShellSort(int *a,int n){
    int d,i,j;
    for(d=n/2;d>=1;d/=2){ //每一趟排序使增量d减小一半
        for(i=d+1;i<=n;++i){
            if(a[i]<a[i-d]){
                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];
            }
        }
    }
}

当n在某个范围内时，时间复杂度可达O(n^1.3)，最坏时间复杂度为O(n^2^)
稳定性：不稳定
不适用于链表

冒泡排序

从后往前(或者反过来)两两比较相邻元素的值，若为逆序(A[i-1]>A[i])，则交换他们，直到序列比较完。

每一趟排序使得最小、次小、更小。。。的元素向前“冒泡”

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void bubbleSort(int *a,int n){
    bool flag = false;
    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 ; //第一轮比较，没有元素交换，说明已经有序，直接返回
    }
}

最好情况(有序)：时间复杂度为O(n)，交换次数=0，比较次数为n-1
最坏情况(逆序)：时间复杂度为O(n²)，
算法稳定
顺序表，链表通用

快速排序

基于分治法思想：

待排序表L[1…n]中任取一个元素pivot作为枢轴(一般为首元素)，
通过一趟排序将表分为两个子表，一个表中所有元素小于pivot，另一个表中所有元素大于pivot，则称该pivot元素达到了最终位置，该过程称为一次快排/划分
递归地对两个子表重复上述过程，直到每部分只剩下一个元素或为空为止，此时所有元素达到了最终位置，整个表完成排序

在408考题中，对所有尚未确定最终位置的所有元素进行一遍处理称为“一趟”排序，故一趟排序包括多次划分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


//递归算法实现，需要接收low和high来定位每次递归的区间
void quickSort(int *a,int low, int high){
    if(low<high){
        //Partition()函数用于一次划分，返回枢轴pivot的最终位置
        int pivotpos = Partition(a,low,high); //划分
        quickSort(a,low,pivotpos-1); //递归枢轴左半区间
        quickSort(a,pivotpos+1,high); //递归枢轴右半区间
    }
}
//教材写法
//注意++i与i++的不同，++i先自增再使用i，i++先使用再自增
int Partition(int *a,int low,int high){
    int pivot = a[low]; 数组首元素作为枢轴
    while(low<high){
        while(low<high && a[high]>=pivot) --high; //找到比pivot小的元素下标
        a[low] = a[high]; //把小元素交换到左端
        while(low<high && a[low]<=pivot) ++low; //找到比pivot大的元素下标
        a[high] = a[low]; //把大元素交换到右端
    }
    //此时low == high，pivot元素达到最终位置，存入数组
    a[low] = pivot;
    return low; //返回pivotpos
}
//或者我们也可以这么写，i++的写法
int partition(vector<int> &test, int low, int high) {
  int pivot_pos = low; //记录枢轴下标
  int pivot = test[pivot_pos]; //记录枢轴元素
  while (low < high) { //反复交换，直到数组内所有比枢轴元素小的排在枢轴左边，大的排在枢轴右边
    while (low < high && test[high] >= pivot) high--; //移动指针到第一个比枢轴小的元素
    while (low < high && test[low] <= pivot) low++;  //移动指针到第一个比枢轴大的元素
    if (high > low) {
      swap(test[low], test[high]); //交换元素
    }
  }
  swap(test[low], test[pivot_pos]); //找到枢轴元素最终位置，交换元素
  return low; //返回枢轴元素下标用于下一步递归左右子表
}

算法的时间复杂度与递归层数相关，其时间复杂度为O(n*递归层数），最好为O(nlog₂n)，最坏为O(n²)
空间复杂度同理，与递归层数直接相关，为O(递归层数)，最好为O(log₂n)，最坏为O(n)

时间复杂度简单判断：每次枢轴将表等分为长度相近的子表时，速度最快

若每一次选中的“枢轴”将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高。

而原序列原本就有序或逆序则为最坏情况。

该算法不稳定
优化思路：尽量选择可以把数据中分的pivot元素—–头/中/尾三个位置或者随机选择

简单选择排序

每一趟在待排序元素中选择关键字最小的元素加入有序子序列。

1
2
3
4
5
6
7
8


void selectSort(int *a, int n){
    int min = i;
    for(int j=i+1;j<n;j++){ 		//进行n-1次比较
        if(a[j]<a[min]) min = j;    //记录最小元素位置
    }
    if(min!= i) swap(a[i],a[min]); 
    
}

该算法不稳定，顺序表/链表均适用。

堆排序

可以从二叉树的顺序存储来理解大根堆与小根堆概念

满足下述两个条件其中之一的序列，称为堆：

$l(i) \geq l(2i)且l(i)\geq l(2i+1)$，称为大根堆
$l(i) \geq l(2i)且l(i)\geq l(2i+1)$，称为小根堆

从逻辑视角看，该序列为完全二叉树，可以看出父节点都要大于两个子节点，为大根堆，反之为小根堆

建立大根堆

思路：把所有非终端节点都检查一遍，是否满足大根堆的要求，如果不满足则进行调整

如果不满足，则将当前节点与更大的一个孩子互换($i的左孩子为2i，右孩子为2i+1，父节点\lfloor i/2 \rfloor$)

在顺序存储的完全二叉树中，非终端节点编号为$i \leq [n/2]$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


void buildMaxHeap(int a[], int len){
    for(int i=len/2;i>0;i--){
        headAdjust(a,i,len);
    }
}
void headAdjust(int a[],int k, int len){
    a[0] = a[k]; //暂存父节点值
    for(int i = 2*k;i<=len;i*=2){ //沿key值较大的子树向下筛选
        if(i<len&&a[i]<a[i+1]){ //取孩子中较大key值的下标
            i++; 
        }
        if(a[0]>=a[i]) break; //满足大根堆条件，退出
        else{
            a[k] = a[i]; //将孩子节点调整到父节点上
            k = i; //修改k值，准备检查调整后的子树是否破坏大根堆条件
        }
    }
    a[k] = a[0] //被筛选的结点抵达了最终位置
}

大根堆排序

建立大根堆以后：

堆顶元素就是该序列最大值，输出
将序列最后一个结点作为堆顶元素，重新进行调整
重复上述步骤直到树空

一个结点每下坠一层，最多只需要比较两次关键字

若树高为h，结点在i层则该节点向下最多下坠n-i层，即对比不超过2(h-i)次

完全二叉树的树高$h=\lfloor log_{2}n\rfloor+1$

1
2
3
4
5
6
7


void heapSort(int a[], int len){
    buildMaxHeap(a,len); //建堆需要O(n)时间复杂度
    for(int i = len;i>1;i--){  //调整需要O(nlog2n)时间复杂度
		swap(a[i],a[i]);
        headAdjust(a,1,i-1);
    }
}

堆排序总时间复杂度=O(n)+O(nlog₂n)=O(nlog₂n)

堆排序算法不稳定

堆的删除与插入

插入：对于小根堆，新元素放入表尾，与父节点对比，若新元素比父节点更小，则二者互换。新元素一路“上升”，直到无法继续。

删除：对于小根堆，用堆底元素替代被删除的元素，然后让该元素不断下坠，直到无法继续。

归并排序

把两个或多个有序的序列合并成一个

m路归并每次对比m-1次关键字
在内部排序中一般采用2路归并

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


int *b = (int*)malloc(n*sizeof(int)); //辅助数组
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++){
        //将较小值复制到b中
        if(b[i]<=b[j]){
            a[k] = b[i++]; 
        }else{
            a[k] = b[j++]
        }
    }
    //将剩下的非空表中的元素直接复制到a中
    while(i<=mid) a[k++] = b[i++]; 
    while(j<=high) a[k++] = b[j++];
}

二路归并树形态上为一棵倒立的二叉树，所以其时间复杂度与树高h有关

每趟归并的时间复杂度为O(n),所以总时间复杂度为O(n*log~2~n)
空间复杂度为O(n),来自于辅助数组b。

基数排序

关于“分配”与“收集”的排序，基数其实指的就是进制的基数，分有最高位优先MSD以及最低位优先LSD

分配：根据基数r，设置r-1个辅助队列，对无序序列L按MSD或LSD方法进行分配

收集：将各个辅助队列中的结点依次出队并链接

基数排序并不是基于比较的排序！

基数排序通常基于链式存储实现，需要r个辅助队列，空间复杂度为O(r)
基数排序是稳定的

基数排序的适用问题：

数据元素的关键字可以方便的拆分为d组，且d较小
每组关键字的取值范围不大，即r不大
关键字个数n较大

外部排序

之前介绍的所有排序方法都是内部排序，即全部在内存中进行

数据元素太多，无法一次全部读入内存进行排序，只能将数据分部多次调入内存进行排序

使用归并排序最少用3块内存缓冲区就可对任意大小的文件进行排序。

每次读入两个块的内容，进行内部排序后写回磁盘，将这两块有序的子序列称为一个“归并段”
有一个输入缓冲区空了就需要从归并段的下一块补上
外部排序时间开销=读写外存的时间(主要开销)+内部排序所需时间+内部归并所需时间

外部排序优化

想办法减少关键字对比次数与减少初始归并段数量

多路归并，需要m路就在内存中开辟m(输入)+1(输出)个缓冲区，采用多路归并可以减少归并趟数，从而减少磁盘I/O次数

对r个初始归并段，做k路归并，则归并树可以用k叉树表示，若树高为h，

则$归并趟数=h-1=\lceil log_{k}{r} \rceil$，由于k叉树第h层最多有$k^{h-1}$个结点，则$r\leq k^{h-1}$

$(h-1)_{最小}=\lceil log_kr\rceil$

k越大，r越小，归并趟数越少，读写磁盘次数越少
缺点：内存开销增加，每挑选一个关键字需要对比关键字(k-1)次，内部归并所需时间增加

减少归并段数量：增加初始归并段的长度就可以减少初始归并段的数量r

k路归并：最多有k个段归并为1个

k路平衡归并：在k路归并的基础上，每一趟归并若有m个归并段参与，处理后得到$\lceil m/k\rceil$个归并段

败者树

可以减少关键字对比次数

可视为一个单结点连接一棵完全二叉树，k个叶节点为当前参与比较的元素，非叶节点记忆左右子树的败者，胜者逐层向上继续进行比较，一直到根节点

构建好败者树后，选出最小元素，只需对比$\lceil log_2k \rceil$次

置换—选择排序

进一步减少了初始归并段的数量

设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录

从FI输入w个记录到工作区WA
从WA中选出最小值记为MINIMAX记录
将MINIMAX输出到FO
若FI非空，从FI输入下一个记录到WA
从WA中比MINIMAX大的关键字序列中，选出最小关键字，作为新的MINIMAX
重复3~5,hi到WA选不出新的MINIMAX，此时得到一个初始归并段，输出一个归并段结束标志到FO
重复2~6,h直到WA为空，此时得到全部初始归并段

其中第5步通过败者树实现

最佳归并树

归并过程中的磁盘I/O数=归并树的WPL*2

所以二路归并的最佳归并树就是进行哈夫曼树(最小WPL)化

推导多路归并的最佳归并树：

取k个最小的叶子节点为兄弟，父节点为其权值和，直到所有的子树全部并入归并树。

对于K叉归并，若初始归并段的数量无法构成严格的k叉归并树，则需要补充几个长度为0的虚段，再进行哈夫曼树构造

k叉最佳归并树一定是个严格的k叉树即树中只包含度为k度为0的节点

($k*n_k=n-1$这条式子表明k叉树的分叉数量=节点数-1个根节点)

各种排序算法的性质

排序算法小结：

若记录数n较小，适用直接插入排序或简单选择排序，当记录本身信息量大时，使用简单选择排序
若序列初始状态已基本有序，使用直接插入或者冒泡排序
若n较大，使用时间复杂度为O(nlog₂n)的算法，比如快排、堆排、归并排序
- 堆排序所需辅助空间少于快速排序，不会出现快速排序可能出现的最坏情况
- 归并排序稳定，其他两种不稳定
当记录本身信息量较大时，为了减少移动记录造成的时间开销，可以使用链表作为存储结构
当n个记录随机分布时，任何基于比较的排序算法，至少需要O(nlog₂n)时间复杂度（判定过程为二叉树）