408数据结构——排序

文章声明：第一，本文涉及的内容只包括408考研大纲的内容，本文只是觉得王道408辅导教材在这个地方又臭又长（其实王道书在绝大多数地方都是这样），这里只是精简王道书上的内容，这部分的内容其实挺复杂，但是考研要求你甚至代码都不需要掌握，所以这只是知识提炼。第二，这部分我不会太过注重细节，所以只适合科班出身或者已经复习的不错的人阅读。

有问题欢迎大佬补充

查找

一.首先王道书上有这个图，这个一定需要背下来，没啥好说，死记硬背就完事了：

时间为n2的空间一定为1

二.插入排序：就是不断的把下一个元素放在之前已经排序好的序列中的对应位置上，改进是折半插入排序，但是效率是一样的，没有额外空间，时间复杂度n2,空间复杂度为1，是稳定算法，适用于顺序存储和链式存储的线性表。

三.希尔排序：也属于插入排序，按照间隔k分成很多组，组内插入排序，排序好之后，把k-1然后重新分组，接着重复之前的步骤，注意希尔排序是唯一一个时间复杂度不定的算法，没有利用额外空间，空间复杂度为1，不是稳定算法，希尔排序只适用于顺序存储的线性表(只有希尔排序和堆排序不能用链表，因为涉及到随机存储）。

三.冒泡排序：从前往后（或者从后往前），两两比较元素，要是顺序不是最终结果的顺序，则交换。特点是每一次都可以使得有一个元素放在最终位置上。时间复杂度n2,空间复杂度为1，是稳定算法。

四.快速排序：随机找一个元素，比它大的扔到后面，比它小的扔到前面，然后对前后两个子表重复上述步骤，直至每部分只有一个元素或没有为止。时间，空间复杂度均为nlogn大数据排序，快速排序是性能最优的算法，但不是稳定算法。每趟排序之后都有一个元素放在最终位置上（特例：2019年的题目，如果第一趟没有边界元素放在位置上，第二趟则会确定2个元素）

五.选择排序：假设大小n，第i趟就从i-n中选出来最小的一个，放到第i个位置，然后i++;比较次数和初始序列无关，每趟排序之后都有一个元素放在最终位置上，时间复杂度n2,空间复杂度1，不是稳定算法。

六.堆排序：这玩意实质就是一个用数组存储的二叉树，大根堆就是这个二叉树父比子大，小根堆就是二叉树子比父大。空间复杂度1，时间复杂度nlogn，不是稳定算法，需要用顺序存储，每一次趟使得至少一个元素到达最终位置。考法一：插入，这个找到数组下一个位置对应的二叉树到位置插入就行，然后自下而上，如果父子关系不符合大根堆/小根堆的定义，孩子交换就行，然后一直往上交换直到根节点。考法二：输出，将根节点输出之后，把最后一个元素放在该位置。然后自上而下重新调整，与插入类似，直到最后一层为止。（补充：二叉排序树需要左小右大，堆排序是左右都小或者左右都大，不一样！）

七.归并排序：文字不好描述，看图，图片是二路归并排序，先两两分组，再排序:

时间复杂度是nlogn 空间复杂度是n，这玩意空间占用是最多的，是稳定算法，值得注意的就是这东西是外部排序，如果排序文件太大了就用这个，

八.基数排序，比如给三位数排序，先按照个位大小排序，然后按照十位大小排序，十位数字相同则看个位大小，最后看百位大小，百位相同看十位大小，总之就是看上一次排序的大小来定。空间复杂度为r，时间复杂度位很特殊的d(n+r),是稳定算法。这个考的不难，理解原理就行。

九.外部排序：①13，19两年考过最佳归并树，有两个公式，记住公式，完全搞懂2道真题，明白归并树，虚段的定义就行。②败者树，这个看书上的图片就行，理解原理，目前还没有考过（感觉也不好考），简单来说就是每个节点的胜者向上传递大小和来源，然后当前节点保留失败者的大小和来源。③置换——选择排序，也就是看书，实在不懂就听课，王道的课比树质量高太多了。

补充，关于每趟排序能否确定元素位置：

1.选择排序：每次将最大（小）的数放到最后（前）。所以排一次序后位置就确定了。

2.冒泡排序：同选择排序。每一次排序最大的值位置确定。

3.快速排序：每一次排序pivot的位置确定。

4.堆排序：每一次排序时，都是将堆顶的元素和最后一个节点互换，然后调整堆，再将堆大小减1。所以每一次排序堆顶元素确定。

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!