思想:
- 在待排序的元素任取一个元素作为基准(通常选第一个元素,但最的选择方法是从待排序元素中随机选取一个作为基准),称为基准元素;
- 将待排序的元素进行分区,比基准元素大的元素放在它的右边,比其小的放在它的左边;
- 对左右两个分区重复以上步骤直到所有元素都是有序的。
所以把快速排序联想成东拆西补或西拆东补,一边拆一边补,直到所有元素达到有序状态。
public static int[] quick(int [] arr,int start,int end) {
//设置变量
int left = start;
int right = end;
int temp = 0;
//left 必须小于等于 right
if (left <= right) {
//设置基准
temp = arr[start];
//设置循环条件,等到left=right时填入基准temp
while (left!=right){
//循环找出小于temp的数组值的下标
while (right>left&&arr[right]>=temp) {
right--;
}
//赋值
arr[left] = arr[right];
//循环找出大于temp的数组值的下标
while (left<right&&arr[left]<=temp) {
left++;
}
//赋值
arr[right]=arr[left];
}
//填入基准
arr[right] = temp;
//根据基准分为两边,分别进行递归
quick(arr,start,left-1);
quick(arr,right+1,end);
}
return arr;
}
链接
https://www.cnblogs.com/brady-wang/p/15157250.html