算法基础知识、算法分析基础、查找、排序、常用算法原理

NULL

考纲

算法基础知识

基本概念

• 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法的五个重要特性如下：

  

算法分析基础

复杂度

• 上述的时间复杂度，经常考到，需要注意的是，时间复杂度是一个大概的规模表示，一般以循环次数表示，O(n)说明执行时间是n的正比，另外，log对数的时间复杂度一般在查找二叉树的算法中出现。渐进符号O表示一个渐进变化程度，实际变化必须小于等于O括号内的渐进变化程度。

查找

• 顺序查找：将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败

  • 时间复杂度为O(n)

• 折半（二分）查找：设查找表的元素存储在一维数组r[1..n]中，在表中元素已经按照关键字递增方式排序的情况下，进行折半查找的方法是：

  1. 首先将待查元素的关键字（key）值与表r中间位置上（下标为mid）记录的关键字进行比较，若相等，则查找成功。
  2. 若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1..n]中，下一步应在后半个子表中查找。
  3. 若key<r[mid].key，说明待查记录只可能在前半个子表r[1..mid-1]中，下一步应在r的前半个子表中查找。
  4. 重复上述步骤，逐步缩小范围，直到查找成功或子表为空失败时为止。

  • 要注意两点：中间值位置求出若为小数，应该向下取整，即4.5=4，非四舍五入中间值已经比较过不相等，在划分下一次比较区间时，无需将中间值位置再纳入下一次比较区间。当查找的数据越多时，二分查找的效率越高。

    • 折半查找的时间复杂度为O(log₂n)

• 前面的查找方法，由于记录在存储结构中的相对位置是随机的，所以查找时都要通过一系列与关键字的比较才能确定被查记录在表中的位置。也就是说，这类查找都是以关键字的比较为基础的，而哈希表则通过一个以记录的关键字为自变量的函数（称为哈希函数）得到该记录的存储地址，所以在哈希表中进行查找操作时，需要用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功

• 散列（哈希）表：根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置。

  

• 在上图中，很明显，哈希函数产生了冲突，使用的是线性探测法解决冲突，还有其他方法如下：

  • 线性探测法：按物理地址顺序取下一个空闲的存储空间。
  • 伪随机数法：将冲突的数据随机存入任意空闲的地址中。
  • 再散列法：原有的散列函数冲突后，继续用此数据计算另外一个哈希函数，用以解决冲突。

排序

基本概念

• 排序的分类：稳定与不稳定排序：依据是两个相同的值在一个待排序序列中的顺序和排序后的顺序应该是相对不变的，即开始时21在21前，那排序结束后，若该21还在21前，则为稳定排序，不改变相同值的相对顺序。

• 内排序和外排序：依据排序是在内存中进行的还是在外部进行的。

  • 数据量小的一般放在内存中进行，效率算法为按照时间复杂度计算
  • 数据量大的一般放在外存中进行，效率算法为按照I/O次数计算

• 排序算法的分类：

  1. 插入类排序：直接插入排序、希尔排序。
  2. 交换类排序：冒泡排序、快速排序。
  3. 选择类排序：简单选择排序、堆排序。
  4. 归并排序。
  5. 基数排序。

直接插入排序

• 直接插入排序是一种简单的排序方法，具体做法是：在插入第 i 个记录时，R₁、R₂、R_i-1已经排好序，这时将R_i，的关键字k_i依次与关键字k_i-1、k_i-2等进行比较，从而找到应该插入的位置并将R_i，插入：插入位置及其后的记录依次向后移动

• 要注意的是，前提条件是前i-1个元素是有序的，第i个元素依次从第i-1个元素往前比较，直到找到一个比第个元素值小的元素，而后插入，插入位置及其后的元素依次向后移动，本质是插入排序。

• 例如将 [57, 68, 59, 52] 进行排序

  

  • 上图中，59依次向前比较，先和68比较，再和57比较，发现57比他小，才插入。

  • 代码如下：

    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 38 39 40 41 42 43

    #include <iostream> #include <vector> using namespace std; // 使用std命名空间 // 插入排序函数 void insertionSort(vector<int>& arr) { int n = arr.size(); for (int i = 1; i < n; ++i) { int key = arr[i]; // 从未排序区域中取出一个元素作为关键字 int j = i - 1; // j的初始值为i的前一个 // 移动已排序区域中比关键字大的元素，为关键字找到合适的位置 while (j >= 0 && arr[j] > key) { // 如果j位置合法，且arr[j]比关键字大 arr[j + 1] = arr[j]; // 就将arr[j]向后移动一个位置 --j; } arr[j + 1] = key; // 在合适的位置插入关键字 } } int main() { vector<int> arr = {57, 68, 59, 52}; cout << "原始数组: "; for (int num : arr) { cout << num << " "; } cout << endl; insertionSort(arr); // 调用插入排序函数 cout << "排序后数组: "; for (int num : arr) { cout << num << " "; } cout << endl; return 0; }

希尔排序

• 希尔排序的基本思想是通过逐渐缩小增量的方式，将整个待排序的记录序列分割成若干子序列，然后对这些子序列分别进行直接插入排序。当整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序，以完成排序过程。具体实现包括以下步骤：

  1. 选择一个小于n的整数d₁作为第一个增量，将所有记录分成d₁个组。这些组中的记录的距离头部为d₁倍数的序号的记录被放在同一组内。
  2. 对每个组内的记录进行直接插入排序，使得每个组内的记录基本有序。
  3. 选择一个比d₁小的增量d₂（d₂必须满足d₂<d₁），重复上述分组和排序工作。依此类推，不断缩小增量，直到所取的增量d_i=1（d_i必须满足d_i<d_i-1<…<d₂<d₁）。这意味着此时所有的记录都被放在同一组内，接下来可以对整个序列进行一次直接插入排序。

• 希尔排序的核心思想在于通过逐步排序、分组和逐渐减小增量的方式，是对直接插入排序算法的改进，可以在一定程度上提高排序效率，尤其是对于大型数据集。

• 例题：

  

  • 第一轮增量为5：

    • 分组为[12, 3], [48, 37], [64, 26], [96, 48], [75, 54]
    • 分组后的排序结果：[12, 3, 37, 26, 48, 54, 64, 48, 96, 75]

  • 第二轮增量为3：

    • 分组为[12, 26, 96], [3, 48, 75], [37, 54, 64]
    • 分组后的排序结果：[12, 3, 37, 26, 48, 54, 64, 48, 96, 75]

  • 第三轮增量为1（最后一轮）：

    • 分组为[3, 12, 26, 37, 48, 48, 54, 64, 75, 96]
    • 分组后的排序结果：[3, 12, 26, 37, 48, 48, 54, 64, 75, 96]

简单选择排序

• n个记录进行简单选择排序的基本方法是：通过n-i（1≤i≤n）在次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有记录有序排列。

• 本质就是每次选择最小的元素进行交换，主要是选择过程，交换过程只有一次

  

  • 代码如下：

    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 38 39 40 41 42 43 44

    #include <iostream> #include <vector> using namespace std; // 使用std命名空间 // 简单交换排序函数 void simpleSwapSort(vector<int>& arr) { int n = arr.size(); // 数组的大小 // 外部循环遍历每一个元素 for (int i = 0; i < n - 1; ++i) { // 内部循环比较并交换元素 for (int j = 0; j < n - i - 1; ++j) { // 如果当前元素大于下一个元素，交换它们 if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } } int main() { // 定义要排序的数组 vector<int> arr = {57, 68, 59, 52}; // 打印排序前的数组 cout << "排序前的数组："; for (int num : arr) { cout << num << " "; } cout << endl; // 调用简单交换排序函数对数组进行排序 simpleSwapSort(arr); // 打印排序后的数组 cout << "排序后的数组："; for (int num : arr) { cout << num << " "; } cout << endl; return 0; }

堆排序

• 基本概念：

  

• 堆排序的方法可分为两步：

  1. 根据给出的待排序关键字建立初始堆
  2. 输入堆顶元素，并调整堆，重复上述步骤
  

• 例子1，建立初始堆：

  

  • 由图可知，首先将给出的数组按完全二叉树规则建立图1.1。

    而后，找到此完全二叉树的最后一个非叶子节点（也即最后一颗子树，1.1中是5），比较此非叶子节点和其两个孩子结点的大小，若小，则与其孩子结点中最大的结点进行交换，如图1.2所示。依据此规则再去找倒数第二个非叶子节点。

    这是只有一层的情况，当涉及到多层次时如图1.3和1.4所示，将3交换下来，又打破了之前的堆，因此又要进行变换，如图1.5所示。之后，就按上述规则依次对非叶子节点进行变换。

• 例子2，堆排序：

  • 初始堆建成后，堆排序的过程如下：
  

  • 由图可知，取走堆顶元素后，将最后一个元素移入堆顶并重新建堆。而后，再取走堆顶元素，重复此过程。

  • 堆排序适用于在多个元素中找出前几名的方案设计，因为堆排序是选择排序，而且选择出前几名的效率很高。

冒泡排序

• 冒泡排序是一种简单的排序方法，适用于对n个记录进行排序。它的工作原理如下：

  • 首先，比较第一个记录的关键字和第二个记录的关键字，如果它们是逆序的，就交换这两个记录的值。然后，继续比较第二个记录和第三个记录的关键字，以此类推，直到比较了第n-1个记录和第n个记录的关键字为止。这一轮的操作称为第一趟冒泡排序，其结果是将关键字最大的记录交换到了第n个记录的位置上。

  • 接下来，进行第二趟冒泡排序，对前n-1个记录进行相同的操作，将关键字次大的记录交换到第n-1个记录的位置上。这个过程最多需要进行n-1趟，之后所有的记录就会有序排列。如果在某一趟冒泡排序过程中没有进行相邻位置的元素交换，那么可以提前结束排序过程，因为已经达到了有序状态。

• 冒泡排序的本质是从最后两个元素开始进行比较，将较小的元素交换到前面去，依次进行比较交换。较小的气泡浮到水面上。

• 例题：

  

  • 代码如下：

    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 38 39

    #include <iostream> #include <vector> using namespace std; // 冒泡排序函数，接受一个整数向量作为输入参数 void bubbleSort(vector<int>& arr) { int n = arr.size(); // 外循环，用于控制比较的轮数 for (int i = 0; i < n - 1; ++i) { // 内循环，用于执行每一轮的比较和交换 // 注意：每一轮都会将当前未排序部分的最大元素移动到末尾 for (int j = 0; j < n - i - 1; ++j) { // 如果当前元素比下一个元素大，交换它们 if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } } int main() { // 初始化整数向量 vector<int> arr = {57, 68, 59, 52}; // 调用冒泡排序函数来对向量进行排序 bubbleSort(arr); // 打印排序后的结果 cout << "排序后的结果是："; for (int num : arr) { cout << num << " "; } cout << endl; return 0; }

快速排序

• 快速排序的基本思想是将待排的记录通过一种超级排序划分为两个独立的部分。其中一部分记录的关键字均不大于另一部分记录的关键字。然后，分别对这两部分记录继续进行快速排序，以最终达到整个序列有序的目的。

• 使用一维数组存储记录。一趟快速排序的具体做法如下：

  • 首先，设定两个指针i和j，它们的初始位置分别指向第一个记录和最后一个记录。设枢轴记录通常是第一个记录的关键字为pivotkey。
  • 然后，从j所指的位置开始向前搜索，找到第一个关键字小于pivotkey的记录，并将其与枢轴记录互相交换位置。接下来，从i所指的位置开始向后搜索，找到第一个关键字大于pivotkey的记录，并将其与枢轴记录互相交换位置。
  • 重复这两步，直到i和j指针相遇时为止。

• 例题：

  

  • 一次快速排序：设定一个基准为57，设定两个指针high=1，low=n，从low指向的第n个元素开始，与基准值进行比较，若小于基准值，则与基准进行交换low–，此时，转而从high指向的第1个元素开始和基准值进行比较，若大于基准值，则和基准值进行交换，此时，又转而从low一指向的值和基准进行比较。

  • 最终以57为界，左边都是小于57的元素，右边都是大于57的元素，完成一次快速排序，接着对两块再分别进行递归即可。

归并排序

• 基本概念：

  

• 一般归并排序都是用来合并多个线性表的，对单列数据，二路归并排序可以对元素进行两两合并，示例如下：

  

  • 对第三次归并，将52与28比较，28小，放入新表头；52再与33比较，33放入新表；52再与72比较，52放入新表；57再与72比较，57放入新表…

基数排序

• 基本概念：

  

  • 由上图可知，基数排序是基于多个关键字来进行多轮排序的，本质也是将问题细分。如上右图例子，分别按个位、十位、百位的大小作为关键字进行了三轮排序，最终得出结果

排序算法总结

• 稳定性是指排序前后，相等的两个元素的相对位置保持不变。

• 在空间复杂度方面，大部分排序算法都是比较交换，因此无需额外的空间。但快速排序需要额外存储每次的基准值，归并排序需要一个新表，基数排序除了需要新表，还需要空间来储存关键字。

• 关于时间复杂度，与堆、树、二分相关的算法通常具有n*logn的时间复杂度，而直接排序算法通常具有n*n的时间复杂度。这些结论可以轻松地通过分析算法原理得出。

• 例题1：

  

  • 插入排序：1+1+1+1+2=6

    • 第一次，[1,1]比较，共一次
    • 第二次，[1,1,2]比较，共一次
    • 第三次，[1,1,2,4]比较，共一次
    • 第四次，[1,1,2,4,7]比较，共一次
    • 第五次，[1,1,2,4,7,5]比较，其中5与7比较一次，5与4比较一次，共两次

  • 归并排序：3+2+4=9

    • 第一次：[1,1], [2,4], [5,7] 共三次
    • 第二次：[1,1,2,4], [5,7] 比较了两次，分别为1-2,1-4
    • 第三次：[1,1,2,4,5,7] 比较了4次，分别为1-5,1-5,2-5,4-5

  • 堆排序：4+2+2+1=9

    

    • 取走1，将5换上去。

      • 5分别与1,2比较，然后与1交换。

      5分别与4,7比较，然后与4交换。

    • 取走1，将7换上去。

      • 7分别与4,2比较，然后与2交换。

    • 取走2，将5换上去。

      • 5分别与4,7比较，然后与4交换。

    • 取走4，将7换上去。

      • 7与5比较，然后将5换上去。

    • 取走5。

  • 快速排序：

    

• 例题2：