Quick Sort

核心:快排是一种采用分治思想的排序算法,大致分为三个步骤。

  1. 定基准——首先随机选择一个元素最为基准
  2. 划分区——所有比基准小的元素置于基准左侧,比基准大的元素置于右侧
  3. 递归调用——递归地调用此切分过程

Java

public static void quickSort(int[] array) {
    quickSort1(array, 0, array.length - 1);
}

public static void quickSort1(int[] nums, int start, int end) {
    if(start>=end) return;
    int pivot = end;
    int left = start;
    int right = end-1;
    while (left <= right) {
        if (nums[left] > nums[pivot]) {
            swap(nums, left, right);
            right--;
        } else {
            left++;
        }
    }
    swap(nums, left, pivot);
    quickSort1(nums, start, left-1);
    quickSort1(nums, left+1, end);
}

public static void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}