可算结束了简单数据结构的学习 收 官！
壹 排序的基本概念
排序主要分为 内部排序 和 外部排序
（我考试主要涉及内部排序 因此外部排序略过）
对于内部排序算法 都需要做的是比较和移动
重点---稳定性：经过排序后 能使关键字相同的元素保持原顺序中的相对位置不变（排序算法内允许有相同的关键字记录）
举个例子 冒泡排序就是一个稳定的排序算法
两个关键字相同的5 经过冒泡排序后相对位置不变
贰 插入排序
主要探讨直接插入排序和希尔排序
基本思想：每次将一个待排序的记录按关键字大小插入前面已经排好序的子序列
直接插入排序
适用于基本有序 数据量不大
第一趟都会前两个元素排好序 第二趟则有前三个元素排好序
空间复杂度O(1)
时间复杂度O(n二次方)
稳定
适用顺序存储和链式存储的线性表
看题
用直接插入排序算法对下列4个表进行升序排序 比较次数最少的是
A 94,32,40,90,80,46,21,69 B 21,32,45,40,80,69,90,94
C 32,40,21,46,69,94,90,80 D 90,69,80,46,21,32,94,40
首先明确一点直接插入排序算法在基本有序的情况下发挥厉害 所以在BC下选择
然后计算比较次数 以B为例
还有在直接插入排序算法的实现中 哨兵的作用是简化边界条件的处理
希尔排序
本质也是插入排序
利用增量d来实现排序 又叫缩小增量排序
空间复杂度O(1)
时间复杂度O(n二次方)
不稳定
适用顺序存储的线性表
很抽象 直接用一道题来破解考点
已知输入序列{13，24，7，1，8，9，11，56，34，51，2，77，5} 增量序列d={5，3，1}采用希尔排序
我们利用知道题把所有能涉及到的考点来一遍
仨 交换排序
主要讲解快速排序 冒泡排序已多次接触过
冒泡排序
空间复杂度O(1)
时间复杂度O(n二次方)
稳定
适用顺序存储和链式存储的线性表
对n个关键字要按升序排序 冒泡排序算法下 啥情况比较的次数最多
快速排序
在完全无序的情况下发挥长处
基本思想采用分治法 会利用到一个枢轴或叫做基准
就平均性能而言 快速排序是目前最好的内部排序算法
每一趟排序都会将枢轴元素放到其最终位置
空间复杂度O(log2为底n)
时间复杂度O(nlog2为底n)
不稳定
适用顺序存储的线性表
还是以题目来理解
数据序列F={2，1，4，9，8，10，6，20}是哪种排序算法两趟排序后的结果
但我们也借此题来分析一下快速排序的过程
对8个元素的序列进行快速排序 最好情况下关键字比较的次数为
首先最好情况下 就是每次都平均的分为两个子序列
首先分为3 4比较7次 继续划分 3->1 1比较两次 4->1 2比较3次 2->1比较1次
共比较13次
统考真题下列选项不可能是快速排序第二趟排序结果的是
A.2,3,5,4,6,7,9 B.2,7,5,6,4,3,9
C.3,2,5,4,7,6,9 D.4,2,3,5,7,6,9
首先之前写过每一趟都会确定枢轴元素放在最终位置
巳 选择排序
我自认为这个里面的堆排序才是重点也是难点常考的
选择排序就是挑元素然后换 n个元素只需要n-1趟完事
简单选择排序
空间复杂度O(1)
时间复杂度O(n二次方)
不稳定
适用顺序存储和链式存储的线性表
适用于关键字较少的情况
这个很好理解 简单看一个例子
你会发现原序列无论是升序还是降序状态 都不会影响比较的次数
因此：简单选择排序比较的次数与序列初始状态无关
堆排序
堆排序可以视为一棵完全二叉树
分为大根堆和小根堆(大根堆就是最大元素为根节点 任意一个非根节点的值小于或等于其双亲结点值)
空间复杂度O(1)
时间复杂度O(nlog2为底n)
不稳定
适用顺序存储的线性表
关于堆的删除就是删除堆顶元素将最后一个元素换上 然后再调整
关于堆的插入就是放在堆的末端然后再依次向上调整
适用于海量关键字多的情况
每一趟都将一个元素放在其最终位置
概念逻辑总是傻x的 看题目理解要考啥完事
判断下列哪一个是一个堆
A.19,75,34,26,97,56 B.97,26,34,75,19,56
C.19,56,26,97,34,75 D.19,34,26,97,56,75
题目没有给出是大根堆还是小根堆 所以分为两种情况
我们就以A B为例分析方法
已知大根堆{62，34，53，12，8，46，22}删除堆顶元素后重新调整堆 在此过程中关键字的比较次数为
统考真题 已知序列{25，13，10，12，9}是大根堆 在序列尾部插入新元素18 再将其调整为大根堆 调整过程中元素之间的比较次数为
统考真题 将关键字6，9，1，5，8，4，7依次插入初始为空的大根堆H 得到的H为
这里还是有点小坑的错误的解法 直接看着序列调整好了
其实应该是边插入边调整
伍 归并排序(二路归并排序)
因为考试不注重考察就简单考察二路归并排序
归并排序要求内存大
空间复杂度O(n)
时间复杂度O(nlog2为底n)
稳定
适用顺序存储和链式存储的线性表
对于N个元素进行K路归并排序 趟数m=logk为底N 向上取整
若对27个元素只进行三趟多路归并排序 选取的归并路数最少为
用到上述写过的方法
一组经过一趟二路归并排序后的记录的关键字为{25，50，15，35，80，85，20，40，36，70}其中包含5个长度为2的有序表 用二路归并排序算法对该序列进行第二趟归并后的结果为
六 内部排序算法的比较
参考：https://blog.csdn.net/alzzw/article/details/98100378
杀青！！！
标签：归并,复杂度,元素,关键字,序列,69,排序 From： https://www.cnblogs.com/gaodiyuanjin/p/18539022