2024王道数据结构考研丨第六篇：查找、排序

2023-06-04 16:24| 来源: 网络整理| 查看: 265

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

文章目录第七章查找7.1查找表相关概念第八章排序8.1排序的基本概念8.2 插入排序8.2.1直接插入排序8.2.2折半插入排序8.2.3希尔排序 8.3 交换排序8.3.1冒泡排序8.3.2快速排序 8.4选择排序8.4.1简单选择排序8.4.2堆排序 8.5归并排序和基数排序8.5.1 归并排序8.5.2 基数排序

第七章查找 7.1查找表相关概念

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

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

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

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

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

索引查找：在这里插入图片描述

第八章排序 8.1排序的基本概念排序：重新排列表中的元素，使表中元素满足按关键字有序的过程（关键字可以相同）排序算法的评价指标：时间复杂度、空间复杂度；排序算法的稳定性：关键字相同的元素在排序之后相对位置不变，称为稳定的；（选择题考查） Q：稳定的排序算法一定比不稳定的好？ A：不一定，要看实际需求；排序算法的分类：内部排序：数据都在内存——关注如何使时间、空间复杂度更低；外部排序：数据太多，无法全部放入内存——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少； 8.2 插入排序 8.2.1直接插入排序算法思想：每次将一个待排序的记录按其关键字大小，插入（依次对比、移动）到前面已经排好序的子序列中，直到全部记录插入完成代码实现：不带“哨兵” void InsertSort(int A[], int n){ //A中共n个数据元素 int i,j,temp; for(i=1; i //A中从1开始存储，0放哨兵 int i,j; for(i=1; i int i,j,low,high,mid; for(i=2;i //折半查找 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] } } 与直接插入排序相比，比较关键字的次数减少了，但是移动元素的次数没有变，时间复杂度仍然是O(n²) 8.2.3希尔排序

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

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

代码实现：

void ShellSort(ElemType A[], int n){ //A[0]为暂存单元 for(dk=n/2; dk>=1; dk=dk/2) //步长递减（看题目要求，一般是1/2 for(i=dk+1; i int temp = a; a = b; b = temp; } //冒泡排序 void BubbleSort(int A[], int n){ //从0开始存放 for(int i=0; i //若为逆序 swap(A[j-1],A[j]); //交换 flag=true; } if(flag==false) return; //本趟遍历后没有发生交换，说明表已经有序，可以结束算法 } } 算法效率分析

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

8.3.2快速排序每一趟排序都可使一个中间元素确定其最终位置用一个元素（不一定是第一个）把待排序序列“划分”为两个部分，左边更小，右边更大，该元素的最终位置已确认算法实现（重点） //用第一个元素将待排序序列划分为左右两个部分 int Partition(int A[], int low, int high){ int pivot = A[low]; //用第一个元素作为枢轴 while(low if(low //A从0开始 for(int i=0; i 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 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 if(low

【本文地址】

公司简介

联系我们