对一待排序序列分别进行直接插入排序和简单选择排序，若待排序序列中有两个元素的值相..

（2）冒泡排序。首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换两个记录的值，然后比较第二个记录和第三个记录的关键字，以此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称为第一趟冒泡排序，其结果是关键字最大的记录被安置到第n个记录的位置上，然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被安置到第n-1个记录的位置上，当进行完第n-1趟时，所有记录有序排列。

（3）简单选择排序。通过n-1次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有记录有序排列。

简单选择排序

n个记录进行简单选择排序的基本方法是：通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录进行交换，当i等于n时所有记录有序排列。

【算法】简单选择排序算法。

简单选择排序法在最好情况下（待排序列已按关键码有序）不需要移动元素，因此n个元素排序时的总移动次数为0次。在最坏情况下（元素已经逆序排列），每趟排序移动记录的次数都为3次（两个数组元素交换值），共进行n-1趟排序，总移动次数为3（n-1）。无论在哪种情况下，元素的总比较次数为

。

由此，简单选择排序是一种不稳定的排序方法，其时间复杂度为O（n²）。排序过程中仅需要一个元素的辅助空间用于数组元素值的交换，空间复杂度为O（1）。

排序

假设含n个记录的文件内容为｛R₁，R₂，…，R_n｝，其相应的关键字为｛k₁，k₂，…，k_n｝。经过排序确定一种排列｛R_j₁，R_j₂，…，R_jn｝，使得它们的关键字满足如下递增（或递减）关系：k_j₁≤k_j₂≤…≤k_jn（或k_j₁≥k_j₂≥…≥k_jn）。

选择排序

若设R[1...n]为待排序的n个记录，R[1...i-1]已按照主关键字由小到大排序，且任意x∈R[1...i-1]，y∈R[i...n]满足x.key≤y.key，则选择排序的主要思路如下。

（1）反复从R[i...n]中选出关键字最小的结点R[k]。

（2）若i≠k，则将R[i]与R[k]交换，使得R[1...i]有序且保持原来的性质。

（3）i增1，直到i为n。

为方便描述，被查找的顺序表C类型定义如下：

顺序存储线性表的选择排序算法如下：

可见，选择排序不管原先序列是否有序，其排序需要比较的次数均为n(n-1)/2；同时，由于相等的两个元素，位置相对在前的可能被交换到后面，故该选择排序是不稳定的。

直接插入排序

直接插入排序是一种简单的排序方法，具体做法是：在插入第i个记录时，R₁，R₂，…，R_i-1己经排好序，这时将记录R_i的关键字k_i依次与关键字k_i_-1，k_i_-2，…，k₁进行比较，从而找到R_i应该插入的位置，插入位置及其后的记录依次向后移动。

【算法】直接插入排序算法。

直接插入排序法在最好情况下（待排序列已按关键码有序），每趟排序只需作1次比较且不需要移动元素，因此n个元素排序时的总比较次数为n-1次，总移动次数为0次。在最坏情况下（元素已经逆序排列），进行第i趟排序时，待插入的记录需要同前面的i个记录都进行1次比较，因此，总比较次数为

。排序过程中，第i趟排序时移动记录的次数为i+1（包括移进、移出temp），总移动次数为

。

由此，直接插入排序是一种稳定的排序方法，其时间复杂度为O（n²）。排序过程中仅需要一个元素的辅助空间，空间复杂度为O（1）。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5