手撸快速排序 -- java 排序算法之快速排序(左右指针法)

时间:2022-10-11 00:59:00


基本思路:

1.将数组的第一作为基准数 stone 。
2.以 stone 进行分组,左边要小于或等于 stone ; 右边大于或等于 stone ; 

例:[12, 21, 3, 5, 2, 18]  以 12 为 stone  low = 0 ; hi = array.length-1;

分组过程:

记录 stone  index

int oldIndex = low; 

hi 开始向前找比 stone 大的的数(hi 找大最后大的全移右边),循环找 比 low< hi,由右向左找  stone 值 和rray[hi]比较,找不到hi- -找到,退出循环;

while(low<hi&&rray[hi] >= stone)
{
hi--
}

从数组的首元素 low 开始向后找比 stone 的数(low 找小,小的最后全移左边),循环找low <hi,由左向右,low++ 找到,退出循环;

while(low<hi&&rray[low] <= stone)
{
low++
}

找到后然后两者交换(swap),

if(low<hi)
{
array[low],arry[hi],交换
}

再循环,直到 low<hi终止;最后判断,if(low==hi)  移 stone 到正确位置,完成分组,以stone 划分 左边小,右边大;

if(low==hi)
{
array[oldInde ], array[low] 交换
}

记下当前 divideIndex ;
3.再对左组小值组,递归 hi = divideIndex -1; 右值组 递归 low = divideIndex +1,直到各区间只有一个数。

快速排序之左右指针排序前:[12, 21, 3, 5, 2, 18]
left ,right swap low:1 hi:4 array:[12, 2, 3, 5, 21, 18]
stone Index :0 divideIndex:3 move stone swap :[5, 2, 3, 12, 21, 18]
stone Index :0 divideIndex:2 move stone swap :[3, 2, 5, 12, 21, 18]
stone Index :0 divideIndex:1 move stone swap :[2, 3, 5, 12, 21, 18]
stone Index :4 divideIndex:5 move stone swap :[2, 3, 5, 12, 18, 21]
快速排序之左右指针排序后:[2, 3, 5, 12, 18, 21]

 

import java.util.Arrays;

/**
* 第次以 array[low ] 为 stone 划分两部分,最后记得把 stone 放到中间位置;递归,最后可得到结果;
*
* @author jacli
*
*/

public class quickSort {

public static void swap(int[] array, int low, int hi) {
int tmp = array[low];
array[low] = array[hi];
array[hi] = tmp;
}

public static int getDivideIndex(int[] array, int low, int hi) {
int stoneValue = array[low];
// save stone index 最后记得把 stone 放到中间位置
int oldStoneIndex = low;
while (low < hi) {
// first hi

// hi 从右向左移,如果 值小于 stone hi ++ ;如果大于去和左边low互换,小值 最后全跑左边
while (low < hi && array[hi] >= stoneValue) {
hi--;
}

// low 从左向右移,如果 值小于 stone hi ++ ;如果大于去和左边low互换,小值 最后全跑左边
while (low < hi && array[low] <= stoneValue) {
low++;
}
// 互换 low,hi 值,小值跑左边,大值跑右边;
if (low < hi) {
swap(array, low, hi);
System.out.println("left ,right swap low:" + low + " hi:" + hi
+ " array:" + Arrays.toString(array));
}
}
// 最后把 stone 移到相应位置
if (low == hi) {
swap(array, oldStoneIndex, hi);
System.out.println("stone Index :" + oldStoneIndex
+ " divideIndex:" + hi+ " move stone swap :"
+ Arrays.toString(array));
}

return low;
}

public static void quickSort(int[] array, int low, int hi) {
if (low < hi) {
// array[low] get divideIndex divice two part;
int divideIndex = getDivideIndex(array, low, hi);
// 由 stone 分两部分,左边小值,右边大值
// 继续递归
quickSort(array, low, divideIndex - 1);
quickSort(array, divideIndex + 1, hi);

}
}

public static void main(String[] args) {

int[] arrays = { 12, 21, 3, 5, 2, 18 };

System.out.println("快速排序之左右指针排序前:" + Arrays.toString(arrays));
quickSort(arrays, 0, arrays.length - 1);
System.out.println("快速排序之左右指针排序后:" + Arrays.toString(arrays));
}

}