第三十四课：插入排序，快速排序（2）
时间：2010-09-21 来源：yuxinlen
2、折半插入排序
在直接插入排序中，为了找到插入位置，采用了顺序查找的方法。为了提高查找速度，可以采用折半查找，这种排序称折半插入排序。
3、2－路插入排序
为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进：
|
49 |
38 |
65 |
97 |
78 |
13 |
27 |
49 |
... |
|
|
i=1 |
49 |
|
|
|
|
|
|
|
|
|
first |
|
|
|
|
|
|
|
|
i=2 |
49 |
|
|
|
|
|
|
38 |
|
|
final |
|
|
|
|
|
|
first |
|
i=3 |
49 |
65 |
|
|
|
|
|
38 |
|
|
|
final |
|
|
|
|
|
first |
|
i=4 |
49 |
65 |
97 |
|
|
|
|
38 |
|
|
|
|
final |
|
|
|
|
first |
|
i=5 |
49 |
65 |
76 |
97 |
|
|
|
38 |
|
|
|
|
|
final |
|
|
|
first |
|
i=6 |
49 |
65 |
76 |
97 |
|
|
13 |
38 |
|
|
|
|
|
final |
|
|
first |
|
|
i=7 |
49 |
65 |
76 |
97 |
|
13 |
27 |
38 |
|
|
|
|
|
final |
|
first |
|
|
|
i=8 |
49 |
49 |
65 |
76 |
97 |
13 |
27 |
38 |
|
|
|
|
|
|
final |
first |
|
|
三、快速排序
1、起泡排序
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第n-1个记录和第n个记录的关键字进行过比较为止。
然后进行第二趟起泡排序，对前n-1个记录进行同样操作。
...直到在某趟排序过程中没有进行过交换记录的操作为止。
|
49 |
38 |
38 |
38 |
38 |
13 |
13 |
|
38 |
49 |
49 |
49 |
13 |
27 |
27 |
|
65 |
65 |
65 |
13 |
27 |
38 |
38 |
|
97 |
76 |
13 |
27 |
49 |
49 |
|
|
76 |
13 |
27 |
49 |
49 |
|
|
|
13 |
27 |
49 |
65 |
|
|
|
|
27 |
49 |
78 |
|
|
|
|
|
49 |
97 |
|
|
|
|
|
|
初始 |
第一趟 |
第二趟 |
第三趟 |
第四趟 |
第五趟 |
第六趟 |
相关阅读 更多 +
