核心:
- 每次以left index作为基准数字
- 先从右向左找第一个比基准数字小的数,再从左向右找比基准数字大的数。这样最后leftPoint == rightPoint 时,nums[rightPoint] 总是比基准数字小或者就是基准数字,可以放心的交换,保证交换后的nums[left] 不大于基准数字
- 和基准数字相同的数不用管,经过递归后,总能交换到基准数字附近
- 每递归一次,就能保证基准数字在准确的index上,并且左边的数不大于基准数字,右边的数不小于基准数字
- 归并排序的目的是先让小范围数组有序,再让大范围数组有序
package com.company;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] nums= new int[]{6,4,2,6,7,4,8,9,3,1};
quickSort(nums, 0, nums.length);
System.out.println(Arrays.toString(nums));
}
public static void quickSort(int[] nums, int left, int right) {
if(left >= right) {
return;
}
int standard = nums[left];
int leftPoint = left;
int rightPoint = right-1;
while(leftPoint<rightPoint) {
while (nums[rightPoint] >= standard && leftPoint<rightPoint){
rightPoint--;
}
while (nums[leftPoint] <= standard && leftPoint<rightPoint) {
leftPoint++;
}
if(leftPoint < rightPoint) {
int temp = nums[leftPoint];
nums[leftPoint] = nums[rightPoint];
nums[rightPoint] = temp;
}
}
nums[left] = nums[leftPoint];
nums[leftPoint] = standard;
quickSort(nums, left, leftPoint);
quickSort(nums, leftPoint+1, right);
}
}