快速排序这几行代码都是啥意思?课堂上ppt写的,让我们理解,麻烦解答一下
private static void quickSort(Integer[] arr, int low,int high){
if(low > high){
return;
}
int i = low;
int j = high;
int temp = arr[low];
while (i < j){
while (i < j && arr[j] >= temp){
j --;
}
while (i < j && arr[i] <= temp){
i ++;
}
if(i < j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[low] = arr[i];
arr[i] = temp;
quickSort(arr,low,i - 1);
quickSort(arr,i + 1,high);
}
知道每一行的含义
快速排序的基本思想。
先从数组中找一个基准数
让其他比它大的元素移动到数列一边,比他小的元素移动到数列另一边,从而把数组拆解成两个部分。
再对左右区间重复第二步,直到各区间只有一个数。
private static void quickSort(Integer[] arr, int low,int high){
//当左边下标大于右边的下标,说明本轮已经完成比较了,直接退出
if(low > high){
return;
}
int i = low;
int j = high;
//哨兵
int temp = arr[low];
while (i < j){
//找到右边大于左边的下标
while (i < j && arr[j] >= temp){
j --;
}
//找到左边小于右边的下标
while (i < j && arr[i] <= temp){
i ++;
}
//到这一步,说明左边大于右边的元素找到了,交换元素
if(i < j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
//哨兵移动到中间位置(比大的小,比小的大的位置)
arr[low] = arr[i];
arr[i] = temp;
//这里为什么是 i - 1、i + 1:因为哨兵已经找到了它位置,不需要再移动了
quickSort(arr,low,i - 1);
//继续按照上面思路继续比较交互
quickSort(arr,i + 1,high);
}