This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

One, foreword

Quicksort: it is an efficient sorting algorithm proposed by Tony Hall, abbreviated as quicksort.

Can be summarized by three steps and six words: base selection, segmentation, recursion:

  • Select base: select the base value first

  • Split: Splits the array, putting elements smaller than the base value in front of the base value and elements larger than the base value behind the base value

  • Recursion: Recursively sorts subsequences that are smaller than a reference value and subsequences that are larger than a reference value

Ju Li, the GIF is as follows:

Why is it faster than bubbling?

Because it’s a jump swap, where two elements are exchanged at a distance.





Two, knowledge points

Knowledge points, as follows:

  1. Time complexity
  2. The reverse of
  3. Implementations fall into two categories:
    1. LomutoSegmentation method: simple implementation, not easy to error, poor efficiency
    2. Hall partition method: reduce exchange


(1) Time complexity

  • Best case: Time complexity O(N * logN)

  • Worst case: time complexity O(N ^ 2), delta elements are not mutual, small deltas may not work at all

  • Stability: unstable.

    For example, the original array {4, 1, 4}

    Unstable: The second 4 is ranked before the first 4 in the sorting process.

General sorting diagram, as shown in figure:


(2)

If arr[I] > A [j] for subscript I < j, (I, j) is an inversion pair.

For example, sequence{34, 8, 64, 51, 32, 21}How many inversions are there?

Nine: (34, 8), (34, 32), (34, 21), (64, 51), (64, 32), (64, 21), (51, 32), (51, 21), (32, 21)Copy the code

Obtained theorem:

  • Theorem: ArbitraryNA sequence of different elements has an average ofN(N-1)/4A reverse order to
  • Theorem: The average time complexity of any algorithm that sorts only by swapping two adjacent elements isO(N^2)

So what’s the use of reverse pairs?

  1. It’s the number of swaps you have to make.

  2. It provides the basis for improving the efficiency of the algorithm

In order to improve the efficiency of the algorithm, it is necessary to:

  1. It cancels out more than one inversion pair at a time

  2. Swap two elements far apart at a time


(3) implementation

1)LomutoSegmentation method

The realization is simple, not easy to make mistakes, and the efficiency is poor.

Base line: at the highest point

public class QuickSort {

    // Time: O(n * log(n)), Space: O(n)
    public void lomutoSort(int [] arr) {

        if (arr == null || arr.length == 0) return;
        lomutoSort(arr, 0, arr.length - 1);
    }

    private void lomutoSort(int [] arr, int low, int high) {
        if (low < high) {
            int k = lomutoPartition(arr, low, high);
            lomutoSort(arr, low, k - 1);
            lomutoSort(arr, k + 1, high); }}private int lomutoPartition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low;
        for (int j = low; j < high; ++j) {
            if (arr[j] < pivot) {
                swap(arr, i, high);
                ++i;
            }
        }
        swap(arr, i, high);
        return i;
    }

    private void swap(int[] arr, int i, int j) {
        inttmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }}Copy the code


2) Hall segmentation method

Base line: at the middle point

public class QuickSort {

    // Time: O(n * log(n)), Space: O(n)
    public void hoareSort(int [] arr) {

        if (arr == null || arr.length == 0) return;
        hoareSort(arr, 0, arr.length - 1);
    }

    private void hoareSort(int [] arr, int low, int high) {
        if (low < high) {
            int k = hoarePartition(arr, low, high);
            hoareSort(arr, low, k);
            hoareSort(arr, k + 1, high); }}private int hoarePartition(int [] arr, int low, int high) {
        int pivot = arr[low + (high - low) / 2];
        int i = low, j = high;
        while (true) {
            while (arr[i] < pivot) ++i;
            while (arr[j] > pivot) --j;
            if (i >= j) returnj; swap(arr, i++, j--); }}private void swap(int[] arr, int i, int j) {
        inttmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }}Copy the code