This article has been accepted by Github github.com/silently952…

IDEA plug-ins commonly used by programmers: github.com/silently952…

Fully open source Taoke project: github.com/silently952…

Wechat official account: Beta learning Java

preface

Quicksort can be said to be the most widely used sorting algorithm, the main characteristic is based on in-place sorting (do not need to use auxiliary array, save space); In fact, for an array of length N, the time of quicksort is NlogN; Previous articles have also discussed other sorting algorithms, but failed to combine these two features.

Quicksort idea

Quicksort is also a divide-and-conquer sorting algorithm, which divides an array into two subarrays and then sorts the subarrays recursively to ensure that the entire array is in order.

Algorithm idea:

  1. Select a shard element at random, usually the first element of the array
  2. Scan from the left side of the array for values greater than or equal to the shard element, scan from the right side of the array for values less than or equal to the shard element, and swap the two values
  3. Loop this process until the left and right Pointers meet, thus arranging an element that ensures that the value on the left of the shard element is less than its value and the value on the right is greater than its value
  4. Recursively, this is what keeps the array in order

Algorithm implementation

According to the idea of quicksort algorithm, we can write the first version of implementation:

public class QuickSort implements SortTemplate { @Override public void sort(Comparable[] array) { quickSort(array, 0, array.length - 1); } private void quickSort(Comparable[] array, int lo, int hi) { if (lo >= hi) { return; } int partition = partition(array, lo, hi); quickSort(array, lo, partition - 1); quickSort(array, partition + 1, hi); } private int partition(Comparable[] array, int lo, int hi) { int i = lo, j = hi + 1; Comparable el = array[lo]; while (true) { while (less(array[++i], el)) { if (i == hi) { break; } } while (less(el, array[--j])) { if (j == lo) { break; } } if (i >= j) { break; } exch(array, i, j); } exch(array, lo, j); return j; }}Copy the code

See the previous article “Common primary sorting algorithm, this time all understand” for the implementation of exCH and less methods.

This code is a general implementation of quicksort. Consider a worst-case scenario where the array to be sorted is already sorted [1,2,3,4,5,6,7,8].

For an array of length N, the worst case is N minus 1 recursion, so the time is O(N ^ 2), so to avoid that, let’s see how we can improve the algorithm

Algorithm to improve

  • Guaranteed randomness

To avoid the worst-case scenario, there are two ways to randomly shuffle the array before sorting it. Select the first partition element randomly from the partition method.

private int partition(Comparable[] array, int lo, int hi) {
    int i = lo, j = hi + 1;
    int random = new Random().nextInt(hi - lo) + lo;
    exch(array, lo, random);
    Comparable el = array[lo];
    while (true) {
        while (less(array[++i], el)) {
            if (i == hi) {
                break;
            }
        }
        while (less(el, array[--j])) {
            if (j == lo) {
                break;
            }
        }
        if (i >= j) {
            break;
        }
        exch(array, i, j);
    }
    exch(array, lo, j);
    return j;
}
Copy the code
  • Switch to insert sort

Just like merge sort, we switch to insert sort for small arrays

private void quickSort(Comparable[] array, int lo, int hi) { if (lo >= hi) { return; } if (hi-lo < 5) {insertionSort(array, lo, hi); return; } int partition = partition(array, lo, hi); quickSort(array, lo, partition - 1); quickSort(array, partition + 1, hi); } private void insertionSort(Comparable[] array, int lo, int hi) {for (int I = lo; i <= hi; i++) { for (int j = i; j > lo && less(array[j], array[j - 1]); j--) { exch(array, j, j - 1); }}}Copy the code
  • Three-way split

When a large number of duplicate elements appear in the array that we need to sort, the recursive quicksort we implement will encounter many completely duplicate subarrays, and our algorithm will still slice them, there is a lot of room for improvement.

The idea is to select a shard element (EL) at random, and then switch the array into three parts: greater than, equal to, and less than. All the values equal to the shard element can be arranged in one recursive way. Maintain a pointer lt, gt, such that a[lo..lt-1] is less than the shard element, a[gt+1..hi] is greater than the shard element;

  • Initialize variables: lt=lo, I =lo+1, gt=hi
  • if a[i] < el ; Swap a[I] with a[lt], I ++, lt++
  • if a[i] > el ; Swap a[gt] with a[I], gt–
  • a[i] == el; i++

Code implementation:

public class Quick3waySort implements SortTemplate { @Override public void sort(Comparable[] array) { quickSort(array, 0, array.length - 1); } @SuppressWarnings("unchecked") private void quickSort(Comparable[] array, int lo, int hi) { if (lo >= hi) { return; } int lt = lo, i = lo + 1, gt = hi; Comparable el = array[lo]; while (i <= gt) { int tmp = el.compareTo(array[i]); if (tmp > 0) { exch(array, lt++, i++); } else if (tmp < 0) { exch(array, i, gt--); } else { i++; } } quickSort(array, lo, lt - 1); quickSort(array, gt + 1, hi); }}Copy the code

Finally (pay attention, don’t get lost)

There may be more or less deficiencies and mistakes in the article, suggestions or opinions are welcome to comment and exchange.

Finally, writing is not easy, please do not white whoring I yo, I hope friends can point comment attention to three even, because these are all the power source I share 🙏

All source code has been put into github repository github.com/silently952…