数据结构问答9-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构问答9。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

排序（递增）

1. 排序算法的评价指标

答：除时间空间复杂度外。还要关注算法的稳定性：即经过排序算法关键字相同的元素在排序之后相对位置不变，则为稳定的算法。

内部排序（数据都在内存中）

插入排序

2. 直接插入排序

答：基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

时间复杂度：O(n^2)，空间复杂度：O(1)，稳定性：稳定

3. 折半插入排序

答：基本思想：对直接排序算法的优化（没有质的提升），采用折半查找的方式找到插入位置，再通过移动元素进行插入。

时间复杂度：O(n^2)，空间复杂度：O(1)，稳定性：稳定

4. 希尔排序（Shell Sort）

答：基本思想：是一种分组插入的方法。先追求表中元素部分有序，再逐渐逼近全局有序。

数据结构问答9,408复习打卡,数据结构

时间复杂度：O(n^1.3)，d=1时退化为直接插入最坏O(n^2)，空间复杂度：O(1)，稳定性：不稳定

因为要使用增量d快速的找到相邻的从属于一个子表的元素，因此只适用于顺序表（随机存取）

交换排序

基于“交换”的排序：根据序列中两个元素关键字的比较结果来对换两个记录在序列中的位置

5. 冒泡排序

答：

算法原理：从后往前（从前往后）两两比较相邻元素的值，若为逆序，则交换，直至序列比较完。这是一趟冒泡排序。每一趟可以使一个元素移动到最终位置，之后的处理中这个元素不需要进行比较。如果某一趟排序过程中未发生“交换”，则说明整个序列已有序，可提前结束算法。

基本思想：通过无序区中相邻元素关键字的比较和位置交换，使关键字最小的元素如“气泡”逐渐向前“漂浮”。相同的元素不交换位置，保证算法稳定性。整个算法从最后面的两个元素开始，每两个相邻的关键字进行比较，使关键字小的元素置换到大的前面。依次类推，直至有序。

时间复杂度：最好O(n)，最坏和平均O(n^2)，空间复杂度：O(1)，稳定性：稳定

这种方法也同样适用于链表。每一趟确定一个最大或最小的元素的最终位置

6. 快速排序

答：快速排序是一种高效的排序算法，采用分治的思想。它通过选择一个基准元素将待排序序列划分为左右两个部分，然后对左右两个部分分别进行递归排序。

基本思想：在待排序的n个元素中选择一个基准元素（通常选第一个），然后将序列分为左右两部分，所有关键字与基准比较，比它小的放在前半部分，比它大的放在后半部分，最后基准放在中间（此时确定了一个中间元素的最终位置）。这是一趟快排。接着分别对两半部分递归的继续划分，直到每部分只有一个或不存在元素为止。

时间复杂度：O(n*递归层数)，空间复杂度：O(递归层数)，稳定性：不稳定

最好时间复杂度 O(nlog2n)，每一次划分都将数组分为长度相等的两半。最坏时间复杂度O(n^2)，每一次划分都将数组划分为长度为 1 和 n-1 的两半；

选择排序

每一趟在待排序元素中选取关键字最小（最大）的元素加入有序子序列。

7. 简单选择排序

答：

基本思想：每次从未排序的数据中选出最小的数据，然后将其放到已排序数据的末尾。通过不断重复这个过程，直到所有数据都排好序为止。这种方法适用于顺序表、链表。

时间复杂度：O(n^2)，空间复杂度：O(1)，稳定性：不稳定

8. 堆排序

答：堆排序是一种树形选择排序，特点是：在排序过程中，将顺序表看成一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(小)的元素。堆排序分为两个阶段，以使用大根堆进行升序排序为例：

① 建堆：将待排序序列看作是一棵完全二叉树，从最后一个分支结点开始，对每个结点进行一次调整（也就是将其与其子结点进行比较，如果不满足大根堆的性质则进行交换），直到根结点。

② 排序：将堆顶元素（最大元素）与堆底元素交换，然后将堆的大小减 1，然后对堆顶元素调整进行下坠（保证堆的性质）。重复执行直到堆的大小为 1。

基本思想：利用大根堆（根>左右），每次选择根下坠到最后，堆的大小-1，并调整堆保持大根堆的性质。不断重复这一过程，直到堆只剩下一个元素。小根堆（根<左右）同理

时间复杂度：建堆O(n)+排序O(nlog2n)，整体为O(nlog2n)空间复杂度：O(1)，稳定性：不稳定

堆中插入：新元素放表尾(堆底)，根据大/小根堆的要求，新元素不断上升，直到无法继续上升

堆中删除：被删元素用表尾()元素代替，根据堆要求，替代元素不断下坠，直到无法继续下坠

归并排序

9. 归并排序

答：在内部排序中一般采用二路归并。也有多路归并，m路归并关键字对比次数为m-1次。归并排序是一种基于分治思想的排序算法。第一阶段是分治阶段，将待排序序列不断二分，直到分成单个元素，这些单个元素可以看作是已经排好序的子序列。第二阶段是合并阶段，将已经排好序的子序列两两合并成一个有序的序列，直到整个序列有序。

（二路）基本思想：将初始序列看做n长度为1的有序子序列，然后将相邻的子序列两两归并，然后把排好序的部分看做新的子序列，然后递归的进行，直到得到一个长度为n的有序序列。

将归并排序的过程表示为一棵递归树，假设待排序序列长度为 n，递归树的深度为 log₂n，每层的时间复杂度为 O(n)，则归并排序的最好、最坏时间复杂度均为 O(nlog2n)，空间主要来着合并数组(与原数组大小相同)，比递归函数调用栈比，空间复杂度数量级更高，因此为O(n)。

时间复杂度：O(nlog2n)，空间复杂度：O(n)，稳定性：稳定

每一趟的有序区是局部的，在最后一趟结束前，所有元素并不一定归位了。