int hoare_partition(int arr[],int start,int end){ int pivot = arr[start]; int i = start; int j = end; while(true){ while(i<j && arr[i]<=pivot) i++; while(i<j && arr[j]>=pivot) j--; if(i<j){ swap(&arr[i],&arr[j]); } else return j; } }应用三 奇偶排序。忘记是哪个公司的面试题了。题目大意是这样的,给定一个数组,数组中元素有奇数有偶数。要求对数组进行处理,使得数组的左边为奇数,右边为偶数 这个题目直接看上去,跟快速排序的划分十分类似,唯一不同的是,不需要返回索引。所以,简单的方式如下:
算法总结:双指针法的常见应用
所谓双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向或者相反方向的指针进行扫描,从而达到相应的目的。当然,我们关心的可以是两个指针指向的元素,也可以是两个指针中间的区域.
换言之,双指针法充分使用了数组有序这一特征,从而在某些情况下能够简化一些运算。
(注:这里的指针,并非专指c中指针的概念,而是指索引,游标或指针,可迭代对象等)
应用一:
给定一个有序递增数组,在数组中找到满足条件的两个数,使得这两个数的和为某一给定的值。如果有多对数,只输出一对即可。
对于这种问题,常见的算法思路不外乎遍历,回溯,但这里,双指针遍历法是一个很有效的方法。具体思路是:初始化两个指针,一个指向数组的第一个元素,另外一个指向数组的最后一个元素,在两个指针相遇之前,指针1只能向前移动,指针2 只能向后移动。比较当前两个指针所指元素和与给定数字的大小,如果和较大,指针2向后移动,如果和较小,指针1向前移动。最终的结果是找到两个满足条件的数或者不存在这样的两个数字。
应用二:hoare的双向扫描快速划分法。快速排序的总结中已经给了思路和代码