李春葆编写的《数据结构教程》核心框架概览
最编程
2024-07-30 22:29:13
...
- 稳定性
- 直接插入算法
- 接口：无序数组A，数组长度n
- 临时变量
- i遍历整个序列代表代插入关键字，j遍历有序区，temp保存带插入无序关键字
- 运算过程
- 两层循环，一层循环整个序列，二层循环遍历有序区插入
- 一层循环内，先判断a[i]与前一个是否无序，若无序那就排序,temp保存关键字，j=i-1，进入二层循环，从后向前找到合适位置，并后移关键字一位，然后temp放入
- 折半插入算法：只是第二层循环用的是折半查找
-
- 接口：无序数组A，数组长度n
- 临时变量
- i遍历整个序列，j用来实现后移插入，temp保存关键字，low,high,mid实现折半查找
- 运算过程
- 两层循环，一层循环整个序列，二层有两个子循环，一子循环为折半查找，二子循环为后移插入
- 一层循环内，先判断a[i]与前一个是否无序，若无序那就排序,temp保存关键字，low=0,high=i-1;进入二层循环，当low<=high的时候，mid=(low+high)/2,折半查找根据不同情况更改low或high的值，跳出循环说明找到位置，用j进行后移插入
-
- 希尔排序：使用直接插入算法实现分组排序，组越分越小，最后完全有序
- 冒泡排序：从后往前，挨个比较交换，每次排出一个最小的，前面为全局有序区
- 接口：无序数组A，数组长度n
- 临时变量
- i表示i次遍历排出i个有序数列，j用来从后往前比较交换
- 运算过程
- 两层循环，一层用i表示i次排序，j用来从后向前直到i那里进行交换
- 快速排序：每次将一个基准排到正确的位置，以此为基准划分左右两块区域，递归调用快速排序算法
- 接口：无序数组A,low，high待排序区间
- 临时变量
- int pivot基准
- 运算过程
- 一层循环里面嵌套递归
- 当low<high时循环，排序第一个关键字并获取基准，根据基准递归调用快速排序左右子序列
-
划分函数
- 接口：无序数组A，low，high
- 返回值：基准物理位置
- 临时变量
- pivot基准保存待排序的基准关键字
- 运算过程
- 两层循环，一层左右遍历序列，二层用来左右横跳
- 先保存第一个关键字为基准，当low<=high开始循环，先从后往前找到一个小于基准的往前放，然后从前往后找一个大于基准的往后放，最后跳出循环剩下的位置放基准，返回基准位置
- 简单选择排序：每次从后面找到一个最小的，往前放
- 接口：无序数字A，长度n
- 临时变量：i代表有序区，j遍历无序区，min保存最小下标
- 运算过程
- 两层循环，一层遍历n遍，二层遍历无序区找最小
- 当i<n循环，min取i,用j从后向前循环，若遇到比min还小的，min取而代之，循环完，发现min值改变，交换a[i]，a[min]
- 堆排序：将数组看成满二叉树的顺序存储结构，先从最后一个分支节点逐个筛选上浮，然后或得一个大根堆，将最大值根与最后一个叶子节点交换，然后再次对根节点进行筛选使之成为大根堆
- 接口：无序数组A,长度n
- 临时变量：
- i用来循环建立初始根堆，以及逐次的根节点交换后排序
- 运算过程：
- 先建立大根堆，i初始为n/2表示最后一个分支节点，当i>=0时i–从后向前逐个进行筛选操作sift(a,i,n)，形成大根堆
- 然后交换根节点和最后一个叶子节点，对根节点进行筛选sift(a,1,i-1)，循环i=n,i>1,i–从后向前，每次算拍好一个最大值，
-
筛选函数sift:先保存待筛选关键字为temp，找出他的最大的一个孩子与父母对比，若比父母大则和父母交换，若破坏了自身大堆性则循环比较孩子和父母的关系，正常则跳出，这时找到temp的位置放入
- 接口：无序数组a，low，high排序区间
- 临时变量：
- i用来表示父母和最后的位置，j表示孩子,temp保存待筛选关键字
- 运算过程：
- i=low,j=2*i,temp=a[i]
- 一层循环调整大根堆并找到带筛选关键字的位置，先比较孩子大小，若孩子比父母大，a[i]=a[j]进行替换，若正常跳出循环，这个循环一直进行到正常，保证替换后的都是大根堆，最后i表示筛选后的位置，a[i]=temp；
- 二路归并
- 接口：无序数组A,low,mid,high表示归并的区间
- 临时变量：r1接受比较后的序列，i，j遍历二路，k遍历r1
- 运算过程：
- 一层循环分别比较二路，哪边小放入r1
- 将二路剩下录入r1
- r1反过来给r，销毁r1
- 插入排序
- 简单插入
- 折半插入
- 希尔排序
- 交换排序
- 冒泡排序
- 快速排序
- 选择排序
- 简单选择排序
- 堆排序
- 归并排序
- 基数排序
- 时间复杂度
- 初级算法都是n^2
- 改进算法都是nlogn
- 希尔排序和基数排序特殊
- 插入和冒泡排序有最好情况，快速排序有最差情况为n^2
- 空间复杂度
- 快速排序：log_2 n
- 二路归并: n
- 基数:r
- 稳定性
- 直，冒，归，基稳定
- 全局有序
- 交换排序和选择排序