Sorting is the process of rearranging a group of objects in some logical order.

Selection sort

For array ARR, sorting from small to large, the algorithm steps are as follows:

  1. For arr[I], find the interval [I + 1,n] min index index;

  2. Swap arr[I] and arr[index].

Features:

  1. The running time is independent of whether the input is ordered or not;

  2. The least data movement, only N swaps.

Code implementation:

public static class Selection {
    public static void sort(Comparable[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            Comparable ele = arr[i];
            int min = i;
            for (int j = i + 1; j < arr.length; j++)
                if(less(arr[j], arr[min])) min = j; exch(arr, min, i); }}}Copy the code

Insertion sort

For array ARR, sorting from small to large, the algorithm steps are as follows:

  1. For ARr [I], the left side is kept in order and the interval [0, I] is judged. If ARr [I] < ARr [i-1], the large value moves right.

  2. Until arr[I] >= arr[i-1] ends shift right and insert arr[I].

Code implementation:

public static class Insert {
    public static void sort(Comparable[] arr) {
        for (int i = 1; i < arr.length; i++) {
            Comparable temp = arr[i]; // The element to insert
            int j = i;
            while (j > 0 && less(temp, arr[j - 1])) {
                arr[j] = arr[j - 1];
                j--;
            }
            if(j ! = i) {// There is a changearr[j] = temp; }}}}Copy the code

Hill sorting

Hill sort is optimized based on insertion sort.

Insertion sort is slow for large arrays of random numbers because it swaps only adjacent elements, so elements can be moved from one end of the array to the other, which is inefficient.

Hill’s idea of sorting is that any element with h interval in an array is ordered, and such an array is called an H-ordered array. In other words, an h ordered array is an array composed of H independent ordered arrays woven together. This way, when sorting, if h is large, we can move the elements far away, making it easier to order smaller h.

Code implementation:

public static class Shell {
    public static void sort(Comparable[] arr) {
        int N = arr.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1;
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                Comparable temp = arr[i]; // The element to insert
                int j = i;
                while (j >= h && less(temp, arr[j - h])) {
                    arr[j] = arr[j - h];
                    j -= h;
                }
                if(j ! = i) { arr[j] = temp; } } h /=3; }}}Copy the code

Merge sort

To sort an array, recursively divide it into two parts and then merge the result.

Algorithm implementation:

public static class Merge {
    private static Comparable[] aux;

    public static void sort(Comparable[] arr) {
        aux = new Comparable[arr.length];
        sort(arr, 0, arr.length - 1);
    }

    / / recursion
    public static void sort(Comparable[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(arr, lo, mid);
        sort(arr, mid + 1, hi);
        merge(arr, lo, mid, hi);
    }

    // Bottom-up
    public static void sort2(Comparable[] arr) {
        aux = new Comparable[arr.length];
        for (int sz = 1; sz < arr.length; sz = sz + sz) {
            for (int lo = 0; lo < arr.length - sz; lo += sz + sz) {
                merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, arr.length - 1)); }}}private static void merge(Comparable[] arr, int lo, int mid, int hi) {
        // Merge arr[mid] and arr[mid+1,hi]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++)
            aux[k] = arr[k];
        for (int k = lo; k <= hi; k++) {
            if (i > mid) arr[k] = aux[j++];
            else if (j > hi) arr[k] = aux[i++];
            else if (less(aux[i], aux[j])) arr[k] = aux[i++];
            elsearr[k] = aux[j++]; }}}Copy the code

Quick sort

Based on the divide-and-conquer idea, quicksort divides an array into two subarrays, and the two parts are sorted independently.

Quicksort and merge sort are complementary: merge sort divides an array into two subarrays, and merges the ordered subarrays to sort the entire array.

Quicksort sorts an array in such a way that when both subarrays are ordered the entire array is ordered.

The left half of quicksort is not greater than a certain value, and the right half is not less than a certain value.

Algorithm implementation:

public static class Quick {
    private static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        // partition
        int index = partition(arr, start, end);

        // sort left
        sort(arr, start, index - 1);
        // sort right
        sort(arr, index + 1, end);
    }

    private static int partition(int[] arr, int start, int end) {
        int partition = arr[end]; // Use this data as a partition
        int counter = start; // Left of counter is all data smaller than partition

        for (int i = start; i < end; i++) {
            if (arr[i] < partition) { // Move to the left
                exch(arr, i, counter++);
            }
        }
        exch(arr, end, counter);
        return counter;
    }

    private static void exch(int[] arr, int a, int b) {
        inttemp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }}Copy the code