1. An overview of the

Sorting algorithm is divided into internal sorting and external sorting. Internal sorting puts data records in memory for sorting, while external sorting cannot hold all sorting records at one time due to the large amount of sorted data, so it needs to access external storage in the sorting process.

Eight sorting algorithms often mentioned refers to the internal sorting algorithm of eight, bubble sort, quick sort, direct insertion sort, hill sorting, simple selection sort, heap sort, merge sort, and radix sort, if according to the principle of division, bubble sort and quick sort belong to exchange sort, direct insertion sort and hill belongs to insertion sort, Simple selection sort and heap sort are selective sorts, as shown in the figure above.

2. Bubble sort

2.1 Basic Ideas

Bubble Sort is a simple sorting algorithm. It iterates through the sequence to be sorted, comparing two elements at a time, and swapping them if they are in the wrong order. Access to a sequence is repeated until there is no more data to exchange, that is, the sequence has been sorted. The algorithm gets its name from the fact that smaller elements slowly “float” to the top of the list via exchange, like bubbles floating from the bottom to the surface of water.

2.2 Algorithm Description

The algorithm process of bubble sort algorithm is as follows:

①. Compare adjacent elements. If the first one is bigger than the second, swap them both.

②. Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number.

Repeat this step for all elements except the last one.

Repeat steps ① to ③ for fewer and fewer elements at a time until there are no more pairs to compare.

2.3 Code Implementation

package com.fufu.algorithm.sort;

import java.util.Arrays;

/** * Created by zhoujunfu on 2018/8/2. */
public class BubbleSort {
    public static void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;
        // Outer: requires length-1 loop comparison
        for (int i = 0; i < length - 1; i++) {
            // Inner: the number of pairs of comparisons is required for each loop. After each comparison, the current largest number is put to the last position, so the number of comparisons is decreased once
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j+1]) {
                    // Swap the j and j+1 positions of array
                    swap(array, j, j+1); }}}}/** * Swap array for I and j positions *@paramArray an array of *@paramI sub I star@paramJ sub j star divided by theta
    public static void swap(int[] array, int i, int j) {
        inttemp = array[i]; array[i] = array[j]; array[j] = temp; }}Copy the code

2.4 Algorithm Efficiency

Bubble sort is a stable sorting algorithm, the easiest to implement, and the worst case is that it needs to swap each time, traversing and swapping nearly n²/2 times, with O(n²) time complexity. The best case is for the inner loop to iterate once and find that the sorting is correct, so it exits the loop with time O(n). On average, the time complexity is O(n²). Since only cached temp variables in bubble sort require memory space, the space complexity is constant O(1).

Average time complexity The best situation The worst Spatial complexity
O(n2) O(n) O(n2) O(1)

2.5 Three ways to exchange numbers

Swap (int[] array, int I, int j) swap(int[] array, int I, int j) swap(int[] array, int I, int j) swap(int[] array, int I, int j) swap(int[] array, int I, int j)

package com.fufu.algorithm.sort;

import java.util.Arrays;

/** * Created by zhoujunfu on 2018/9/10. */
public class SwapDemo {

    public static void main(String[] args) {
        // temporary variable method
        int[] array = new int[] {10.20};
        System.out.println(Arrays.toString(array));
        swapByTemp(array, 0.1);
        System.out.println(Arrays.toString(array));
        
        / / arithmetic method
        array = new int[] {10.20};
        swapByArithmetic(array, 0.1);
        System.out.println(Arrays.toString(array));
        
        // bit operation
        array = new int[] {10.20};
        swapByBitOperation(array, 0.1);
        System.out.println(Arrays.toString(array));
    }

    /** * Swap the I and j positions of the array with temporary variables *@paramArray an array of *@paramI sub I star@paramJ sub j star divided by theta
    public static void swapByTemp(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /** * Swap the I and j positions of the array by arithmetic (possible overflow) *@paramArray an array of *@paramI sub I star@paramJ sub j star divided by theta
    public static void  swapByArithmetic(int[] array, int i, int j) {
        array[i] = array[i] + array[j];
        array[j] = array[i] - array[j];
        array[i] = array[i] - array[j];
    }


    /** * Swap the I and j positions of the array with bits *@paramArray an array of *@paramI sub I star@paramJ sub j star divided by theta
    public static void  swapByBitOperation(int[] array, int i, int j) {
        array[i] = array[i]^array[j];
        array[j] = array[i]^array[j]; //array[i]^array[j]^array[j]=array[i]
        array[i] = array[i]^array[j]; //array[i]^array[j]^array[i]=array[j]}}Copy the code

3. Quicksort

3.1 Basic Ideas

Quicksort is an improvement on bubble sort, borrowed from the idea of divide-and-conquer and proposed by C. A. R. Hoare in 1962. Its basic idea is: by a trip to sort to sort data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence.

3.2 Algorithm Description

Quicksort uses a divide-and-conquer strategy to divide a list into two sub-lists. Steps as follows:

1. Pick an element from the sequence, called pivot.

②. Reorder the sequence so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition ends, the benchmark is in the middle of the array. This is called a partition operation.

③ Recursively arrange subarrays of values less than the base element and those greater than the base element.

At the bottom of the recursion, the size of the column is zero or one, so it’s sorted. The algorithm must end because in each iteration it puts at least one element in its final position.

3.3 Code Implementation

①. The digging method is described by pseudocode as follows:

(1) low = L; high = R; The datum is dug out to form the first pit A [low].

(2) High –, from back to forward to find the number smaller than it, after finding the number to fill the previous pit a[low].

(3) low++, from front to back to find the number greater than it, after finding the number also dug to fill the previous pit a[high].

(4) Repeat steps ② and ③ until low==high, and fill the base number into a[low].

Example: an unordered array: [4, 3, 7, 5, 10, 9, 1, 6, 8, 2]

(1) Just dig a hole in the first element (the benchmark element), and the “turnip” (the first element 4) will be used in the “basket” (temporary variable). After digging, the array looks like this: pit, 3, 7, 5, 10, 9, 1, 6, 8,2

(2) Dig right hole and fill left hole: From the right, find an element smaller than “turnip” (element 4), dig out and fill the previous hole. After filling the pit: [2, 3, 7, 5, 10, 9, 1, 6, 8, pit]

(3) Dig left hole and fill right hole: Start from left, find an element larger than “turnip” (element 4), dig out and fill right hole. After filling the pit: [2, 3, pit, 5, 10, 9, 1, 6, 8, 7]

(4) Dig right hole and fill left hole: From the right, find an element smaller than “turnip” (element 4), dig out and fill the previous hole. After pit filling: [2, 3, 1, 5, 10, 9, pit, 6, 8, 7]

(5) Dig left hole and fill right hole: Start from left, find an element bigger than “turnip” (element 4), dig out and fill right hole. After pit filling: [2, 3, 1, pit, 10, 9, 5, 6, 8, 7]

Left pit digging pit right (6) : starting from the right, looking for a smaller than “turnip” element (4) elements, dig out, fill into a pit before, this time in the process of looking for pit, find the last dig a hole, that can be stopped, with the basket of radish, have to do is fill out the pit, and returns the position of the pit, as the central axis of divide and conquer. After filling the pit: [2, 3, 1, 4, 10, 9, 5, 6, 8, 7]

Step 2, step 4, step 6 are actually the same operation, 3 and 5 are the same operation, the code is as follows:

Public static void sort(int arr[], int arr, public static void sort(int arr[], int arr, int high) {if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return; } int left = low; int right = high; int temp = arr[left]; // Dig 1: save the base valuewhile (left < right) {
            while(left < right && arr[right] >= temp) { right--; } arr[left] = arr[right]; // pit 2: find the element smaller than the base from back to front and insert it into the base position pit 1while(left < right && arr[left] <= temp) { left ++; } arr[right] = arr[left]; } arr[left] = temp;} arr[left] = temp; // Fill the base value into pit 3, ready to divide and conquer recursive quicksort system.out.println ("Sorting: " + Arrays.toString(arr));
        sort(arr, low, left-1);
        sort(arr, left + 1, high);
    }
Copy the code

②. Left and right pointer method

Pseudocode description is as follows:

(1) low = L; high = R; Select a[low] as key record.

(2) High –, looking forward for the number less than it

(3) low++, looking backwards for something larger than it

(4) Swap the numbers found in steps (2) and (3)

(5) Repeat (2), (3), keep looking back until left and right meet, then switch key and a[low].

The code is as follows:

/** * Created by zhoujunfu on 2018/8/6. */
public class QuickSort {
    /** * quick sort (left/right pointer method) *@paramArr Array to be sorted *@paramLow Left margin *@paramHigh Right border */
    public static void sort2(int arr[], int low, int high) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;

        int key = arr[left];

        while (left < right) {
            while (left < right && arr[right] >= key) {
                right--;
            }
            while (left < right && arr[left] <= key) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        swap(arr, low, left);
        System.out.println("Sorting: " + Arrays.toString(arr));
        sort2(arr, low, left - 1);
        sort2(arr, left + 1, high);
    }

    public static void swap(int arr[], int low, int high) {
        inttmp = arr[low]; arr[low] = arr[high]; arr[high] = tmp; }}Copy the code

3.4 Algorithm efficiency

Quicksort is not stable, and quicksort may swap elements that are not adjacent each time, so it may break the order between elements that originally had the same value.

Average time complexity The best situation The worst Spatial complexity
O(nlogn) O(nlogn) O(n2) O(1)

4. Insert sort directly

4.1 Basic Ideas

The basic idea of direct insert sort is to compare all the elements in the array to the previously sorted elements, and if the selected elements are smaller than the sorted elements, swap until all the elements have been compared.

4.2 Algorithm Description

In general, insert sorts are implemented on arrays using in-place. The specific algorithm is described as follows:

Starting with the first element, the element can be considered sorted

②. Fetch the next element and scan back to front in the sorted element sequence

③ If the element (sorted) is larger than the new element, move the element to the next position

Repeat step 3 until you find the position where the sorted element is less than or equal to the new element

⑤. After inserting the new element into the position

Repeat steps ② to ⑤

4.3 Code Implementation

Two notations are provided, one is the shift method and the other is the exchange method. In the process of re-insertion, the data larger than the number to be inserted in the ordered sequence is moved backward. Since the data to be inserted will be covered by the movement, additional temporary variables are needed to save the data to be inserted, and the code is implemented as follows:

①. Shift method:

public static void sort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }

        for(int i = 1; i < a.length; i++) { int j = i - 1; int temp = a[i]; // Remove the data to be inserted first, because the backshift process overwrites the data to be insertedwhile(&& a [j] j > = 0 > temp) {/ / if the stay is bigger than to insert the data, will move backward a [j + 1) = a, [j]. j--; } a[j+1] = temp; // Insert data into a position smaller than the data to be inserted}}Copy the code

The swap method does not require extra storage of the data to be inserted, but inserts the data by continuously switching forward strips, similar to bubbling method, until it finds a value smaller than it, that is, the data to be inserted finds its position. ②. Exchange method:

  public static void sort2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        for (int i = 1; i < arr.length; i ++) {
            int j = i - 1;
            while(j >= 0 && arr[j] > arr[i]) { arr[j + 1] = arr[j] + arr[j+1]; Arr [j] = arr[j + 1] -arr [j]; arr[j + 1] = arr[j + 1] - arr[j]; System.out.println("Sorting: "+ Arrays.toString(arr)); }}}Copy the code

4.4 Algorithm Efficiency

Direct insertion sort is not a stable sorting algorithm.

Average time complexity The best situation The worst Spatial complexity
O(n2) O(n) O(n2) O(1)

5. Hill sort

Hill sorting, also known as the descending incremental sorting algorithm, was invented by Shell in 1959. Is a fast and stable version of insert sort.

Hill sort is to divide the whole sequence of records to be sorted into several sub-sequences for direct insertion sort respectively. When the records in the whole sequence are “basically ordered”, the direct insertion sort is carried out for all records successively.

5.1 Basic Ideas

The array to be sorted is grouped according to the step size gap, and then the elements of each group are sorted by direct insertion sort method. Each time to reduce the gap half, cycle the operation; When gap=1, direct insertion is used to complete sorting.

You can see that step size selection is an important part of Hill sorting. Any sequence of steps will work as long as the final step is 1. Generally speaking, the simplest step size is to increment the array by half and then halve it by half each time until the increment is 1. For a better step sequence, see Wikipedia.

5.2 Algorithm Description

Select a delta sequence T1, T2… , where Ti >tj, tk=1; (Generally, the first half of the array length is halved each time until the increment is 1.)

②. Sort the sequence k times according to the number of incremental sequences K;

③. In each sort, according to the corresponding increment TI, the sequence to be sorted is divided into several sub-sequences with length m, and the direct insertion sort is performed on each sub-table respectively. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.

In the picture above: Initially, there is an unordered sequence of size 10.

In the first sorting, we might as well assume that gap1 = N / 2 = 5, that is, the elements separated by 5 form a group, which can be divided into 5 groups.

Next, sort each group by direct insertion sort.

In the second sort, we reduce the gap by half, that is, gap2 = gap1/2 = 2 (integer). Each group of elements separated by 2 can be divided into 2 groups.

Sort each group by direct insertion sort.

In the third order, the gap is halved again, i.e. Gap3 = GAP2/2 = 1. The elements separated by 1 thus form a group, that is, there is only one group. Sort each group by direct insertion sort. At this point, the sorting is done.

Notice that there are two elements 5 and 5 with equal values. We can clearly see that in the sorting process, the two elements are swapped. So hill sort is an unstable algorithm.

5.3 Code Implementation

public class ShellSort {

    public static void sort(int[] arr) {
        int gap = arr.length / 2;
        for(; gap > 0; gap = gap/2) {for(int j = 0; (j + gap) < arr.length; J++) {// keep narrowing gap until 1for(int k = 0; (k + gap) < arr.length; K +=gap) {// Use the current gap for in-group insertion sortif(arr [k] > arr [k + gap]) {/ / exchange operation arr = arr [k] [k] + arr [k + gap]; arr[k+gap] = arr[k] - arr[k+gap]; arr[k] = arr[k] - arr[k+gap]; System.out.println(" Sorting: " + Arrays.toString(arr));
                    }
                }
            }
        }
    }
}
Copy the code

5.4 Algorithm Efficiency

Unstable sorting algorithm, hill sorting is the first breakthrough O(N2) sorting algorithm; It’s an improved version of simple insert sort; It differs from insertion sort in that it compares distant elements first, and direct insertion sort is stable. The time complexity of Hill sort is related to the choice of step size. Shell incremental sort is commonly used, that is, the sequence of N/2. Shell incremental sequence is not the best incremental sequence. Introduction to Hill sort incremental sequences.

6. Select sort

6.1 Basic Ideas

Locate the smallest (largest) element in the unsorted sequence and store it at the start of the unsorted sequence. Of all the sorting methods that rely entirely on swapping to move elements, selective sorting is the best one.

6.2 Algorithm Description

①. Find the element with the smallest keyword from the sequence to be sorted;

②. If the smallest element is not the first element of the sequence to be sorted, swap it with the first element;

③. From the remaining N-1 elements, find the element with the smallest keyword, and repeat steps ① and ② until the end of sorting.

6.3 Code Implementation

public class SelectSort {
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for(int j = i+1; j < arr.length; J ++) {// Select the position with the smallest value after sortingif(arr[j] < arr[min]) { min = j; }}if(min ! = i) { arr[min] = arr[i] + arr[min]; arr[i] = arr[min] - arr[i]; arr[min] = arr[min] - arr[i]; }}}Copy the code

6.4 Algorithm Efficiency

Unstable sorting algorithms, the simplicity and intuitionistic nature of sorting choices make them notoriously slow, and in either case, even if the array is sorted, it will take nearly n ^ 2 /2 traversals to verify it. The only good news is that it doesn’t cost any extra memory.

Average time complexity The best situation The worst Spatial complexity
O(n2) O(n2) O(n2) O(1)

7. Merge sort

Merge sort is an effective sorting algorithm based on merge operation. It was first proposed by John von Neumann in 1945. This algorithm is a very typical application of Divide and Conquer, and each level of divide-and-conquer recursion can be performed simultaneously.

7.1 Basic Ideas

Merge sort algorithm is to merge two (or more than two) ordered tables into a new ordered table, that is, the sequence to be sorted into several sub-sequences, each sub-sequence is ordered. Then the ordered subsequence is combined into a whole ordered sequence.

7.2 Algorithm Description

The recursive method is adopted: ①. Merge each two adjacent digits of the sequence to form floor(N /2) sequences, and each sequence contains two elements after sorting;

②. Merge the above sequences again to form floor(N /4) sequences, each sequence containing four elements;

Repeat step 2 until all elements are sorted

7.3 Code Implementation

package com.fufu.algorithm.sort;

import java.util.Arrays;

/**
 * Created by zhoujunfu on 2018/8/10.
 */
public class MergeSort {

    public static int[] sort(int [] a) {
        if (a.length <= 1) {
            return a;
        }
        int num = a.length >> 1;
        int[] left = Arrays.copyOfRange(a, 0, num);
        int[] right = Arrays.copyOfRange(a, num, a.length);
        returnmergeTwoArray(sort(left), sort(right)); } public static int[] mergeTwoArray(int[] a, int[] b) { int i = 0, j = 0, k = 0; int[] result = new int[a.length + b.length]; // Request extra space to store the merged datawhile(I < a.length &&j < b.length) {// Take the smaller value of the two sequences and put it into a new arrayif (a[i] <= b[j]) {
                result[k++] = a[i++];
            } else{ result[k++] = b[j++]; }}while(I < a. ength) {/ / sequence is a result of superfluous elements into the new array [k++] = [i++] a; }while(j < b.l ength) {/ / redundant elements in sequence b moved into the new array result [k++] [j++] = b; }returnresult; } public static void main(String[] args) { int[] b = {3, 1, 5, 4}; System.out.println(Arrays.toString(sort(b))); }}Copy the code

7.4 Algorithm Efficiency

Average time complexity The best situation The worst Spatial complexity
O(nlogn) O(nlogn) O(nlogn) O(n)

Stable sorting algorithm, from the efficiency point of view, merge sort can be regarded as the “outstanding” sorting algorithm. Assuming that the length of the array is N, it takes logn to split the array, and each step is a common process of merging subarrays. The time complexity is O(n), so the comprehensive time complexity is O(nlogn). On the other hand, the subarrays that are split in the recursive process of merge sort need to be kept in memory space with a space complexity of O(n). As with select sort, merge sort performs independently of the input data, but performs much better than select sort because it is always O(nlogn) time. The trade-off is extra memory.

8. Radix sort

Radix sort is a non-comparative integer sorting algorithm, its principle is to cut the integers into different numbers according to the number of digits, and then compare them according to each number. Since integers can also represent strings (such as names or dates) and floating-point numbers in a particular format, radix sort is not restricted to integers.

8.1 Basic Ideas

All values to be compared (positive integers) are unified into the same digit length, with the shorter digit preceded by zeros. Then, sort the order one by one, starting with the lowest order. So from the lowest order to the highest order, the sequence becomes an ordered sequence.

There are two implementations of radix sort:

MSD (Most Significant Digital) is sorted from the left-most high level. In the same group, the key codes k1 are equal, and then the groups are sorted into subgroups according to K2. After that, the following key codes are sorted into subgroups until the subgroups are sorted according to the lowest key code KD. Then connect the groups together to get an ordered sequence. MSD mode is suitable for sequences with many bits.

LSD (Least Significant Digital) sorts from the lowest to the right. Start with kd, then kD-1, and repeat until k1 is sorted and you get an ordered sequence. LSD is suitable for sequences with few bits.

Below is a schematic diagram of LSD radix sort:

8.2 Algorithm Description

Taking LSD as an example, starting from the lowest level, the specific algorithm is described as follows:

Get the largest number in the array, and get the number of digits; ②. Arr is the original array, and each bit is taken from the lowest level to form the RADIX array; ③. Radix counting sequencing (using counting sequencing for a small range of numbers);

8.3 Code Implementation

Radix sort: Sorting N elements by the values of each element in the sequence through several rounds of “allocation” and “collection”.

Allocation: We take the element in L[I], first determine the digit in its units place, and then assign the digit to the bucket with the same serial number

Collection: When all the elements in the sequence are allocated to the corresponding bucket, the elements in the bucket are collected in sequence to form a new sequence L[]. Repeat allocation and collection of tens, hundreds… in the newly formed sequence L[]. The sorting ends until the highest bits in the sequence are allocated

package com.fufu.algorithm.sort; import java.util.Arrays; Public class RadixSort {public static void main(String[] args) {public static void main(String[] args) { int[] array = {10, 20, 5, 4, 100}; sort(array); } public static void sort(int[] a) {if (a == null || a.length < 0) {
            return;
        }

        int max = a[0];
        for (int i = 0; i <a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        System.out.println("max, " + max);

        int maxDigit = 0;
        while(max ! = 0) { max = max / 10; maxDigit++; } System.out.println("maxDigit, "+ maxDigit); int[][] buckets = new int[10][a.length]; int base = 10; // From low to high, each bit is traversed, and all elements are assigned to the bucketfor(int i = 0; i < maxDigit; i++) { int[] bucketLen = new int[10]; // The number of stored elements in each bucket // Collection: The data in different buckets are retrieved one by one to prepare for the next round of ranking. Since the elements near the bottom of the bucket rank first, they are retrieved from the bottom of the bucket firstfor (int j = 0; j < a.length; j++) {
                int whichBucket = (a[j] % base) / (base / 10);
                buckets[whichBucket][bucketLen[whichBucket]] = a[j];
                bucketLen[whichBucket]++; } int k = 0; // Collect data from different buckets one by one to prepare for the next round of high ranking. Since elements near the bottom of the bucket rank higher, they are retrieved from the bottom of the bucket firstfor (int l = 0; l < buckets.length; l++) {
                for (int m =0; m < bucketLen[l]; m++) {
                    a[k++] = buckets[l][m];
                }
            }
            System.out.println("Sorting: "+ Arrays.toString(a)); base *= 10; }}}Copy the code

8.4 Algorithm Efficiency

Radix sort does not change the relative order of the same elements, so it is a stable sorting algorithm. The complexity of radix sort algorithm is as follows:

Average time complexity The best situation The worst Spatial complexity
O(d*(n+r)) O(d*(n+r)) O(d*(n+r)) O(n+r)

Where d is the number of digits, r is the base number, and n is the number of original arrays. In radix sort, because there is no comparison operation, the complexity of best-case and worst-case is O(d*(n + r)) in time.

Radix sort is more suitable for sorting data such as time, string, etc. whose overall weight is unknown.

(1) The data range is small, and it is recommended to be less than 1000

(2) Each value must be greater than or equal to 0

Radix sort vs counting sort vs bucket sort

These three sorting algorithms all use the concept of buckets, but there are obvious differences in the way buckets are used:

Radix sort: Buckets are allocated according to each digit of the key value. Counting sort: each bucket stores a single key value. Bucket sort: each bucket stores a range of values

Count sort and bucket sort in this article specific will not write, there is a need to baidu.

9. The heap sort

Before looking at heap sort, let’s introduce the following concepts:

Complete binary tree: If the depth of the binary tree is set as H, except for the h layer, the node number of all other layers (1 ~ H-1) reaches the maximum number, and all nodes of the h layer are continuously concentrated on the left, which is a complete binary tree, as shown in the figure below.

Heap: A heap is a complete binary tree with the property that each node has a value greater than or equal to the value of its left and right children, called the big top heap; Or the value of each node is less than or equal to the value of its left and right children, called the small top heap. The diagram below:

At the same time, we number the nodes in the heap by layer, and map this logical structure to an array like this:

The array is logically a heap structure. Let’s use a simple formula to describe the definition of a heap:

Arr [I] >= ARr [2i+1] &&arr [I] >= ARr [2I +2]

Small top heap: ARr [I] <= ARr [2i+1] &&arr [I] <= arr[2i+2]

Ok, so those are the definitions. Next, let’s look at the basic idea and steps of heap sort:

9.1 Basic Ideas

The basic idea of heap sort is to construct the sequence to be sorted as a big top heap, in which the maximum value of the whole sequence is the root node of the top of the heap. Swap it with the trailing element, where the trailing element is the maximum. The remaining n-1 elements are then reconstructed into a heap, which yields the subsmallest values of n elements. Do this repeatedly, and you get an ordered sequence.

9.2 Algorithm Description

Step one constructs the initial heap. The given unordered sequence is constructed into a big top heap (generally the big top heap is used for ascending order and the small top heap is used for descending order).

1. Assume the given unordered sequence structure is as follows

2. At this time, we start from the last non-leaf node (leaf node naturally need not be adjusted, the first non-leaf node arr. Length /2-1=5/2-1=1, namely the following 6 nodes), from left to right, from bottom to top.

3. Find the second non-leaf node 4, since element 9 in [4,9,8] is the largest, 4 and 9 are swapped.

At this time, swapping leads to structural disorder of the child roots [4,5,6], further adjustment,6 is the largest in [4,5,6], and swapping 4 and 6.

At this point, we construct a large top heap from an unnecessary sequence.

Step two swaps the top element with the end element to maximize the end element. We then continue to adjust the heap, swapping the top element with the bottom element to get the second largest element. And so on and so forth.

B. Readjust the structure so that it continues to meet the heap definition

C. Then swap the top element 8 with the bottom element 5 to get the second largest element 8.

The follow-up process, continue to adjust, exchange, so repeated, eventually making the sequence order

The basic idea of heap sorting is summarized briefly:

A. Build the unnecessary sequence into a heap, and select the big top heap or small top heap according to the ascending and descending requirements;

B. Swap the top element with the end element, and “sink” the largest element to the end of the array;

C. Rearrange the structure so that it meets the heap definition, and then continue swapping the top element with the current end element, repeating the adjust + swap step until the sequence is in order.

9.3 Algorithm Implementation

package com.fufu.algorithm.sort; import java.util.Arrays; /** * Created by zhoujunfu on 2018/9/26. */ public class HeapSort { public static void main(String []args){ int []arr = ,6,8,5,9 {4}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int []arr){ //1. Build the big top heapfor(int i=arr.length/2-1; i>=0; AdjustHeap (arr, I,arr.length); } //2. Adjust heap structure + swap top and end heap elementsfor(int j=arr.length-1; j>0; j--){ swap(arr,0,j); AdjustHeap (arr,0,j); // Resize the heap}} /** * Resize the big top heap (only the resize process, * @param arr * @param I * @param length */ public static void adjustHeap(int []arr,int I,int length)  temp = arr[i]; // Get the current element Ifor(int k=i*2+1; k<length; K =k*2+1){// Start at the left child of I, which is 2i+1if(k + 1 < length && arr [k] < arr [k + 1]) {/ / if the left child node is less than the right child node, k k++ pointing in the right child nodes; }if(arr[k] >temp){// If the child is larger than the parent, assign the value of the child to the parent (without swapping) arr[I] = arr[k]; i = k; }else{
                break; } } arr[i] = temp; } /** * swap element * @param arr * @param a * @param b */ public static void swap(int []arr,int a,int b){int temp=arr[a]; arr[a] = arr[b]; arr[b] = temp; }}Copy the code

9.4 Algorithm Efficiency

It is not suitable for small sequences because the heap initialization process is compared more frequently in heap sort. At the same time, the relative order of the same elements is broken due to the multiple exchange of positions between arbitrary subscripts. Therefore, it is an unstable sort.

①. The process of building the heap, from length/2 to 0, the time complexity is O(n);

②. The process of adjusting the heap is to adjust along the parent node of the heap, the number of times is the heap depth, and the time complexity is O(LGN);

③ Heapsort is completed by step ② of N times, and the time complexity is O(NLGN).

Average time complexity The best situation The worst Spatial complexity
O(nlogn) O(nlogn) O(nlogn) O(1)

10. Summary

In terms of time complexity:

(1). Square order O(n²) sort: all kinds of simple sort: direct insertion, direct selection and bubble sort;

(2). Linear log order O(Nlog ₂ N) sort: quick sort, heap sort and merge sort;

(3).o (n1+§)) sort, § is a constant between 0 and 1: Hill sort

(4). Linear order O(N) sort: radix sort, in addition to bucket, box sort.

Time complexity limit:

The sorting algorithm can be less than O(NLGN) if the number being sorted has some property (such as an integer, such as a range). Such as:

The sorting complexity O(k+n) requirements are as follows: The sorted number must be an integer ranging from 0 to K

The cardinality sorting complexity O(d(k+n)) requires d digits, with each digit having k values

Bucket sorting complexity O(n) (average) The sorted numbers must be within a certain range and evenly distributed

However, when the sorted numbers do not have any properties, the comparison-based sorting algorithm is generally used, and the lower limit of the time complexity of the comparison-based sorting algorithm must be O(NLGN). The cost of referring to a lot of efficient sorting algorithms is nlogn, is that the limit of sorting algorithms?

Note When the original table is ordered or basically ordered, direct insert sort and bubble sort can greatly reduce the number of comparison and moving records, and the time complexity can be reduced to O (n).

On the contrary, when the original table is basically ordered, it is degraded to bubble sort, and the time complexity is increased to O (n2).

Whether the original table is ordered or not has little effect on the time complexity of simple selection sort, heap sort, merge sort and radix sort.

11. Reference materials

  1. Summary and Java implementation of eight sorting algorithms
  2. Graphic sorting algorithm (3) heap sorting