快速排序　　基本思想：通过一趟排序将待排序的记录分割为独立的两部分，其中一部分记录的关键字均比另一部部分记录的关键字小，然后再分别对这两部分记录继续进行排序，已达到整个序列有序。　　以趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别指向文件的第一个记录和最后一个记录。设枢轴记录（通常是第一个记录）的关键字为pivotkey，则首先从high所指位置起向前搜索，找到第一个关键字小于pivotkey的记录并与枢轴记录互相交换，然后从low所指位置向后搜索，找到第一个关键字大于pivotkey的记录并与枢轴记录互相交换，重复这两步直到low=high。例：82 16 9 95 27 75 42 69 34 进行快速排序的过程注：[]表示该步交换的两记录，（）表示已趟排序结束后所分割出的的两部分，||表示pivotkey原始数据：82 16 9 95 27 75 42 69 34第一趟排序：p=82[34]16 9  95  27 75 42  69 [82] 34  16 9 [82]27 75 42  69 [95] 34  16 9 [69]27 75 42 [82] 95结果为：（34 16 9 69 27 75 42）|82|（95）第二趟排序：两部分分别排序，后半部分不用再排了。前半部分p=34[27]16 9  69 [34] 75 42 |82| 9527 16 9 [34][69] 75 42 |82| 95结果为：（27 16 9）|34|（69 75 42）|82| 95第三趟排序：对第一个括号p=27[9]16[27]|34|（69 75 42）|82| 95结果：（9）|16|（27）|34|（69 75 42）|82| 95对第二个括号p=699 |16| 27 |34|[42] 75 [69] |82| 959 |16| 27 |34| 42 [69][75] |82| 95结果：9 |16| 27 |34| （42）|69|（75）|82| 95最终结果为：9 |16| 27 |34| 42 |69| 75 |82| 95

评论