java惯用排序算法总结<二>【转】

java常用排序算法总结<二>【转】

第二种实现（partition2方法）：
以第一个元素为中枢元素，刚开始时使用低指针指向中枢元素。当中枢元素在低指针位置时，此时我们判断高指针指向的元素是否小于中枢元素，如果大于中枢元素则高指针继续向头移动，如果小于则与中枢元素交换，此时中枢元素被移到了高指针位置；当中枢元素在高指针位置时，我们此时判断低指针指向的元素是否大于中枢元素，如果小于中枢元素则低指针继续向尾移动，如果大于则与中枢元素交换，此时中枢元素又回到了低指针位置；这时是拿高还是低指针所指向的元素与中枢比较时根据前面逻辑来处理，直到高低指针指向同一位置则完成一轮排序，然后再对中枢元素两边的序列进行同样的操作直到排序完成
此种实现逻辑比较好理解，中枢元素的永远在低指针或指针所指向的位置，每次找到需处理的元 素后，要与中枢交换，中枢就像皮球一样从这里踢到那里，又从那里踢到这里。但此种实现会频繁地交换中枢元素，性能可能不如第一种

第三种实现（partition3方法）：
此种方式与前两种方式不太一样，同时移动高低指针，低指针向尾找出大于等于中枢的元素，而高向头找出小于中枢的元素，待两者都找出后交换高低指针所指向的元素，直到高低指针指向同一位置止，然后比较中枢与高低指针所指向的元素大小，如果中枢元素大，则直接与高低指针元素交换，如果中枢元素小于等于高低指针元素，则中枢元素与高低指针前一元素交换，完成一轮比较，然后再对中枢元素两边的序列进行同样的操作直到排序完成

此种方式有点难度，在移动元素时要注意的是：与中枢相等的元素也要向集合后部移动，不然的话如[3,3,0,3,3]第一轮排序结果不准确，虽然最后结果正确。当中枢后面的元素集合移动完成后，还得要把中枢元素放置在集合中的合适位置，这就需要找准集合中前部分与后部分的边界，最后只能把中枢元素与最后一个小于中枢的元素进位置互换。但此种实现方式与第一种有点像，也不需要把中枢元素调来调去的，而是待后面集合排序完成后将中枢放入适当位置


?

原文：http://jiangzhengjun.iteye.com/blog/547735

代码准确率再高点就很好了