【数据结构】——排序算法简答题模板

一、内排序和外排序

1、内排序和外排序有什么区别？内排序有哪些算法？

答：根据排序过程中，数据元素是否完全在内存中进行，可分为内排序和外排序。内排序有直接/折半插入排序、简单旋转排序、冒泡排序、希尔排序、快速排序和堆排序。

二、排序算法的稳定性

1、什么是稳定排序？

答：经过排序后能使关键字相同的元素保持原本顺序中的相对位置不变，则称这个算法是稳定的，反之则不稳定。

三、插入排序

（一）直接插入排序的步骤

1、简述直接插入排序算法的基本思想。

答：直接插入排序是将要排序的序列按照关键字的大小插入至已排好序的子序列中，一直进行直到整个序列有序。

（二）直接插入排序的稳定性

1、直接插入排序算法是不是稳定的排序方法？

答：由于每次插入元素时总是从后向前比较后再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是稳定的。

（三）折半插入排序的步骤

1、简述折半插入排序算法的基本思想。

答：折半插入排序的具体步骤如下：
初始化一个已排序序列，该序列只包含第一个元素，从第二个元素开始，通过折半查找确定每个待排序元素的插入位置，根据已排序序列中元素的中点，比较待排序元素与中点元素的大小，若待排序元素大于中点元素，则插入位置在中间位置的右侧；否则，插入位置在中间位置的左侧，然后插入元素，同时，需要将插入位置及其之后的所有元素向后移动一位，以为待排序元素腾出空间，重复步骤，直到所有元素都被插入到已排序序列中。

（四）希尔排序的步骤

1、简述希尔排序的基本思想。

答：希尔排序也称为缩小增量排序，即通过选取一定的增量来排序的，本质还是插入排序，通过增量将序列分为几个子序列，然后对每个子序列进行直接插入排序。

四、交换排序

（一）冒泡排序的步骤

1、简述冒泡排序的步骤。

答：通过两两比较相邻的元素，若发生逆序，则进行交换，直到整个序列有序为止，即若某一趟冒泡排序中没有发生元素交换，说明此时序列已整体有序。

（二）冒泡排序的趟数和比较次数

1、设有n 个元素采用冒泡排序法进行排序，通常需要进行多少趟排序?对于第i 次冒泡通常需要进行多少次关键字比较?

答：n个元素采用冒泡排序进行排序，最多需要进行n-1趟排序，即最坏情况下，排好的序列刚好与初始序列相反，呈逆序排列；而最少是初始序列正序，只需一趟即可完成排序。

2、设有n 个元素采用冒泡排序法进行排序，第i 次冒泡通常需要进行多少次关键字比较?

答：最好情况下，比较次数为n-1；最坏情况下，由于需要进行n-1趟排序，第i趟排序中要进行n-i次比较。

（三）快速排序的步骤

1、简述快速排序的步骤。

答：快速排序又称为分区交换排序，通过多次划分操作来实现排序思想，其步骤如下：
①每一趟排序中选取一个关键字作为枢轴；
②枢轴将待排序的序列分为两个部分，比枢轴小的元素移到其前，比枢轴大的元素移到其后，这是一趟快速排序；
③然后递归地对两个部分按照枢轴划分规则继续进行快速排序，直至每个区域只有一个元素为止或序列为空，最后达到整个序列有序。

（四）快速排序的稳定性

1、试举例说明快速排序的稳定性。

答：快速排序是不稳定的。当快速排序在处理包含有相等的元素的数组时，相等元素的值没有改变，但它们的相对顺序已经发生了变化，从而导致排序结果不稳定。

五、堆排序

（一）堆排序的步骤

1、简述堆排序的基本思想。

答：堆排序的基本思想是利用大根堆（小根堆）进行排序的方法，步骤如下：
①将待排序的序列构造成一个大根堆（小根堆），此时，整个序列的最大值（最小值）即为堆的根结点。
②将当前根结点移走，即与堆数组的末尾元素交换，此时末尾元素就是最大值（最小值），然后将剩余的n-1个序列重新构造成一个堆，依次得到n个元素中的次大值（次小值）；
③重复以上步骤，从而得到一个有序序列。

（二）堆排序的稳定性

1、堆排序是不是稳定排序？

答：堆排序不是，因为在进行筛选时可能会将后面相同关键字的元素调整到前面，所有不是稳定的排序算法。

（三）堆排序的时间复杂度

1、设结点个数为 n，采用堆排序法进行排序，其时间复杂性是多少?

答：堆排序的时间复杂性取决于堆的构造和调整过程，将结点个数为n的初始序列构造成一个大根堆或小根堆，建堆过程中元素比较次数最多为4n，由于需要遍历整个序列，所以这个构造过程的时间复杂度为O(n)。然后，从剩余n-1个元素中选出一个最大或最小的元素，与末尾元素交换，这样的步骤最多需要n-1次，所以复杂度是n(n-1)/2次对数级别的比较，但是需要减去n/2的建堆时间，即排序过程的时间复杂度为O(nlog₂n)，所以总的堆排序的时间复杂度为O(n)+O(nlog₂n)=O(nlog₂n)。

六、归并排序

（一）k路归并排序的步骤

1、什么是归并排序？

答：将已有序的子序列合并，得到完全有序的序列，其中先使每个子序列有序，再使子序列间有序，即为归并排序。

（二）k路归并排序的稳定性

1、归并排序是不是稳定的？

答：归并排序是稳定的排序算法，满足稳定算法的定义，即假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面，且排序之后，a[i]仍然在a[j]前面。

（三）二路归并排序的步骤

1、简述二路归并排序的算法思想。

答：二路归并排序的步骤如下：
①将含n个元素的序列分为由n个长度为1的有序子表；
②相邻的两个有序子表归并为一个有序子表（两两相邻归并）；
③重复以上步骤，最终归并成一个长度为n的有序表。

七、排序算法的综合运用

1、现有一文件F含有 1000 个记录，其中只有少量记录次序不对，且它们距离正确位置不远如果以比较和移动次数作为度量，那么将其排序最好采用什么方法?为什么?

答：由于文件中基本都是有序的，只有少量记录次序不正确，所以可以通过直接插入排序，它在初始序列已基本有序的情况下表现较好，即在每一步中，只需要移动很少的记录，而不像其他排序算法可能需要交换多个记录。因为只需要比较和交换记录的位置，所以比较次数较少，且由于距离正确位置不远，从而使通过直接插入排序的移动次数也较少，所以选择直接插入排序。

2、全国有 10000 人参加物理竞赛，只录取成绩优异的前 10 名，将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快?为什么?

答：堆排序。一般在n个元素中选出k（k<<n，k>2）个最大（或最小）元素时，均采用堆排序，且堆排序建堆时的最多比较次数为4n，而其他排序算法的时间复杂度较高。