Sorting algorithms have evolved over a long period of time, resulting in many different methods. For beginners, it is very important to organize them for easy understanding and memory. Each algorithm has its own specific application occasion, and it is difficult to be used universally. Therefore, it is necessary to summarize all the common sorting algorithms.

Big sorting can be divided into two categories: internal and external. In the sorting process, all records are stored in memory, which is called internal sorting. If external memory is needed in the sorting process, it is called external sorting. The sorting described below belongs to inner sorting.

Internal ranking can be divided into the following categories:

(1) insertion sort: direct insertion sort, dichotomy insertion sort, Hill sort.

(2) Selective Sorting: Direct Selective Sorting and Heap Sorting.

(3) Exchange Sort: Bubble Sort, Quick Sort.

(4) Merge and Sort

(5) cardinal sorting

Form version

(1) Insertion sort

Thought: At each step, insert a record to be sorted into the appropriate position of the previously sorted word sequence according to the size of its ordinal code until all the insertions have been sorted.  
Key question: Find the right insertion position in the sequence that has already been sorted.  
Method:
Direct insertion sort
Dichotomous insertion sort
Hill sort

(1) Direct insertion sort (insertion after finding the appropriate position from back to front)

1. Basic idea: Insert a record to be sorted into the proper position of the word sequence that has been sorted before according to the size of its sequence code (after finding the right position from back to front), until all the insertions have been sorted.

2. Example

3. Implementation of java

package DirectInsertSort;

public class DirectInsertSort
{

    public static void main(String[] args)
    {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 };
        System.out.println("Before sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
        // Direct insertion sort
        for (int i = 1; i < a.length; i++)
        {
            // Elements to be inserted
            int temp = a[i];
            int j;
            for (j = i - 1; j >= 0; j--)
            {
                // Move one bit back over temp
                if (a[j] > temp)
                {
                    a[j + 1] = a[j];
                }
                else
                {
                    break;
                }
            }
            a[j + 1] = temp;
        }
        System.out.println();
        System.out.println("After sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }

    }

}

(2) Dichotomy insertion sort (find the appropriate insertion position by dichotomy)

1. Basic idea: The idea of dichotomy insertion sort is the same as that of direct insertion, but the way to find the appropriate insertion position is different. Here is to find the appropriate insertion position by dichotomy, which can reduce the number of comparisons.

2. Example

3. Implementation of java

package BinaryInsertSort;

public class BinaryInsertSort
{

    public static void main(String[] args)
    {
        int[] a = { 49, 38, 65, 97, 176, 213, 227, 49, 78, 34, 12, 164, 11, 18, 1 };
        System.out.println("Before sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
        // Bipartite insertion sort
        sort(a);
        System.out.println();
        System.out.println("After sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
    }

    private static void sort(int[] a)
    {
        for (int i = 0; i < a.length; i++)
        {
            int temp = a[i];
            int left = 0;
            int right = i - 1;
            int mid = 0;
            while (left <= right)
            {
                mid = (left + right) / 2;
                if (temp < a[mid])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            for (int j = i - 1; j >= left; j--)
            {
                a[j + 1] = a[j];
            }
            if (left != i)
            {
                a[left] = temp;
            }
        }
    }

}

(3) Hill Ranking

1. Basic idea: First, take an integer d1 less than n as the first increment, and divide all records into d1 groups. All records with multiple distances of d1 are placed in the same group. First, insert the sorting directly within each group; then, take the second increment d2.

package ShellSort;

public class ShellSort
{

    public static void main(String[] args)
    {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 };
        System.out.println("Before sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
        // Shell Sort
        int d = a.length;
        while (true)
        {
            d = d / 2;
            for (int x = 0; x < d; x++)
            {
                for (int i = x + d; i < a.length; i = i + d)
                {
                    int temp = a[i];
                    int j;
                    for (j = i - d; j >= 0 && a[j] > temp; j = j - d)
                    {
                        a[j + d] = a[j];
                    }
                    a[j + d] = temp;
                }
            }
            if (d == 1)
            {
                break;
            }
        }
        System.out.println();
        System.out.println("After sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }

    }

}

SELECTION ORDERING

Thought: Choose the record with the smallest keyword from the list of records to be sorted and place it at the front of the sorted list until it is all sorted.  
Key problem: Find the minimum key code record in the remaining sequence of records to be sorted.  
Method:
Direct Selection Sorting
Heap sort

(1) Direct Selection Sorting

1. Basic idea: In a group of numbers to be sorted, select the smallest number to exchange with the number of the first position; and then find the smallest number to exchange with the number of the second position among the remaining numbers, so as to circle until the penultimate number and the last number are compared.

2. Example

3. Implementation of java

package DirectSelectSort;

public class DirectSelectSort
{

    public static void main(String[] args)
    {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8 };
        System.out.println("Before sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
        // Direct Selection Sorting
        for (int i = 0; i < a.length; i++)
        {
            int min = a[i];
            int n = i; // Minimum Index
            for (int j = i + 1; j < a.length; j++)
            {
                if (a[j] < min)
                { // Find the smallest number
                    min = a[j];
                    n = j;
                }
            }
            a[n] = a[i];
            a[i] = min;

        }
        System.out.println();
        System.out.println("After sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }

    }

}

(2) heap sort

1. Basic Ideas:

Heap sorting is a tree selection sorting, which is an effective improvement on direct selection sorting.

The heap is defined as a sequence of n elements (h1,h2,... (hn), if and only if satisfied (hi > = h2i, hi > = 2I + 1) or (hi < = h2i, hi < = 2I + 1) (i=1,2,... n/2) is called heap. Only heaps satisfying the former condition are discussed here. As can be seen from the definition of heap, the top element (that is, the first element) must be the largest item (the large top heap). Complete binary tree can intuitively represent the structure of the heap. The top of the heap is the root, the others are the left subtree and the right subtree.

Idea: Initially, the sequence of numbers to be sorted is regarded as a binary tree stored sequentially, and their storage order is adjusted to make it a heap. At this time, the number of root nodes of the heap is the largest. Then the root node is exchanged with the last node of the heap. The number of preceding (n-1) is then readjusted to make it a heap. By analogy, until there are only two nodes in the heap and they are exchanged, an ordered sequence of N nodes is finally obtained. From the description of the algorithm, heap sorting requires two processes, one is to build the heap, the other is to exchange the location of the last element between the heap top and the heap. So heap sorting consists of two functions. The first is the permeability function of the reactor, and the second is the function that calls the permeability function repeatedly to achieve sorting.

2. Example

Initial sequence: 46, 79, 56, 38, 40, 84

Build heap:

Exchange, kick out the maximum number from the heap

Analogy in turn: the last two remaining nodes in the final heap are exchanged, kicked out, and sorted.

3. Implementation of java

package HeapSort;

import java.util.Arrays;

public class HeapSort
{
    public static void main(String[] args)
    {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64 };
        int arrayLength = a.length;
        // Cyclic construction
        for (int i = 0; i < arrayLength - 1; i++)
        {
            // Build heap
            buildMaxHeap(a, arrayLength - 1 - i);
            // Exchange heap top and last element
            swap(a, 0, arrayLength - 1 - i);
            System.out.println(Arrays.toString(a));
        }
    }

    // Build a large top heap for data arrays from 0 to lastIndex
    public static void buildMaxHeap(int[] data, int lastIndex)
    {
        // Start with the parent node of the node (the last node) at lastIndex
        for (int i = (lastIndex - 1) / 2; i >= 0; i--)
        {
            // k Saves the node being judged
            int k = i;
            // If the child node of the current k node exists
            while (k * 2 + 1 <= lastIndex)
            {
                // Index of left subnode of k node
                int biggerIndex = 2 * k + 1;
                // If biggerIndex is less than lastIndex, the right child node of k node represented by biggerIndex+1 exists
                if (biggerIndex < lastIndex)
                {
                    // If the value of the right child node is larger
                    if (data[biggerIndex] < data[biggerIndex + 1])
                    {
                        // Bigger Index always records the index of larger subnodes
                        biggerIndex++;
                    }
                }
                // If the value of k node is less than the value of its larger subnode
                if (data[k] < data[biggerIndex])
                {
                    // Swap them
                    swap(data, k, biggerIndex);
                    // Give biggerIndex to k, start the next loop of the while loop, and reassure that the value of K node is greater than that of its left and right sub-nodes.
                    k = biggerIndex;
                }
                else
                {
                    break;
                }
            }
        }
    }

    // exchange
    private static void swap(int[] data, int i, int j)
    {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}

(3) Exchange sort

(1) Bubble sort

1. Basic idea: In a group of numbers to be sorted, compare and adjust the two adjacent numbers from top to bottom, so that the larger ones sink and the smaller ones rise. That is, when two adjacent numbers are compared and their ranking requirements are opposite, they are exchanged.

2. Example

3. Implementation of java

package BubbleSort;

public class BubbleSort
{
    public static void main(String[] args)
    {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8 };
        System.out.println("Before sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
        // Bubble sort
        for (int i = 0; i < a.length; i++)
        {
            for (int j = 0; j < a.length - i - 1; j++)
            {
                // Here - i is mainly the largest number of i sinks to the bottom every time it traverses. There is no need to replace it.
                if (a[j] > a[j + 1])
                {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        System.out.println();
        System.out.println("After sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }

    }

}

(2) Quick Sorting

1. Basic idea: select a reference element, usually the first element or the last element, and divide the sequence to be arranged into two parts through a scan. One part is smaller than the reference element, and the other part is greater than or equal to the reference element. At this time, the reference element is in the correct position after it is arranged, and then recursively use the same method. Two parts of sorting.

2. Example

3. Implementation of java

package QuickSort;

public class QuickSort
{
    public static void main(String[] args)
    {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8 };
        System.out.println("Before sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
        // Quick sort
        quick(a);
        System.out.println();
        System.out.println("After sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
    }

    private static void quick(int[] a)
    {
        if (a.length > 0)
        {
            quickSort(a, 0, a.length - 1);
        }
    }

    private static void quickSort(int[] a, int low, int high)
    {
        if (low < high)
        { // If this judgment is not added, recursion will not be able to exit, resulting in stack overflow exception
            int middle = getMiddle(a, low, high);
            quickSort(a, 0, middle - 1);
            quickSort(a, middle + 1, high);
        }
    }

    private static int getMiddle(int[] a, int low, int high)
    {
        int temp = a[low];// Reference element
        while (low < high)
        {
            // Find element locations smaller than base elements
            while (low < high && a[high] >= temp)
            {
                high--;
            }
            a[low] = a[high];
            while (low < high && a[low] <= temp)
            {
                low++;
            }
            a[high] = a[low];
        }
        a[low] = temp;
        return low;
    }
}

(4) Merging and sorting

1. Basic idea: Merge sorting method is to merge two (or more) ordered tables into a new ordered table, that is, to divide the sequence to be sorted into several sub-sequences, each of which is ordered. Then the ordered subsequences are merged into the whole ordered sequence.

2. Example

3. Implementation of java

package MergeSort;

import java.util.Arrays;

public class MergeSort
{
    /**
     * Introduction to Merging and Sorting: Merging two (or more) ordered tables into a new ordered table
     * That is to say, the sequence to be sorted is divided into several sub-sequences, each of which is ordered. Then the ordered subsequences are merged into a global ordered sequence with time complexity O(nlogn) stable sorting method.
     * 
     * @param nums
     *            Array to be sorted
     * @return Output ordered array
     */
    public static int[] sort(int[] nums, int low, int high)
    {
        int mid = (low + high) / 2;
        if (low < high)
        {
            // left
            sort(nums, low, mid);
            // Right
            sort(nums, mid + 1, high);
            // Merge left and right
            merge(nums, low, mid, high);
        }
        return nums;
    }

    public static void merge(int[] nums, int low, int mid, int high)
    {
        int[] temp = new int[high - low + 1];
        int i = low;// Left pointer
        int j = mid + 1;// Right pointer
        int k = 0;

        // Move smaller numbers to new arrays first
        while (i <= mid && j <= high)
        {
            if (nums[i] < nums[j])
            {
                temp[k++] = nums[i++];
            }
            else
            {
                temp[k++] = nums[j++];
            }
        }

        // Move the remaining number on the left into the array
        while (i <= mid)
        {
            temp[k++] = nums[i++];
        }

        // Move the remaining number on the right into the array
        while (j <= high)
        {
            temp[k++] = nums[j++];
        }

        // Override nums arrays with new arrays
        for (int k2 = 0; k2 < temp.length; k2++)
        {
            nums[k2 + low] = temp[k2];
        }
    }

    // Realization of Merging and Sorting
    public static void main(String[] args)
    {

        int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };

        MergeSort.sort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}

 

Cardinal sorting

1. Basic idea: Unify all the numeric values (positive integers) to be compared into the same digit length, and make up zero before the shorter digits. Then, start with the lowest bit and sort it one by one. In this way, from the lowest bit sort to the highest bit sort, the sequence becomes an ordered sequence.

2. Example

3. Implementation of java

package BaseSort;

import java.util.*;

public class BaseSort
{

    public static void main(String[] args)
    {
        int[] a = { 49, 38, 65, 97, 176, 213, 227, 49, 78, 34, 12, 164, 11, 18, 1 };
        System.out.println("Before sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
        // Radix sorting
        sort(a);
        System.out.println();
        System.out.println("After sorting:");
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(a[i] + " ");
        }
    }

    private static void sort(int[] array)
    {
        // Find the maximum number and determine how many times to sort
        int max = 0;
        for (int i = 0; i < array.length; i++)
        {
            if (max < array[i])
            {
                max = array[i];
            }
        }
        // Judgement digit
        int times = 0;
        while (max > 0)
        {
            max = max / 10;
            times++;
        }
        // Establish ten queues
        List<ArrayList> queue = new ArrayList<ArrayList>();
        for (int i = 0; i < 10; i++)
        {
            ArrayList queue1 = new ArrayList();
            queue.add(queue1);
        }
        // Time sub-allocation and collection
        for (int i = 0; i < times; i++)
        {
            // distribution
            for (int j = 0; j < array.length; j++)
            {
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList queue2 = queue.get(x);
                queue2.add(array[j]);
                queue.set(x, queue2);
            }
            // collect
            int count = 0;
            for (int j = 0; j < 10; j++)
            {
                while (queue.get(j).size() > 0)
                {
                    ArrayList<Integer> queue3 = queue.get(j);
                    array[count] = queue3.get(0);
                    queue3.remove(0);
                    count++;
                }
            }
        }
    }

}

--------

Links to the original text: https://blog.csdn.net/gane_cheng/article/details/52652705