快速排序原理与代码
程序员文章站
2022-03-24 13:16:12
...
1原理
我们必须首先确定一个基准数,使得序列中比基准数小的数都在左边,比基准数大的数都在右边。如何确定基准数?其实可以任意,不过一般取第一个数或者序列中间位置的数,我们这里取第一个数为基准数
public class QuickSort {
public static void main(String[] args) {
int[] nums = {3, 1, 4, 2, 5, 0};
quickSort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
public static void quickSort(int[] nums, int start, int end) {//在调用quickSort时,start为0,end为数组长度减一
int i = start;
int j = end;
int temp = nums[start];
while (i < j) {
while (i < j && nums[j] >= temp) {
j--;
}
nums[i] = nums[j];
while (i < j && nums[i] <= temp) {
i++;
}
nums[j] = nums[i];
}
nums[i] = temp;//当i==j时,i就是基准数应该摆放的位置
if (i > start + 1) {
//为什么要start+1?因为如果是i>start,有可能是i刚好比start大1,此时就没有必要进行快排,因为i和start位置的俩元素必然有序
quickSort(nums, start, i - 1);
}
if (j < end - 1) {//end-1原理同上
quickSort(nums, j + 1, end);
}
}
}
上一篇: 20210401任务
下一篇: 快速排序的非递归算法