|
|
|
|
知识点：
简单排序
排序
直接插入排序
|
|
关键词：
插入排序
排序
章/节：
计算机软件知识
|
|
|
|
|
|
|
对以下四个序列用直接插入排序方法由小到大进行排序时，元素比较数最少的是 (61).
|
|
|
|
|
A.
89,27,35,78,41,15
|
|
|
| B.
27,35,41,16,89,70
|
|
|
| C.
15,27,46,40,64,85
|
|
|
| D.
90,80,45,38,30,25
|
|
|
|
|
|
|
|
| |
|
为保障您的权益，请登录
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
（1）直接插入排序。在插入第i个记录时，R1,R2,…,Ri-1已经排好序，这时将关键字ki依次与关键字ki-1,ki-2,…，k1进行比较，从而找到应该插入的位置，然后将ki插入，插入位置及其后的记录依次向后移动。
|
|
|
|
（2）冒泡排序。首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换两个记录的值，然后比较第二个记录和第三个记录的关键字，以此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称为第一趟冒泡排序，其结果是关键字最大的记录被安置到第n个记录的位置上，然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被安置到第n-1个记录的位置上，当进行完第n-1趟时，所有记录有序排列。
|
|
|
|
（3）简单选择排序。通过n-1次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有记录有序排列。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
假设含n个记录的文件内容为｛R1，R2，…，Rn｝，其相应的关键字为｛k1，k2，…，kn｝。经过排序确定一种排列｛Rj1，Rj2，…，Rjn｝，使得它们的关键字满足如下递增（或递减）关系：kj1≤kj2≤…≤kjn（或kj1≥kj2≥…≥kjn）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
直接插入排序是一种简单的排序方法，具体做法是：在插入第i个记录时，R1，R2，…，Ri-1己经排好序，这时将记录Ri的关键字ki依次与关键字ki-1，ki-2，…，k1进行比较，从而找到Ri应该插入的位置，插入位置及其后的记录依次向后移动。
|
|
|
|
|
|
|
直接插入排序法在最好情况下（待排序列已按关键码有序），每趟排序只需作1次比较且不需要移动元素，因此n个元素排序时的总比较次数为n-1次，总移动次数为0次。在最坏情况下（元素已经逆序排列），进行第i趟排序时，待插入的记录需要同前面的i个记录都进行1次比较，因此，总比较次数为 。排序过程中，第i趟排序时移动记录的次数为i+1（包括移进、移出temp），总移动次数为 。
|
|
|
|
由此，直接插入排序是一种稳定的排序方法，其时间复杂度为O（n2）。排序过程中仅需要一个元素的辅助空间，空间复杂度为O（1）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
