Java implements ten classic sorting algorithms (with dynamic renderings)

Java implements ten classic sorting algorithms (with dynamic renderings)

Preface

Sorting algorithms are a commonplace talk, but they will also be asked in interviews. For example, sometimes when investigating algorithm capabilities, if you are not allowed to write algorithms, let you describe the idea and time complexity of a sorting algorithm Or space complexity. I have encountered it and asked the quick sorting directly, so this time I will summarize and sort out the top ten classic sorting algorithms and their template codes.

Analysis of Algorithms

The quality of a sorting algorithm is generally analyzed through the following key information. The key information is introduced below, and then these key information of common sorting algorithms are counted.

Noun introduction

  • Time complexity : refers to the number of data operations (or simply understood as the number of executions of a certain piece of code). For example: O(1): constant time complexity; O(log n): logarithmic time complexity; O(n): linear time complexity.
  • Space complexity : The amount of memory that needs to be opened up each time a certain piece of code is executed.
  • Internal sorting : does not rely on external space, and sorts directly inside the data;
  • External sorting : The sorting of data cannot be done through the internal space and needs to rely on the external space.
  • Stable sorting : If two elements are equal: a=b, a is ranked before b before sorting, and a is still behind b after sorting, which is called stable sorting.
  • Unstable sorting : If two elements are equal: a=b, a is ranked before b before sorting, and a may appear after b after sorting, which is called unstable sorting.

The key information of common sorting algorithms is as follows:

Bubble Sort

Bubble sort is a simple and intuitive sorting algorithm, it needs to traverse the data multiple times; there are mainly these steps:

  • Compare two adjacent elements. If the previous element is larger than the next element, then swap the positions of the two elements. After such a traversal, the last element is the largest element;
  • Then, repeat the steps of comparing two adjacent elements above with the remaining elements except for the last element.
  • Repeat the above steps for fewer and fewer elements each time, until there is only one number left to compare.

In this way, the orderliness of the overall data is finally achieved.

Animation demo

Code template

/**
 *  
 * @param array
 */
public static void bubbleSort(int[] array){
    if(array.length == 0){
        return;
    }
    for(int i=0;i<array.length;i++){
        // i 
        for(int j=0;j<array.length-1-i;j++){
            // 
            if(array[j]>array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}
 

Bubble sort summary

When the elements in the array are already in positive order, the execution efficiency is the highest. When the elements in the array are in a reverse order, the execution efficiency is the lowest, and adjacent elements need to be exchanged each time they are compared. Moreover, bubble sorting is performed entirely within the data and does not require additional space, so the space complexity is O(1).

Select sort

Selective sorting is a simple and rude sorting method. Each time the largest or smallest element is selected from the data, and the final selection is completed, then the selected data is sorted.

The main steps:

  • First select the smallest element from all the data and place it in the position of the first element (select the smallest element and swap the position of the first position);
  • Then select the smallest element from the remaining elements except the first element and place it in the second position of the array.
  • Repeat the above steps in a loop, and finally the selected data is put in the front, and the data is sorted.

Animation demo

Code template

public static void selectSort(int[] array){

    for(int i=0;i<array.length;i++){
        // i 
        int min = i;
        // array[min]  min 
        for(int j=i+1;j<array.length;j++){
            if(array[j]<array[min]){
                min = j;
            }
        }
        // i i 
        if(min != i){
            int temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }
}
 

Selection sort summary

All data is sorted by selection, and the time complexity is O(n^2); therefore, the smaller the amount of data that needs to be sorted, the higher the efficiency of selection and sorting.

Insertion sort

Insertion sorting is also an intuitive and easy-to-understand sorting algorithm. By constructing an ordered sequence, the unsorted data is inserted into the sorted sequence, and finally all unsorted are inserted into the sorted sequence to achieve the sorting effect.

The main steps:

  • The first element of the original data is regarded as a sorted sequence, and the following elements except the first element are regarded as an unsorted sequence.
  • Scan from front to back from the following unsorted elements, take out the elements one by one, scan from back to front in the sorted sequence, and insert the elements taken from the unsorted sequence into the specified position of the sorted sequence.
  • When the number of unsorted elements is 0, the sorting is complete.

Animation demo

Code template

public static void insertSort(int[] array){
     // i1 
     for(int i=1;i<array.length;i++){

         int sortItem = array[i];
         int j = i;
         // 
         while (j>0 && sortItem < array[j-1]){
             array[j] = array[j-1];
             j--;
         }
         // 
         if(j !=i){
             array[j] = sortItem;
         }
     }
 }
 

Insertion sort summary

Insertion sort is also internal sorting, so the space complexity is O(1), but the time complexity is O(n^2), because basically each element has to be processed multiple times, and the sorted elements need to be moved repeatedly. Then insert the data into the specified location.

Hill sort

Hill sort is an upgraded version of insertion sort. It mainly divides the original data into several sub-sequences, and then inserts each sub-sequence into insertion sort, and then the number of sub-sequences is successively reduced each time until the length of the sub-sequence to be split Equal to the original data length. Then insert and sort the data as a whole.

Main steps: Select an incremental sequence t1, t2, , tk, where ti> tj, tk = 1; According to the number of incremental sequences k, the sequence is sorted by k times; each pass is sorted according to the corresponding increment ti, divide the sequence to be sorted into several sub-sequences of length m, and perform direct insertion sort on each sub-table respectively. When only the increment factor is 1, the entire sequence is treated as a table, and the length of the table is the length of the entire sequence.

Process demonstration

Raw unsorted data. After initial incremental gap=array.length/2=5grouping, the original data is divided into 5 groups, [12,1], [29,30], [5,45], [16,26], [15,32]. After grouping the data, each group of data is directly inserted and sorted, so that the data is slowly ordered, and then the increment is reduced gap=5/2=2, and the data is divided into 2 groups: [1,5,15,30,26] , [29,16,12,45,32]. Perform insertion sort on the two groups that have been divided above, and the entire data tends to be more ordered, and then reduce the increment gap=2/2=1, the entire data becomes one group, the entire sequence is processed as a table, and then an insertion sort is performed. Eventually reached order.

Code template

/**
 *  
 * @param array
 */
public static void shellSort(int[] array){
    int len = array.length;
    int temp, gap = len/2;
    while (gap > 0) {
        for (int i = gap; i < len; i++) {
            temp = array[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && array[preIndex] > temp) {
                array[preIndex + gap] = array[preIndex];
                preIndex -= gap;
            }
            array[preIndex + gap] = temp;
        }
        gap/= 2;
    }
}
 

Merge sort

Merge sort is a divide-and-conquer recursive method to complete data sorting, which is mainly to merge two subsequences in an existing order into a new ordered subsequence. 1. the subsequences are segmented and ordered, and then the segmented subsequences are merged into one, and finally the data sorting is completed.

The main steps:

  • Divide the length of the data into two from the middle, divide it into two subsequences, and perform recursive operations until there are two elements left in each subsequence.
  • Then the subsequences are merged and sorted separately.
  • The sorted subsequences are merged two by two, and finally merged into a complete sorting sequence.

Animation demo

Code template

/**
     *  
     * @param array      
     * @param left      0
     * @param right     array.length-1
     */
    public static void mergeSort(int[] array,int left,int right){
        
        if (right <= left){
            return;
        }
        // 
        int mid = (left + right)/2;
        // 
        mergeSort(array, left, mid);
        // 
        mergeSort(array, mid + 1, right);
        // 
        merge(array, left, mid, right);
    }

    /**
     *  
     * @param array
     * @param left
     * @param middle
     * @param right
     */
    public static void merge(int[] array,int left,int middle,int right){
     // 
     int[] temp = new int[right - left + 1]; 
     int i = left, j = middle + 1, k = 0;
     while (i <= middle && j <= right) {
         // 
         if(array[i] <= array[j]){
             temp[k++] = array[i++];
         }else {
             // 
             temp[k++] = array[j++];
         }
     }
     // 
     while (i <= middle){
         temp[k++] = array[i++];
     }
     // 
     while (j <= right){
         temp[k++] = array[j++];
     }
     // 
     for (int p = 0; p < temp.length; p++) {
         array[left + p] = temp[p];
     }
 }
 

Merge sort summary

The efficiency of merge sort is very high, the time complexity can be reached O(nlogn), but it relies on additional memory space, and this divide-and-conquer idea is worth learning, many scenes are composed of complex logic through simple functions, so as long as you find a splittable The smallest unit of, you can divide and conquer.

Quick sort

Quick sorting is very similar to the idea of binary search, in which the data is first divided into two and then processed one by one. Quick sort is also one of the most common sorting algorithms, and the probability of being asked in an interview is still relatively large.

The main steps:

  • An element is selected from the data, called a "benchmark" (pivot), and generally the first element or the last element is selected.
  • Then, in the data, all elements smaller than the reference element are placed on the left side of the reference element, and all elements larger than the reference element are placed on the right side of the reference element.
  • Then repeat the previous two steps with the data set in front of the reference element and the data set at the back.

Animation demo

Code template

/**
 *  
 * @param array  
 * @param begin 0
 * @param end   array.length-1
 */
public static void quickSort(int[] array, int begin, int end) {
    if (end <= begin) return;
    int pivot = partition(array, begin, end);
    quickSort(array, begin, pivot - 1);
    quickSort(array, pivot + 1, end);
}

/**
 *  
 * @param array
 * @param begin
 * @param end
 * @return
 */
public static int partition(int[] array, int begin, int end) {
    //pivot:  counter:  pivot 
    int pivot = end, counter = begin;
    for (int i = begin; i < end; i++) {
        if (array[i] < array[pivot]) {
           // counter 
            int temp = array[counter];
            array[counter] = array[i];
            array[i] = temp;
            counter++;
        }
    }
    // 
    int temp = array[pivot];
    array[pivot] = array[counter];
    array[counter] = temp;
    return counter;
}
 

Quick sort summary

The template code for quick sorting I found is quite clever. I chose the last element as the base element, and then the number of base elements is smaller than the number of base elements, which is where the base element should be. This seems a bit difficult to understand, but after you understand it, you will find that this template is quite interesting.

Heap sort

Heap sorting is actually done by using the data structure of the heap. Generally, the way of heap sorting is to complete the sorting in a way that approximates a complete binary tree to achieve the heap, but the implementation of the heap is actually not limited to the way of using a binary tree. , In fact, there are Fibonacci piles. According to the sorting direction, it is divided into big top pile and small top pile:

  • Big top heap: The value of each node is greater than or equal to the value of the child node, which is used for ascending sorting in heap sorting.
  • Small top heap: The value of each node is less than or equal to the value of the child node, and is used for descending sorting in heap sorting.

Like in Java, it PriorityQueueis a small top heap.

The main steps:

  1. Create a binary heap, the parameter is the unordered sequence [0~n];
  2. Swap top element and end element;
  3. The adjusted top element of the heap may not be the maximum or minimum value, so you need to adjust the top element to the correct position at this time. The process of adjusting the position is mainly to find the correct value after comparing with the value of the child element of the binary tree. position.
  4. Repeat steps 2 and 3 until the elements of the entire sequence are in the correct position in the binary pile.

Animation demo

Template code

/**
 *  
 * @param array
 */
public static int[] heapSort(int[] array){
    int size = array.length;
    // 
    for (int i = (int) Math.floor(size/2); i >= 0; i--) {
        heapTopMove(array, i, size);
    }
    // 
    for(int i = size - 1; i > 0; i--) {
        swapNum(array, 0, i);
        size--;
        heapTopMove(array, 0,size);
    }
    return array;
}

/**
 *  
 * @param array
 * @param i
 * @param size
 */
public static void heapTopMove(int[] array,int i,int size){

    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;

    if (left < size && array[left] > array[largest]) {
        largest = left;
    }

    if (right < size && array[right] > array[largest]) {
        largest = right;
    }

    if (largest != i) {
        swapNum(array, i, largest);
        heapTopMove(array, largest, size);
    }
}

/**
 *  
 * @param array
 * @param left
 * @param right
 */
public static void swapNum(int[] array,int left,int right){
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}
 

Heap sort summary

The time complexity of heap sorting is also O(nlogn), this is also a certain probability to be investigated in the interview. In fact, if you really encounter it in the interview, you can implement it without maintaining a heap by yourself, but using Java PriorityQueueto implement it. , You can put the unordered data set into PriorityQueueit, and then take out the top data in turn. When taking out the top data, remove the element from the pile, so that every time you take out the smallest data in the existing data Element too.

Count sort

Counting sorting is a sorting algorithm with linear time complexity. Its main logic is to convert data into keys and store them in an additional array space. Count sorting has certain limitations. It requires the input data to be a sequence of integers with a certain range.

The main steps:

  • Find the largest and smallest elements in the array to be sorted;
  • Count the number of occurrences of each element with value i in the array and store it in the ith item of array C;
  • Accumulate all counts (starting from the first element in C, each item is added to the previous item);
  • Backfill the target array: Put each element i in the C(i) item of the new array, and subtract 1 from C(i) for each element.

Animation demo

Code template

/**
 *  
 * @param array
 */
public static void countSort(int[] array){
    int bucketLen = getMaxValue(array) + 1;
    int[] bucket = new int[bucketLen];
    // 
    for (int value : array) {
        bucket[value]++;
    }
    // 
    int sortedIndex = 0;
    for (int j = 0; j < bucketLen; j++) {
        while (bucket[j] > 0) {
            array[sortedIndex++] = j;
            bucket[j]--;
        }
    }
}

/**
 *  
 * @param arr
 * @return
 */
private static int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    return maxValue;
}
 

Bucket sort

Bucket sorting is an enhanced version of counting sorting . It uses the mapping relationship of a specific function to put data belonging to a certain range into a bucket, then sort the data in each bucket, and finally sort the sorted data Spliced together. The main steps:

  • Set an array of appropriate length as an empty bucket;
  • Traverse the data, put the data in the specified bucket, the more evenly distributed the better;
  • Sort the data in each non-empty bucket;
  • Splice the sorted data in each bucket together.

Animation demo

Code template


 /**
  *  
  * @param arr
  * @param bucketSize
  * @return
  */
 private static int[] bucketSort(int[] arr, int bucketSize){
     if (arr.length == 0) {
         return arr;
     }
     int minValue = arr[0];
     int maxValue = arr[0];
     // 
     for (int value : arr) {
         if (value < minValue) {
             minValue = value;
         } else if (value > maxValue) {
             maxValue = value;
         }
     }
     // 
     int bucketCount = (int) Math.floor((maxValue - minValue)/bucketSize) + 1;
     int[][] buckets = new int[bucketCount][0];

     // 
     for (int i = 0; i < arr.length; i++) {
         int index = (int) Math.floor((arr[i] - minValue)/bucketSize);
         // 
         buckets[index] = appendBucket(buckets[index], arr[i]);
     }
     int arrIndex = 0;
     for (int[] bucket : buckets) {
         if (bucket.length <= 0) {
             continue;
         }
         // 
         InsertSort.insertSort(bucket);
         for (int value : bucket) {
             arr[arrIndex++] = value;
         }
     }
     return arr;
 }

 /**
  *  
  *
  * @param array
  * @param value
  */
 private static int[] appendBucket(int[] array, int value) {
     array = Arrays.copyOf(array, array.length + 1);
     array[array.length - 1] = value;

     return array;
 }
 

Base sort

Cardinality sorting is a non-comparative sorting. The main logic is to split the integers into different numbers according to the digits, and then sort them according to the digits, first sort by the low order, collect, then sort by the high order, and then collect until the highest Bit. The main steps:

  • Get the maximum value and the highest bit in the original data;
  • In the original array, take each bit from the lowest bit to form the base array;
  • On the bases of an array for counting sequencing (using a count number of characteristics suitable for sorting small range);

Animation demo

Code template

/**
 *  
 * @param array
 */
public static void radixSort(int[] array){
    // 
    int maxDigit = getMaxDigit(array);
    int mod = 10;
    int dev = 1;

    for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        //  [0-9] [10-19]  (bucket + 10)
        int[][] counter = new int[mod * 2][0];
        // 
        for (int j = 0; j < array.length; j++) {
            int bucket = ((array[j] % mod)/dev) + mod;
            counter[bucket] = appendBucket(counter[bucket], array[j]);
        }
        // 
        int pos = 0;
        for (int[] bucket : counter) {
            for (int value : bucket) {
                array[pos++] = value;
            }
        }
    }
}

/**
 *  
 */
private static int getMaxDigit(int[] arr) {
    int maxValue = getMaxValue(arr);
    return getNumLength(maxValue);
}

/**
 *  
 * @param arr
 * @return
 */
private static int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    return maxValue;
}

/**
 *  
 * @param num
 * @return
 */
protected static int getNumLength(long num) {
    if (num == 0) {
        return 1;
    }
    int lenght = 0;
    for (long temp = num; temp != 0; temp/= 10) {
        lenght++;
    }
    return lenght;
}

/**
 *  
 *
 * @param array
 * @param value
 */
private static int[] appendBucket(int[] array, int value) {
    array = Arrays.copyOf(array, array.length + 1);
    array[array.length - 1] = value;
    return array;
}
 

Cardinal sort summary

The three sorting algorithms of counting sorting, bucket sorting, and radix sorting all use the concept of buckets, but there are obvious differences in the use of buckets:

  • Cardinality sort: allocate buckets according to each digit of the key value;
  • Counting sort: each bucket only stores a single key value;
  • Bucket sorting: each bucket stores a certain range of values;

summary

This time I summarized 10 classic sorting algorithms, which can be regarded as a patch for the lazy I stole in the early years. Some commonly used algorithms can also be considered as an investigation direction in interviews, but the general inspections are those with low time complexity, that is, time complexity O(nlogn): quick sort, heap sort, and hill sort . So you need to be proficient in these few, at least you need to know how to implement the logic (after all, when the interview also has an oral algorithm).

Drawing: AlgorithmMan

WeChat public account: Jimoer is
concerned about sharing technologies. For questions or suggestions, please leave a message on the official account;