|
|
|
|
若设R[1...n]为待排序的n个记录，R[1...i-1]已按照主关键字由小到大排序，则直接插入排序的主要思路如下。
|
|
|
|
（1）寻找R[i]在R[1…i-1]中的插入位置，确保R[i]插入后保持有序。
|
|
|
|
（2）i增1，若i小于等于m，则转到（1）执行，否则结束。
|
|
|
|
|
|
|
|
|
|
（1）对n个结点的线性表采用直接插入排序，当线性表已是从小到大排序时，内循环每执行一次，只需要进行1次比较，整个排序过程只进行n-1次比较。当线性表已是从大到小排序时，对外循环执行i次，内循环要进行i次比较，整个排序过程需要进行n(n-1)/2次比较。可见，对n个结点的线性表采用直接插入排序，最少比较次数为n-1，最多比较次数为n(n-1)/2。
|
|
|
|
（2）直接插入排序是在有序表的基础上进行的，所以排序效率较高且比较稳定。
|
|
|
|
|
|
|
|
| |
|
|
|
