算法技术手册 – 排序 – 划分

划分是求Kth、快速排序等的基础。

目标:一个数组array,给定一个pivotIndex,要求将array[pivotIndex]的对象至于storeIndex位置,使得[left,storeIndex)的元素都小于array[pivotIndex],而使得大于[storeIndex,right]的元素都大于等于array[pivotIndex]。

算法步骤:
1、交换array[pivotIndex]和array[right],记前者为pivot
2、用store表示pivotIndex“潜在”可能的存储位置,初始为left。
3、i从left到right依次扫描,每当遇到比pivot小的元素,则放入store,并store++。
4、重复上述2-3直到i扫描完最右侧
5、交换array[store]和array[right](切忌忘记right里存得可是pivot)。

Leave a Reply

Your email address will not be published.