排序的基本概念

2022.09.18

1. 算法的稳定性：key相等的值，排序后前后顺序不变

2. 根据元素是否在内存中：内部排序，外部排序
3. 对于任意序列进行基于比较的排序，求最少的比较次数应考虑最坏情况。上取整{log2 n!}

1. 下述排序方法中，不属于内部排序方法的是（ ） A.插入排序 B.选择排序 C.拓扑排序 D.冒泡排序

   【答案】：C

2. 排序算法的稳定性是指（ ）。 A.经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变 B.经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变 C.排序算法的性能与被排序元素个数关系不大 D.排序算法的性能与被排件元素的个数关系密切

   【答案】：A

3. 下列关于排序的叙迷中，正确的是(）。 A.稳定的排序方法优于不稳定的排序方法 B.对同一线性表使用不同的排序方法进行排序，得到的排序结果可能不同 C.排序方法都是在顺序表上实现的，在链表上无法实现排序方法 D.在顺序表上实现的排序方法在链表上也可以实现

   【答案】：B

4. 对任意7个关鍵宇进行基于比较的排序，至少要进行（ 〕次关键宇之间的两两比較

   【答案】：6 -> 13

   对于任意序列进行基于比较的排序，求最少的比较次数应考虑最坏情况。上取整{log2 n!}