算法思想:在待排序的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]单向移动,最后再将支点的值移动到合适的位置就好
代码: