到此，2024王道数据结构考研笔记专栏“基础知识”部分已更新完毕，其他内容持续更新中，欢迎 点此 订阅，共同交流学习…

第七章 查找

7.1查找表相关概念

• 查找表：由同一类型的数据元素（或记录）构成的集合。对查找表进行的经常操作为：查找、检索、增加、删除。

• 静态查找表：对查找表只进行前两种操作。

• 动态查找表：不仅限于前两种操作。

• 关键字：数据元素中某个数据项的值，用以标识一个数据元素，如果是唯一标识，则称为主关键字。

• 查找是否成功：根据给定的值，在查找表中确定一个其关键字等于给定值的元素，如果表中存在这样元素，则称查找成功，否则，不成功。
  折半查找：
  

  索引查找：
  

第八章 排序

8.1排序的基本概念

1. 排序：重新排列表中的元素，使表中元素满足按关键字有序的过程（关键字可以相同）
2. 排序算法的评价指标：时间复杂度、空间复杂度；
3. 排序算法的稳定性：关键字相同的元素在排序之后相对位置不变，称为稳定的；（选择题考查）
   Q： 稳定的排序算法一定比不稳定的好？
   A： 不一定，要看实际需求；
4. 排序算法的分类：
   内部排序： 数据都在内存——关注如何使时间、空间复杂度更低；
   外部排序： 数据太多，无法全部放入内存——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少；

8.2 插入排序

8.2.1直接插入排序

1. 算法思想： 每次将一个待排序的记录按其关键字大小，插入（依次对比、移动）到前面已经排好序的子序列中，直到全部记录插入完成
2. 代码实现：

• 不带“哨兵”

void InsertSort(int A[], int n){    //A中共n个数据元素int i,j,temp;for(i=1; i<n; i++)if(A[i]<A[i-1]){    //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;         //复制到插入位置}
}

• 带“哨兵” ，优点：不用每轮循环都判断j>=0

void InsertSort(int A[], int n){    //A中从1开始存储，0放哨兵int i,j;for(i=1; i<n; i++)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];          //复制到插入位置}
}

3. 算法效率分析

空间复杂度：O(1)
时间复杂度：主要来自于对比关键字、移动关键字，若有n个元素，则需要n-1躺处理
最好情况： 原本为有序，共n-1趟处理，每一趟都只需要对比1次关键字，不需要移动元素，共对比n-1次 —— O(n)
最差情况： 原本为逆序 —— O(n²)
平均情况： O(n²)
算法稳定性：稳定

4. 对链表进行插入排序
   移动元素的次数变少了，因为只需要修改指针，不需要依次右移；
   但是关键字对比的次数依然是O(n²)数量级，因此整体看来时间复杂度仍然是O(n²)

8.2.2折半插入排序

1. 思路： 先用折半查找找到应该插入的位置，再移动元素；

2. 为了保证稳定性，当查找到和插入元素关键字一样的元素时，应该继续在这个元素的右半部分继续查找以确认位置; 即当 A[mid] == A[0] 时，应继续在mid所指位置右边寻找插入位置

3. 当low>high时，折半查找停止，应将[low,i-1]or[high+1,i-1]内的元素全部右移，并将A[0]复制到low所指的位置；

4. 代码实现

void InsertSort(int A[], int n){ int i,j,low,high,mid;for(i=2;i<=n;i++){A[0] = A[i];                    //将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)       //统一后移元素，空出插入位置A[j+1] = A[j];A[high+1] = A[0]}
}

5. 与直接插入排序相比，比较关键字的次数减少了，但是移动元素的次数没有变，时间复杂度仍然是O(n²)

8.2.3希尔排序

1. 思路： 先追求表中元素的部分有序，再逐渐逼近全局有序；

2. 更适用于基本有序的排序表和数据量不大的排序表，仅适用于线性表为顺序存储的情况

3. 代码实现：

void ShellSort(ElemType A[], int n){//A[0]为暂存单元for(dk=n/2; dk>=1; dk=dk/2)   //步长递减（看题目要求，一般是1/2for(i=dk+1; i<=n; ++i)if(A[i]<A[i-dk]){A[0]=A[i];for(j=i-dk; j>0&&A[0]<A[j];j-=dk)A[j+dk]=A[j];         //记录后移，查找插入的位置A[j+dk]=A[0;]             //插入}
}

4. 算法效率分析

• 空间效率：空间复杂度=O(1)
• 时间效率: 最坏情况下时间复杂度=O(n²)
• 稳定性：希尔排序是一种不稳定的排序方法

8.3 交换排序

基于“交换”的排序： 根据序列中两个元素关键字的比较结果来对换这两个记录再序列中的位置；

8.3.1冒泡排序

1. 第一趟排序使关键字值最小的一个元素“冒”到最前面（其最终位置）—— 每趟冒泡的结果是把序列中最小元素放到序列的最终位置，这样最多做n-1趟冒泡就能把所有元素排好序；

2. 为保证稳定性，关键字相同的元素不交换；

3. 代码实现

//交换
void swap(int &a, int &b){int temp = a;a = b;b = temp;
}//冒泡排序
void BubbleSort(int A[], int n){   //从0开始存放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;       //本趟遍历后没有发生交换，说明表已经有序，可以结束算法}
}

4. 算法效率分析

空间复杂度：O(1)
时间复杂度
最好情况 (有序) ：只需要一趟排序，比较次数=n-1，交换次数=0，最好时间复杂度=O(n)
最坏情况 (逆序) ：比较次数 = (n-1)+(n-2)+…+1 = n(n-1)/2 = 交换次数，最坏时间复杂度 = O(n²)，平均时间复杂度 = O(n²)
冒泡排序可以用于链表、顺序表

8.3.2快速排序

1. 每一趟排序都可使一个中间元素确定其最终位置
2. 用一个元素（不一定是第一个）把待排序序列“划分”为两个部分，左边更小，右边更大，该元素的最终位置已确认
3. 算法实现（重点）

//用第一个元素将待排序序列划分为左右两个部分
int Partition(int A[], int low, int high){int pivot = A[low];          //用第一个元素作为枢轴while(low<high){while(low<high && A[high]>=pivot) --high; //high所指元素大于枢轴，high左移A[low] = A[high];   //high所指元素小于枢轴，移动到左侧while(low<high && A[low]<=pivot)  ++low; //low所指元素小于枢轴，low右移A[high] = A[low];   //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);   //划分右子表
}

3. 算法效率分析

每一层的QuickSort只需要处理剩余的待排序元素，时间复杂度不超过O(n);

把n个元素组织成二叉树，二叉树的层数就是递归调用的层数，n个结点的二叉树最小高度 = ⌊log₂n⌋ + 1, 最大高度 = n

时间复杂度 = O(n×递归层数) （递归层数最大为n）

最好 = O(nlog₂n) : 每次选的枢轴元素都能将序列划分成均匀的两部分；
最坏 = O(n²) ：序列本就有序或逆序，此时时间、空间复杂度最高；
平均时间复杂度 = O(nlog₂n) （接近最好而不是最坏）
空间复杂度 = O(递归层数)（递归层数最小为log₂n）

最好 = O(log₂n)
最坏 = O(n)
若每一次选中的“枢轴”可以将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高；

若初始序列本就有序或者逆序,则快速排序的性能最差；

快速排序算法优化思路： 尽量选择可以把数据中分的枢轴元素

选头、中、尾三个位置的元素，取中间值作为枢轴元素；
随机选一个元素作为枢轴元素；
快速排序使所有内部排序算法中平均性能最优的排序算法；

稳定性： 不稳定；

8.4选择排序

思想：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列；

8.4.1简单选择排序

n个元素的简单选择排序需要n-1趟处理；

//交换
void swap(int &a, int &b){int temp = a;a = b;b = temp;
}void SelectSort(int A[], int n){       //A从0开始for(int i=0; i<n-1; i++){          //一共进行n-1趟，i指向待排序序列中第一个元素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)                     swao(A[i],A[min]);         //交换}
}

3. 算法效率分析

空间复杂度 = O(1)
无论有序、逆序、乱序，都需要n-1的处理，总共需要对比关键字 (n-1)+(n-2)+…+1 = n(n-2)/2 次，元素交换次数 < n-1; 时间复杂度 = O(n²)
稳定性： 不稳定
适用性： 既可以用于顺序表，也可以用于链表；

8.4.2堆排序

1. 什么是“堆（Heap）”？
   可理解为顺序存储的二叉树，注意

可以将堆视为一棵 完全二叉树 (✔)

可以将堆视为一棵 二叉排序树 (✖)

大根堆：完全二叉树中，根 ≥ 左、右
小根堆：完全二叉树中，根 ≤ 左、右

2. 如何基于“堆”进行排序

基本思路：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列，堆顶元素的关键字最大或最小 （以下以大根堆为例）

① 将给定初始序列(n个元素)，建立初始大根堆：把所有非终端结点 从后往前都检查一遍，是否满足大根堆的要求——根 ≥ 左、右，若不满足，则将当前结点与更大的孩子互换

在顺序存储的完全二叉树中:

非终端结点的编号 i≤⌊n/2⌋
i 的左孩子 2i
i 的右孩子 2i+1
i 的父节点⌊i/2⌋
更小的元素“下坠”后，可能导致下一层的子树不符合大根堆的要求，则采用相同的方法继续往下调整 —— 小元素不断“下坠”

② 基于大根堆进行排序：每一趟将堆顶元素加入有序子序列中，堆顶元素与待排序序列中最后一个元素交换后，即最大元素换到末尾，之后该位置就不用改变，即移出完全二叉树(len=len-1)，把剩下的待排序元素序列再调整为大根堆；————“一趟处理”

③ 剩下最后一个元素则不需要再调整；

//对初始序列建立大根堆
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较大的子结点向下筛选// i为当前所选根结点的左孩子//i*=2是为了判断调整后再下一层是否满足大根堆if(i<len && A[i]<A[i+1])      //判断：当前所选根结点的左、右结点哪个更大i++;                      //取key较大的子结点的下标if(A[0] >= A[i]) break;                    //筛选结束：i指向更大的子结点else{A[k] = A[i];              //将A[i]调整至双亲结点上k=i;                      //修改k值，以便继续向下筛选}}A[k] = A[0]                       //被筛选的结点的值放入最终位置
}//交换
void swap(int &a, int &b){int temp = a;a = b;b = temp;
}//基于大根堆进行排序
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);       //把剩余的待排序元素整理成堆}
}

8.5归并排序和基数排序

8.5.1 归并排序

归并（Merge）：把两个或多个已经有序的序列合并成一个；

k路归并：每选出一个元素，需对比关键字k-1次；

外部排序通常采用归并排序，内部排序一般采用2路归并；

//创建辅助数组B
int *B=(int *)malloc(n*sizeof(int));//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中elseA[k]=B[j++];}//for//没有归并完的部分复制到尾部，while只会执行一个 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);     //归并}if
}

算法效率分析：

归并排序的比较次数与序列的初始状态无关；

2路归并的“归并树”——倒立的二叉树，树高h，归并排序趟数m = h-1，第h层最多2^(h-1)个结点，则满足n ≤ 2^(h-1)，即h-1 = ⌈log₂n⌉; 结论: n个元素进行2路归并排序，归并趟数 m = ⌈log₂n⌉

每趟归并时间复杂度为O(n), 算法总时间复杂度为O(nlog₂n);

空间复杂度为O(n); (归并排序算法可视为本章占用辅助空间最多的排序算法)

稳定性：归并排序是稳定的

对于N个元素进行k路归并排序，排序的趟数m满足 k^m = N, m = ⌈logkN⌉

8.5.2 基数排序

算法效率分析：

空间效率：O®, 其中r为基数，需要的辅助空间(队列)为r；
时间效率：一共进行d趟分配收集，一趟分配需要O(n), 一趟收集需要O®, 时间复杂度为 O[d(n+r)]，且与序列的初始状态无关
稳定性：稳定！
基数排序擅长解决的问题
①数据元素的关键字可以方便地拆分为d组，且d较小；
②每组关键字的取值范围不大，即r较小；
③数据元素个数n较大；