preface

Algorithm is the soul of programming, not algorithm programmers only with code farming. Algorithm learning is also a stage, from entry to simple, and then to complex, and then to simple. The final simplicity is to be able to find the simplest answer to the problem exactly when you reach a certain height.

introduce

Algorithm inside the most commonly used is the most basic sorting algorithm and search algorithm, this paper mainly explains the algorithm inside the most classic ten sorting algorithm. Here we divide the top ten sorting algorithms into two categories according to their implementation principles and efficiency:

  1. Nonlinear comparison sorting: nonlinear means that the time complexity of the algorithm cannot break through (Nlogn), and the order of elements is determined by comparing their sizes.
  2. Linear non-comparative sort: The algorithm can break through the time complexity (nlogn) and sort elements without comparison.

The specific classification is illustrated in the figure above:

Algorithm to compare

The comparison of time complexity, space complexity and stability of the algorithm is given here, also in the form of pictures:

  • Stable: If a is ahead of B and a= B, a will still be ahead of B after sorting.

  • Unstable: If a is in front of B and a= B, a may appear behind B after sorting.

  • Time complexity: Total number of operations on sort data. Reflect the rule of operation times when n changes.

  • Spatial complexity: A measure of the storage space required for an algorithm to execute within a computer, and a function of data size N.

Below is a detailed explanation of one pair of ten algorithms, will give their basic idea, picture demonstration, and with detailed annotation of the source code. (All sorting algorithms in this article are in ascending order)

1 Bubble sort

1.1 Basic Ideas

Bubble sort is one of the simplest sorts, and the one most people think of most easily. That is, sorting n numbers, each time the previous number is compared to the next number, each cycle, you can move the largest number to the end of the array, a total of N-1 cycles, complete the array sorting.

1.2 Algorithm Steps

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

  2. 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.

  3. Repeat this step for all elements except the last one.

  4. Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.

1.3 Dynamic Demonstration

1.4 Algorithm Characteristics

When the input data is already in positive order, bubble sort is the fastest. Bubble sort is slowest when the input data is in reverse order.

1.5 Code Presentation

public static void bubbleSort(int[] arr) {
    if (arr == null)
        return;
    int len = arr.length;
    // I controls the number of loops. An array of length len only needs to loop len-1. The initial value of I is 0, so I 
    for (int i = 0; i < len - 1; i++) {
        // j controls the number of comparisons, the I loop needs to compare len-i times
        Arr [j] = arr[j] = arr[j+1]
        for (int j = 0; j < len - i - 1; j++) {
            // If the first number is larger than the next, switch places and put the larger number back.
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j + 1];
                arr[j + 1] = arr[j]; arr[j] = temp; }}}}Copy the code

2 Selection sort

2.1 Basic Ideas

Selection sort can be said to be an improved version of bubble sort. Instead of comparing the previous number with the next number, a number is compared with all numbers in each cycle. Each comparison selects the relatively smaller number for the next comparison, and constantly updates the subscript of the smaller number. So at the end of one loop we get the smallest index, we swap the smallest number first, and we sort through n-1 loops. Compared to bubble sort, the number of comparisons has not changed, but the number of data exchanges has been greatly reduced.

2.2 Algorithm Steps

  1. First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence

  2. Find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence.

  3. Repeat the second step until all elements are sorted.

2.3 Dynamic Demonstration

2.4 Algorithm Features

Selection sort is a simple and intuitive sorting algorithm, whatever data goes in is O(n²) time complexity. So when you use it, the smaller the data, the better. The only benefit might be that it doesn’t take up any extra memory.

2.5 Code Presentation

public static void selectSort(int[] arr) {
    if (arr == null)
        return;
    int len = arr.length;
    // I controls the number of loops. An array of length len only needs to loop len-1. The initial value of I is 0, so I 
    for (int i = 0; i < len - 1; i++) {
        // minIndex is used to store the lower index after each comparison.
        int minIndex = i;
        // j controls the number of comparisons, since the smallest number is placed first after each loop,
        // So the next loop can skip this number, so the initial value of j is I +1 instead of starting at 0 each time and j
        for (int j = i + 1; j < len; j++) {
            // Each comparison requires the subscript of the smaller number to be recorded
            if(arr[minIndex] > arr[j]) { minIndex = j; }}// When you complete a loop, you need to move the minimum number selected to the beginning of the loop.
        if(minIndex ! = i) {int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        // Prints the sorted state of the array at the end of each loop
        System.out.println("The first" + (i + 1) + "Effect after the second loop:"+ Arrays.toString(arr)); }}Copy the code

3 Insert sort

3.1 Basic Ideas

The idea of insertion sort is certainly easy for anyone who plays cards to understand, it’s just a fit. By default, the first number in the array is in the correct position, that is, sorted. Then take the next number and compare it with the sorted number in order from back to front. If the number is smaller than the sorted number in the current position, move the sorted number one bit back. Repeat the previous step until you find the right location. Once the position is found, the comparison loop is completed and the number is placed in the appropriate position.

3.2 Algorithm Steps

  1. Treat the first element of the first to be sorted sequence as an ordered sequence and the second element to the last element as an unsorted sequence.

  2. Scan the unordered sequence from beginning to end, inserting each scanned element into the appropriate place in the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)

3.3 Dynamic Demonstration

3.4 Code Presentation

public static void insertSort(int[] arr) {
    if (arr == null)
        return;
    int len = arr.length;
    // I controls the number of loops, since the first position is already assumed to be correct, so I starts at 1, I 
    for (int i = 1; i < len; i++) {
        int j = i;// the variable j is used to record the position of the number to be sorted, i.e. the original position of the target number
        int target = arr[j];//target is used to record the value of the number to be sorted
        // The while loop is used to find the right position for the target value in the sorted number,
        // J >0; // J >0; // J >0
        while (j > 0 && target < arr[j - 1]) {
            // When the value of the target number is smaller than the value of its current position, the position of the previous number is moved back one.
            // and j-- keeps the target number compared to the next element
            arr[j] = arr[j - 1];
            j--;
        }
        // Add the target number of positions.
        arr[j] = target;
        // Prints the sorted state of the array at the end of each loop
        System.out.println("The first" + (i) + "Effect after the second loop:"+ Arrays.toString(arr)); }}Copy the code

4 Hill sort

4.1 Basic Ideas

Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. But Hill sort is an unstable sort algorithm.

Hill sort is an improved method based on the following two properties of insertion sort:

  • Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort.

  • But insert sort is generally inefficient because it can only move data one bit at a time.

The basic idea of Hill sorting is that the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sorting respectively. When the records in the whole sequence are “basically ordered”, the whole records are directly inserted in sequence.

4.2 Algorithm Steps

  1. Select an incremental sequence T1, T2… , where Ti > tj, tk = 1;

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

  3. In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. 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.

4.3 Dynamic Demonstration

4.4 Code Display

public static void shellSort(int[] arr) {
    if (arr == null)
        return;
    int len = arr.length; // The length of the array
    int k = len / 2; // The initial increment is half the array length
    // The while loop controls the sequence of molecules divided by increments, reducing the increments by half each time
    // The minimum value of the increment is 1, which is the last direct insertion sort of the entire array
    while (k > 0) {
        Insert sort (); insert sort ();
        // Insert sort '1' into 'k'.
        for (int i = k; i < len; i++) {
            int j = i;
            int target = arr[i];
            while (j >= k && target < arr[j - k]) {
                arr[j] = arr[j - k];
                j -= k;
            }
            arr[j] = target;
        }
        // The result of different increments
        System.out.println("Increment to" + k + "After sorting:" + Arrays.toString(arr));
        k /= 2; }}Copy the code

5 merge sort

5.1 Basic Ideas

Summary is a recursive split from top to bottom, followed by a gradual merge from bottom to top.

  • Recursive splitting:

First, the array to be sorted is divided into the left and right sub-sequences, and then the left and right sub-sequences are divided into four sub-sequences, and so on until the minimum number of sub-sequence elements is two or one.

  • Progressive consolidation:

Sort the lowest leftmost subsequence, then sort the second subsequence from left to right, then merge and sort the two sorted subsequences, and then sort the third subsequence from left to right….. After the merge, the memory completes the sorting of the array (remember to merge from bottom to top, which can be understood as recursive hierarchy return)

5.2 Algorithm Steps

  1. Apply for a space equal to the sum of two sorted sequences, which is used to store the combined sequence;

  2. Set two Pointers, starting at the start of two sorted sequences;

  3. Compare the elements pointed to by the two Pointers, select the smaller element into the merge space, and move the pointer to the next position;

  4. Repeat step 3 until a pointer reaches the end of the sequence;

  5. Copies all remaining elements of the other sequence directly to the end of the merged sequence.

5.3 Dynamic Demonstration

5.4 Algorithm Features

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.

5.5 Code Display

/** * recursively split *@paramArr Array to split *@paramLeft Minimum subscript * of the array to be split@paramRight Maximum index of the array to be split */
public static void mergeSort(int[] arr, int left, int right) {
    int mid = (left + right) / 2;  // Middle subscript
    if (left < right) {
        mergeSort(arr, left, mid); // Recursively split the left
        mergeSort(arr, mid + 1, right); // Recursively split the right
        sort(arr, left, mid, right); // merge left and right}}/** * merges two ordered subsequences *@paramArr Array to merge *@paramLeft Minimum subscript * of the array to be merged@paramMid Middle subscript * of the array to be merged@paramRight The maximum index of the array to be merged is */
public static void sort(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1]; // A temporary array to store the result after each merge year
    int i = left;
    int j = mid + 1;
    int k = 0; // The initial index of the temporary array
    // This while loop can initially filter out the smaller fractions of the two subsequences to be merged
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else{ temp[k++] = arr[j++]; }}// Put the remaining numbers in the left sequence into a temporary array
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    // Put the rest of the right sequence into a temporary array
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    // Map the positions of the elements in the temporary array to the real array
    for (int m = 0; m < temp.length; m++) { arr[m + left] = temp[m]; }}Copy the code

6 QuickSort

6.1 Basic Ideas

Quicksort uses a Divide and conquer strategy to Divide one serial (list) into two sub-lists. Quicksort is a typical application of divide-and-conquer in sorting algorithm. Quicksort is essentially a recursive divide-and-conquer method based on bubble sort.

6.2 Algorithm Steps

Quicksort also adopts a divide-and-conquer strategy, where the concept of ‘base number’ is introduced.

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

  2. Reorder the array 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 exits, the benchmark is in the middle of the array. This is called a partition operation;

  3. Recursively sorts subsequences of elements less than a reference and subsequences of elements greater than a reference.

6.3 Algorithm Features

In the average case, quicksort requires comparison of TWO previous two (nLOGn) items, and in the worst case, requires comparison of two previous two (n2) items, but this situation is not common. In fact, quicksort is generally significantly faster than any other two (NLOGN) algorithms because its inner loop can be implemented efficiently on most architectures.

The worst case for quicksort is O(n ^ 2), for example, quicksort. But its amortized expected time is O(nlogn), and the constant factor implied in O(nlogn) notation is very small, much smaller than the stable complexity is O(nlogn) merge sort. Therefore, for most random sequences with weak order, quicksort is always better than merge sort.

6.4 Dynamic Demonstration

6.5 Code Presentation

/** * Partition process *@paramArr Array to be partitioned *@paramLeft Minimum subscript * of the array to be partitioned@paramRight The maximum index of the array to be partitioned is */
public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int temp = qSort(arr, left, right);
        quickSort(arr, left, temp - 1);
        quickSort(arr, temp + 1, right); }}/** * the sorting process *@paramArr Array to be sorted *@paramLeft Minimum subscript * of the array to be sorted@paramRight Maximum index of the array to be sorted *@returnAfter the order of the base number of position subscript, convenient next partition */
public static int qSort(int[] arr, int left, int right) {
    int temp = arr[left]; // Define the base number, which defaults to the first element of the array
    while (left < right) { // Conditions for loop execution
        // Since the default base number is on the far left, the criteria for entering the while loop are first compared from the right
        // If the current arR [right] is greater than the base number, move the right pointer to the left one bit, and ensure that left
        while (left < right && arr[right] > temp) {
            right--;
        }
        // the current arr[right] is smaller than the base number, so the current arr is moved to the base number and the left pointer is moved to the right (left++).
        // The current arr[right] position is empty, need to find a number from the left more than the base number to fill.
        if (left < right) {
            arr[left++] = arr[right];
        }
        // The next step is to find the number greater than the base number on the left to fill in the right position.
        If arr[left] is less than or equal to the base number, move the left pointer one bit to the right
        while (left < right && arr[left] <= temp) {
            left++;
        }
        // The current arR [left] value is greater than the base number, and the value needs to be filled to the right of the empty position, and then the current position is empty.
        if(left < right) { arr[right--] = arr[left]; }}// When the loop ends, the left and right Pointers have already met. And the place where they meet is an empty place,
    // At this point, fill the base number into the position and return the subscript of the position to prepare for the partition.
    arr[left] = temp;
    return left;
}
Copy the code

7 heap sort

7.1 Basic Ideas

Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node. Heap sort can be said to be a selection sort that uses the concept of heap to sort. There are two methods:

  • Big top heap: Each node has a value greater than its left and right children, using the big top heap in ascending order.

  • Small top heap: Each node whose value is less than the value of its left and right children in descending order uses the small top heap.

7.2 Algorithm Procedure

  1. Create a heap H[0…… n-1];

  2. Swap the heap head (maximum) with the heap tail;

  3. Reduce the size of the heap by 1 and call shift_down(0) to move the top of the new array into position.

  4. Repeat step 2 until the heap size is 1.

7.3 Dynamic Demonstration

7.4 Code Display

public static void heapSort(int[] arr) {
    if (arr == null) {
        return;
    }
    int len = arr.length;
    // Initialize the big top heap (starting from the last non-leaf node, left to right, bottom to top)
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    // Switch the top node and the last node, and adjust the rest of the heap
    for (int j = len - 1; j > 0; j--) {
        swap(arr, 0, j);
        adjustHeap(arr, 0, j); }}/** * Rearrange the tree into a heap *@paramArr Array to collate *@paramI starts at node *@paramJ array length */
public static void adjustHeap(int[] arr, int i, int j) {
    int temp = arr[i];// Define a variable to hold the starting node
    // k is the left subscript of this node
    for (int k = 2 * i + 1; k < j; k = 2 * k + 1) {
        // Compare the size of the left and right children, k always records the subscript of the larger of the two
        if (k + 1 < j && arr[k] < arr[k + 1]) {
            k++;
        }
        // The larger value of the child node is compared with the current node, and the larger value of the comparison result is placed at the current node
        if (arr[k] > temp) {
            arr[i] = arr[k];
            i = k;
        } else { // Indicates that the heap is already large
            break;
        }
    }
    arr[i] = temp;
}

/** * exchange data *@param arr
 * @param num1
 * @param num2
 */
public static void swap(int[] arr, int num1, int num2) {
    int temp = arr[num1];
    arr[num1] = arr[num2];
    arr[num2] = temp;
}
Copy the code

8 Counting sort

8.1 Basic Ideas

Counting sort takes a new approach. Instead of sorting by comparison, it takes the maximum value in the array to be sorted +1 as the length of a temporary array, and then uses the temporary array to record the number of occurrences of each element in the array to be sorted. Finally, the temporary array is traversed again, because it is in ascending order, so the front to back traversal, the value of the temporary array >0 of the number of the subscript cycle out, one by one into the array to be sorted, you can complete the sorting. Counting sort is efficient, but at the expense of memory, and with a constraint that the array to be sorted must be limited to a certain range.

8.2 Dynamic Demonstration

8.3 Code Presentation

public static void countSort(int[] arr) {
    if (arr == null)
        return;
    int len = arr.length;
    // Save the maximum value in the array to be sorted, in order to determine the length of the temporary array (must)
    int maxNum = arr[0];
    // Save the minimum value in the array to be sorted, in order to determine the initial value of the index of the final traversal of the temporary array (not necessary, just to speed up the loop)
    int minNum = arr[0];
    // The for loop is to find the maximum and minimum value of the array to be sorted
    for (int i = 1; i < len; i++) {
        maxNum = maxNum > arr[i] ? maxNum : arr[i];
        minNum = minNum < arr[i] ? minNum : arr[i];
    }
    // Create a temporary array
    int[] temp = new int[maxNum + 1];
    // The for loop records the number of occurrences of each element in the array to be sorted and stores that number in the temporary array
    for (int i = 0; i < len; i++) {
        temp[arr[i]]++;
    }
    // k=0 records the index of the array to be sorted
    int k = 0;
    // Iterate over the temporary array and re-assign to the array to be sorted.
    for (int i = minNum; i < temp.length; i++) {
        while (temp[i] > 0) { arr[k++] = i; temp[i]--; }}}Copy the code

9 bucket sort

9.1 Basic Ideas

Bucket sort is an updated version of counting sort. It makes use of the mapping relation of functions, and the key of efficiency lies in the determination of the mapping function. To make bucket sorting efficient, we need to do two things:

  • Increase the number of barrels as much as extra space is available

  • The mapping function used can evenly distribute the N input data into K buckets

9.2 Picture Demonstration

9.3 Algorithm Features

Bucket sorting makes use of the mapping relation of function, and the key of efficiency lies in the determination of the mapping function. To make bucket sorting efficient, we need to do two things:

  1. Increase the number of barrels as much as extra space is available

  2. The mapping function used can evenly distribute the N input data into K buckets

Buckets are sorted fastest when input data is evenly distributed to each bucket, and slowest when input data is distributed to the same bucket.

9.4 Code Presentation

public static void bucketSort(int[] arr) {
    if (arr == null)
        return;
    int len = arr.length;
    // define the number of buckets, k depends, we assume that the number of buckets in the sorted array is between 0,100.
    int k = 10;
    // Use nested sets to simulate buckets. The outer set represents buckets, and the inner set represents elements inside buckets.
    List<List<Integer>> bucket = new ArrayList<>();
    // The for loop initializes the outer collection to initialize the bucket
    for (int i = 0; i < k; i++) {
        bucket.add(new ArrayList<>());
    }
    // The loop is used to put the elements of the sorted array into different buckets through the mapping function
    for (int i = 0; i < len; i++) {
        bucket.get(mapping(arr[i])).add(arr[i]);
    }
    // This loop sorts all buckets with more than 1 elements.
    for (int i = 0; i < k; i++) {
        if (bucket.size() > 1) {
            // Because this is the bucket with the collection to simulate so use Java to write the collection sort method.
            // You should write a method to sort.Collections.sort(bucket.get(i)); }}// Put the sorted numbers back into the array to be sorted
    int m = 0;
    for (List<Integer> list : bucket) {
        if (list.size() > 0) {
            for(Integer a : list) { arr[m++] = a; }}}}/** * mapping function *@param num
 * @return* /
public static int mapping(int num) {
    return num / 10;
}
Copy the code

10 Radix Sort

10.1 Basic Ideas

Radix sort is a kind of non-comparative integer sort 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.

10.2 Dynamic Demonstration

10.3 Code Display

public static void main(String[] args) {
    int[] arr = {720.6.57.88.60.42.83.73.48.85};
    redixSort(arr, 10.3);
    System.out.println(Arrays.toString(arr));
}

public static void redixSort(int[] arr, int radix, int d) {
    // Cache the array
    int[] tmp = new int[arr.length];
    // Buckets records information about elements to be sorted
    // Buckets defines Max -min buckets
    int[] buckets = new int[radix];

    for (int i = 0, rate = 1; i < d; i++) {

        // Reset the count array to start counting the next keyword
        Arrays.fill(buckets, 0);
        // Copy the elements in data completely into the TMP array
        System.arraycopy(arr, 0, tmp, 0, arr.length);

        // Calculates the subkey of each data to be sorted
        for (int j = 0; j < arr.length; j++) {
            int subKey = (tmp[j] / rate) % radix;
            buckets[subKey]++;
        }

        for (int j = 1; j < radix; j++) {
            buckets[j] = buckets[j] + buckets[j - 1];
        }

        // Sorts the specified data by subkey
        for (int m = arr.length - 1; m >= 0; m--) {
            intsubKey = (tmp[m] / rate) % radix; arr[--buckets[subKey]] = tmp[m]; } rate *= radix; }}Copy the code

The resources

  1. www.cnblogs.com/onepixel/ar…
  2. Blog.csdn.net/apei830/art…

This account will continue to share learning materials and articles on back-end technologies, including virtual machine basics, multithreaded programming, high-performance frameworks, asynchronous, caching and messaging middleware, distributed and microservices, architecture learning and progression.