现在的位置: 首页 > 综合 > 正文

快速排序

2018年05月10日 ⁄ 综合 ⁄ 共 437字 ⁄ 字号 评论关闭

算法思想:在待排序的n个记录中任取一个记录(通常第一个记录)作为支点,记为num。经过一趟排序后,把所有小于num的记录交换到前面,大于num的记录交换到后面,结果将待排序记录分成两个子表,然后,依次对左、右子表进行上述操作,直至每一个子表只有一个记录时,排序完成。如:(49,38,65,97,76,13,27)经过第一趟后变为(27,38,13)49(76,97,65)

具体做法:

(1)设两个指针low和high,初始时分别指向表的下界和上界,支点记录的关键字为num

(2)从数列的high位置,依次向左搜索找到第一个小于num的记录和支点记录交换。

(3)从数列的low位置,依次向右搜索找到第一个大于num的记录和支点记录交换

(4)重复(2)(3)直至low==high

   在上述过程中,因为每次记录都是和支点交换,每次交换都要移动3次记录,又因为支点的值已经记录在num上了,每次只要将a[low]或a[high]单向移动,最后再将支点的值移动到合适的位置就好

代码:


抱歉!评论已关闭.