2023计算机考研初试在即，在最后阶段建议各位同学将知识点再系统复习一遍，以免有所遗漏！2022计算机考研数据结构第七单元知识点包含内排序、排序码、直接插入排序等内容。高顿考研为大家整理了2022计算机考研数据结构第七单元知识点的详细内容，供大家参考复习！
内排序：元素个数不多，排序过程只用到内存。
排序码：作为排序依据的关键字(通常是次关键字)。
排序的稳定性：在线性表中可能存在多个排序码相同的元素，如果排序前后这些元素的相对位置有可能被改变，则这种排序方法为不稳定的排序方法。
简单排序：从所有元素中选出排序码最小的元素与第一个元素交换位置，从第一个元素之后的元素中选出排序码最小的元素与第二个元素交换位置，以此类推。
比较次数与初始排列顺序无关，为(n-1)加到1。
移动次数与初始排列顺序有关，最多移动3(n-1)次(赋值操作有3次，包括temp)。
算法执行时间为O(n2)。
算法所需空间大小为O(1)。
为不稳定排序。
直接插入排序：将第一个元素看成一个有序表，将第二个元素插入该表，再插入第三个，每次插入需要通过比较来决定元素间的相对位置。
比较次数，最少为n-1次，最多为n加到2。
移动次数最少为2(n-1)次，最多为n+1加到3。
算法执行平均时间为O(n2)。
算法执行时间最长为O(n2)。
算法所需空间大小为O(1)。
为稳定排序。
冒泡排序：先在n个元素间逐个比较，将较大的元素移到右边，一趟过后，最大的元素置于最右端，再在n-1个元素之间比较，以此类推，当某趟没有出现交换情况或i<2，结束排序。(设置swap记录是否有过交换)
比较次数，最少为n-1次(从小到大排列好时最少)，最多为n-1加到1。
移动次数，最少不移动，最多为3(n-1加到1)(从大到小排列时最多)。
算法执行平均时间为O(n2)。
算法执行时间最坏为O(n2)。
算法所需空间大小为O(1)。
为稳定排序。
快速排序：从n个元素中任取一个元素，将其余元素根据排序码大小分别置于该元素两边，再对两边以这种方式继续排序。
算法平均执行时间为O(nlog2n)。
最坏情况为O(n2)。
算法所需空间大小为O(log2n)。
为不稳定排序。
实现：数据最开始存放在数组的1~n空间内
以第一个元素为标准，将它置于0处，设置i=1，j=n
将j与标准元素相比较，如果j较大，则j-1(较大的数留在原处)
如果j较小，则将j与i交换(较小的数置于另一边)
交换之后，将i与标准元素比较，如果i较小，则i+1(较小的数留在原处)
如果i较大，则将i与j交换(较大的数置于另一边)
交换之后，继续将j与标准元素比较(从两边逐步比较，逼近中间)
i和j相遇之后，结束第一趟排序，将标准元素置于i和j所在的位置
归并排序：将n个元素视作n个有序表，将相邻的有序表归并，得到n/2个长度为2的有序表，以此类推，每次归并会进行内部的比较移动。
归并次数为log2n。
每次归并的比较次数不超过n-1。
移动次数都为n。
算法执行时间为O(nlog2n)。
算法所需空间大小为O(n)。
为稳定排序。
实现：设置i，j，k，i和j指向有序表的两端，k指向辅助空间，每次归并时，将i和j中较小的一个移入k中，并将移动的i或j移向中间，实现有序表的内部排序。
堆排序：按堆的定义，将元素调整为堆，交换第一个元素和最后一个元素，再将n-1个元素调整为堆，再交换第一个元素和最后一个元素，以此类推。
算法执行时间为O(nlog2n)。
算法所需空间为O(1)。
为不稳定排序。

展开全文