Introduction:

There are two kinds of comparison algorithms, one is comparison algorithm, the other is non comparison algorithm.

1. Comparison algorithms are: bubble sort, select sort, insert sort, merge sort, heap sort, fast sort, Hill sort.
2. Non comparison algorithms are: count sort, cardinality sort, bucket sort.

https://gitee.com/linqiankun/Utils/tree/v3.0/

Time complexity:

Ranking method	Best case	Average condition	Worst case	Auxiliary space	stability
Bubble sort	n	n^2	n^2	1	yes
Selection sort	n^2	n^2	n^2	1	no
Insertion sort	n	n^2	n^2	1	yes
Merge sort	nlogn	nlogn	nlogn	n	yes
Heap sort	nlogn	nlogn	nlogn	1	no
Quick sort	nlogn	nlogn	n^2	1	no
Shell Sort	n^1.3	nlogn～n^2	n^2	logn~n	no

Comparison algorithm:

Bubble sort

General bubble sorting

Bubble sorting is a very simple sorting algorithm. By looping through the elements in the array, the two adjacent elements are compared in turn. If the sorting rules are not met, the position exchange is carried out until no element needs to be exchanged, and the sorting is completed.

This algorithm will slowly make the elements float out in the required order.

Time complexity: O(n) - O (n ^ 2) - O (n ^ 2)

Bubble sort run order:

public static void bubbleSorted(int[] array, StatusCode statusCode) {
    //The outer loop is finished, and the array sorting is finished
    for (int i = 0; i < array.length; i++) {
        //After the inner loop runs for one loop, an ordered data will be added at the end of the array
        for (int j = 0; j < array.length; j++) {
            int falg = SortUtil.compare(array[i], array[j]);
            //The sorting direction can be modified
            if (falg == statusCode.getCode()) {
                //Exchange data location
                SortUtil.swap(array, i, j);
            }
        }
    }
}

Cocktail sort

The two-level cycle of common bubble sorting is constantly compared from front to back, and the cocktail sorting is optimized. The comparison order is modified to a comparison rule that shrinks from front to back to middle. From the front to the back, it can be determined that the last element of the queue is the largest, and from the back to the front, it can be determined that the starting element of the queue is the smallest, so that the sorting is completed at the end of the middle.

public static void CocktailSort(int[] array, int n) {
    int left = 0;                            // Initialization boundary
    int right = n - 1;
    while (left < right) {
        for (int i = left; i < right; i++)   // First half round, put the largest element behind
        {
            if (array[i] > array[i + 1]) {
                SortUtil.swap(array, i, i + 1);
            }
        }
        right--;
        for (int i = right; i > left; i--)   // In the second half, put the smallest element in front
        {
            if (array[i - 1] > array[i]) {
                SortUtil.swap(array, i - 1, i);
            }
        }
        left++;
    }
}

Selection sort

Select sorting to determine the front end of the array as the sorted queue. Select the best elements satisfying the sorting rules from the subsequent unsorted queues each time and place them at the end of the sorted queue until all the unsorted queues are sorted.

Bubble sorting moves all the data to the right place by exchanging the positions of adjacent data. Select sort every time you traverse, you can select the data you need to place it in the right place.

Time complexity: O(n^2)~O(n^2)~O(n^2)

Select sort run order:

public static void selectionSorted(int[] array, StatusCode statusCode) {
    //Determine the minimum position
    for (int i = 0; i < array.length; i++) {
        
        int min = i;
        //Determine the data stored in the smallest location
        for (int j = i + 1; j < array.length; j++) {
            //Use the flag to find the smallest / largest
            if (statusCode.getCode() == SortUtil.compare(array[j], array[min])) {
                min = j;
            }
        }
        //Put the smallest first
        if (min != i) {
            SortUtil.swap(array, i, min);
        }
    }
}

Insertion sort

Normal insertion sort

Insert a sort to determine the front end of the array as a sorted queue. The first element of the unsorted queue is selected in each traversal and inserted into the sorted queue by comparison. Until all data is sorted.

Select the appropriate place in the unsorted queue, insert the first place. The selection sort comparison occurs when the selection data is not sorted in the queue. Insert sort comparison occurs when the sorted queue is looking for the appropriate location.

Time complexity: O(n)~O(n^2)~O(n^2)

Execution sequence:

public static void insertionSorted(int[] array, StatusCode statusCode) {
    //By default, the 0 is sorted, i is sorted before
    for (int i = 1; i < array.length; i++) {
        int get = array[i];
        int j = i - 1;
        //Search forward from the reverse of current bit value
        while (j >= 0 && statusCode.getCode() == SortUtil.compare(get, array[j])) {
            array[j + 1] = array[j];
            j--;
        }
        //Place on the right side of the position if the comparison conditions are not met
        array[j + 1] = get;
    }

}

Bisection insertion sort

Insertion sorting needs to find out the appropriate location of the selected data in the sorted queue. The search algorithm can be modified to binary search to improve efficiency.

public static void insertionSortedDichotomy(int[] array, StatusCode statusCode) {
        for (int i = 1; i < array.length; i++) {
            int get = array[i];
            int left = 0;
            int right = i - 1;
            //The location of binary search data is also in the previous queue
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (statusCode.getCode() == SortUtil.compare(get,array[mid]))
//                if (array[mid] > get)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            //It takes the data of position i, and moves backward after left
            for (int j = i - 1; j >= left; j--)
            {
                array[j + 1] = array[j];
            }
            array[left] = get;
        }
    }
}

Merge sort

In my opinion, merging and sorting is a kind of divide and rule thought, which can solve the problem by making the big things smaller and smaller. Merge sort merges two sorted arrays into a sorted array to complete the sorting of the array. The idea of recursion can be adopted, starting from the merging of two or two, to the merging of four or four, and the merging of eight or eight, until all the data are sorted.

Time complexity: O(nlogn)~O(nlogn)~O(nlogn)

Execution sequence:

Merge sort

public static void mergeSortedRecursion(int[] array, StatusCode statusCode, int left, int right) {
    if (left == right)
        return;
    int mid = (left + right) / 2;
    //First half array merging
    mergeSortedRecursion(array, statusCode, left, mid);
    //Merging of the second half array
    mergeSortedRecursion(array, statusCode, mid + 1, right);
    //Merging and merging
    merge(array, statusCode, left, mid, right);
}

Array merging algorithm

private static void merge(int[] array, StatusCode statusCode, int left, int mid, int right) {
    int len = right - left + 1;
    int[] temp = new int[len];
    int index = 0;
    //First half array start
    int i = left;
    //Start of the second half array
    int j = mid + 1;
    //Merging operation of two groups of data
    while (i <= mid && j <= right) {
        temp[index++] = statusCode.getCode() == SortUtil.compare(array[i], array[j]) ? array[i++] : array[j++];
    }
    //The above loop cannot loop all the data of two subarrays to
    while (i <= mid) {
        temp[index++] = array[i++];
    }
    while (j <= right) {
        temp[index++] = array[j++];
    }
    //Put the data into the original
    int tindex = 0;
    while (tindex < temp.length) {
        array[left++] = temp[tindex++];
    }

}

Heap sort

Heap sorting is a sort algorithm based on the data structure of heap. Sort by constructing an unordered array into a large top heap or a small top heap.

Time complexity: O(nlogn)~O(nlogn)~O(nlogn)

Execution rules:

Heap sorting algorithm

void HeapSort(int A[], int n)
{
    int heap_size = BuildHeap(A, n);    // Build a maximum heap
    while (heap_size > 1)    　　　　　　 // The number of heap (unordered area) elements is greater than 1, and sorting is not completed
    {
        // Swap the top element of the heap with the last element of the heap and remove the last element from the heap
        // The exchange operation here is likely to disrupt the stability of the following elements, so heap sorting is an unstable sorting algorithm
        Swap(A, 0, --heap_size);
        Heapify(A, 0, heap_size);     // Start with the new heap top element and adjust the heap downward, time complexity O(logn)
    }
}

Heap algorithm

int BuildHeap(int A[], int n)           // Heap building, time complexity O(n)
{
    int heap_size = n;
    for (int i = heap_size / 2 - 1; i >= 0; i--) // Heap adjustment from each non leaf node down
        Heapify(A, i, heap_size);
    return heap_size;
}

Heap adjustment algorithm

void Heapify(int A[], int i, int size)  // Heap adjustment from A[i] down
{
    int left_child = 2 * i + 1;         // Left child index
    int right_child = 2 * i + 2;        // Right child index
    int max = i;                        // Select the maximum of the current node and its left and right children
    if (left_child < size && A[left_child] > A[max])
        max = left_child;
    if (right_child < size && A[right_child] > A[max])
        max = right_child;
    if (max != i)
    {
        Swap(A, i, max);                // Exchange the current node with its largest (direct) child node
        Heapify(A, max, size);          // Recursive call, continue heap adjustment from current node down
    }
}

Quick sort

The rapid sorting of personal feeling is another way of merging and sorting. Through the process of dividing an array into two partitions according to the datum data, and then dividing the partitions recursively, we know that all data segmentation and sorting are completed.

Time complexity: O(nlogn)~O(nlogn)~O(n^2)

Execution sequence:

Quick sort

public static void quickSorted(int[] array, int left, int right, StatusCode statusCode) {
    if (left >= right)
        return;
    int pivot_index = partition(array, left, right, statusCode); // Index of datum
    //Divide recursively
    quickSorted(array, left, pivot_index - 1, statusCode);
    quickSorted(array, pivot_index + 1, right, statusCode);
}

Divide and conquer block

private static int partition(int[] array, int left, int right, StatusCode statusCode)  // Partition function
    {
        int pivot = array[right];               // Here, the last element is selected as the benchmark every time
        int tail = left - 1;                // tail is the index of the last element of the subarray less than the benchmark
        for (int i = left; i < right; i++)  // Traverse elements other than benchmark
        {
            //It will destroy the stability
            if (SortUtil.compare(pivot, array[i]) == 0 || !(statusCode.getCode() == SortUtil.compare(pivot, array[i])))
//            If (array [i] < = pivot) / / put the elements less than or equal to the benchmark to the end of the previous sub array
            {
                SortUtil.swap(array, ++tail, i);
            }
        }
        SortUtil.swap(array, tail + 1, right);           // Finally, the benchmark is placed behind the previous subarray, and the remaining subarray is the subarray larger than the benchmark
        // This operation is likely to disrupt the stability of subsequent elements, so fast sorting is an unstable sorting algorithm
        return tail + 1;                    // Returns the index of the benchmark
    }
}

Shell Sort

Split the queues to be sorted by selecting different cloth lengths. The insertion order is used within each group. By continuously splitting and sorting, the unordered queue will be changed to be more and more orderly. When the cloth length is 1, the last sorting (insertion sorting) is performed to complete the sorting of the queue.

The time consumption of the last sorting can be reduced by continuously splitting and sorting through the hill value. It can effectively reduce the time consumption of moving array elements.

Time complexity: O(n^1.3)~O(nlogn)~O(n^2)~O(n^2)

Execution sequence:

public static void shellSorted(int[] array, StatusCode statusCode) {
    int shell = 0;
    //Find the maximum Hill value
    while (shell <= array.length) {
        shell = shell * 3 + 1;
    }
    //Reduce sorting complexity through Hill
    while (shell >= 1) {
        //After determining the hill value, the internal use is to insert the sorting directly
        for (int i = shell; i < array.length; i++) {
            int j = i - shell;
            int get = array[i];
            while (j >= 0 && statusCode.getCode() == SortUtil.compare(get, array[j])) {
                array[j + shell] = array[j];
                j = j - shell;
            }
            array[j + shell] = get;
        }
        //jian
        shell = (shell - 1) / 3;
    }
}