第三十四课：插入排序，快速排序（3）
时间：2010-09-21 来源：yuxinlen
2、快速排序
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
|
初始关键字 |
49 |
38 |
65 |
97 |
76 |
13 |
27 |
49 |
|
|
i |
|
|
|
|
|
j |
j |
|
1次交换之后 |
27 |
38 |
65 |
97 |
76 |
13 |
|
49 |
|
|
i |
|
i |
|
|
|
j |
|
|
2次交换之后 |
27 |
38 |
|
97 |
76 |
13 |
65 |
49 |
|
|
|
|
i |
|
|
j |
j |
|
|
3次交换之后 |
27 |
38 |
13 |
97 |
76 |
|
65 |
49 |
|
|
|
|
i |
i |
|
j |
|
|
|
4次交换之后 |
27 |
38 |
13 |
|
76 |
97 |
65 |
49 |
|
|
|
|
|
ij |
|
j |
|
|
|
完成一趟排序 |
27 |
38 |
13 |
49 |
76 |
97 |
65 |
49 |
|
|
|
|
|
|
|
|
|
|
|
初始状态 |
49 |
38 |
65 |
97 |
76 |
13 |
27 |
49 |
|
一次划分 |
27 |
38 |
13 |
49 |
76 |
97 |
65 |
49 |
|
分别进行 |
13 |
27 |
38 |
|
|
|
|
|
|
|
结束 |
|
结束 |
|
49 |
65 |
76 |
97 |
|
|
|
|
|
|
49 |
65 |
|
结束 |
|
|
|
|
|
|
|
结束 |
|
|
|
有序序列 |
13 |
27 |
38 |
49 |
49 |
65 |
76 |
97 |
|
|
|
|
|
|
|
|
|
|
四、总结
几种排序的简单分析与比较。（时间、空间复杂度）
五、作业
实现直接插入排序、起泡排序、快速排序算法。
相关阅读 更多 +
