快速排序使用分治法策略来把一个序列分为两个子序列,基本步骤为:
public void sort(int[] arr, int left, int right){
if(left >= right){
return;
}
//左边哨兵开始索引
int i = left;
//右边哨兵开始索引
int j = right;
//基准数
int tmp = arr[left];
//只要还满足左侧索引小于右侧索引,就不停的从右侧找比基准数小的,从左侧找比基准数大的,然后交换
//通过交换可以将比基准数大的放到基准数右边,将比基准数小的放到基准数左边
while(i < j){
//先从右边开始找,找到一个比基准数小的停止
while(tmp <= arr[j] && i < j){
j--;
}
//再从左边开始找,找到一个比基准数大的停止
while(tmp >= arr[i] && i < j){
i++;
}
//将左右找到的两个数进行交换
if(i < j){
int m = arr[j];
arr[j] = arr[i];
arr[i] = m;
}
}
//当左侧哨兵和右侧哨兵的索引相等时(既 i=j),结束循环,将基准数与当前位置上的数进行交换
//为啥当 i 和 j 相遇时要将当前位置和基准数交换呢?
//如果是 j 走向 i 导致的相遇,那说明在上一轮 i 这个位子是比基准数大的,通过和 j 交换,
//这时 i 的位子上的数变成了以前 j 位置上的数,因此比基准数小,所以要交换。
//如果是因为 i 走向 j 导致相遇,那说明在这一轮中右侧找到了比基准数小的(就是 j 位置上的数),
//而左侧没找到比基准数大的,此时 i 和 j 位置一样,所以当前位置上的数比基准数小,因此交换。
arr[left] = arr[i];
arr[i] = tmp;
//对左右子集进行递归调用
sort(arr,left,j -1);
sort(arr,j + 1,right);
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。