“This is the 25th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Merge sort

Merge sort principle

So what is merge sort? Merge sort, the first thing to understand is merge: merge two ordered sequences into one ordered sequence, we call it “merge”.

Idea: Merge Sort is to Sort a sequence using Merge Sort. Depending on the implementation, merge sort can be either “top down” or “bottom up”. It’s also a very typical application of divide-and-conquer.

Algorithm implementation

Step 1: Divide the n elements into two subsequences containing N /2 elements (the left side may have one more number than the right side) Step 2: use MS to recursively sort the two subsequences until the number of elements in all parts is 1. (Finally, the whole original sequence can be decomposed into N sub-sequences.) Step 3: Merge the two ordered sequences Step by Step from the bottom layer.

2, graphic

3. Algorithm space complexity and time complexity

Time complexity:

  • Worst: o (nlog⁡2nn\log _{2}nnlog2n)
  • Best: o (nlog⁡2nn\log _{2}nnlog2n)
  • Average: o (nlog⁡2nn\log _{2}nnlog2n)

Space complexity (secondary storage) : O (n)

Stability: stability

sample

Use merge sort to print the following columns in descending order: 123,45,6,22,99,1,38,41,-6,0

Java code:


import java.util.Arrays;

public class Test {

    public static void mergeSort(int[] arr, int first, int last){
        if(null == arr || arr.length < 0 || first == last){
            return;
        }
        mergeSort(arr, first, (last + first)/2);
        mergeSort(arr, (last + first)/2 + 1, last);
        sort(arr, first, (last + first)/2, last);

    }

    // This method merges two ordered arrays as if inserting the sort algorithm directly
    public static void sort(int[] arr, int first, int mid, int last ){
        int[] temp = new int[last - first + 1];
        int i = 0; 
        int j = 0; 
        int index = 0;
        while(i < mid - first + 1 && j < last - mid){
            if(arr[first + i] >= arr[mid + 1 + j]){
                temp[index] = arr[mid + 1 + j];
                j++;
                index++;
            } else{ temp[index] = arr[first + i]; i++; index++; }}while(i < mid - first + 1){
            temp[index] = arr[first + i];
            index++;
            i++;
        }
        while(j < last - mid){
            temp[index] = arr[mid + 1 + j];
            index++;
            j++;
        }
        for(int k = first, n = 0; k <= last; k++, n++){ arr[k] = temp[n]; }}public static void main(String[] args) {
        int[] arr=new int[] {123.45.6.22.99.1.38.41, -6.0};
        // merge sort
        mergeSort(arr,0.9);

        System.out.println("Merge sort results in :"); System.out.println(Arrays.toString(arr)); }}Copy the code

Bucket sort

Bucket sorting principle

Bucket sort, known as box sort, is a sorting algorithm that works by sorting an array into a finite number of buckets. Bucket sort is a fast and easy method, bucket sort can be seen as an upgraded version of counting sort.

The data to be sorted into multiple ordered buckets, the data in each bucket is sorted separately, and then the data in each bucket is taken out in turn to complete sorting. Bucket sorting is a stable sorting algorithm if stable inner sorting is used and the relative order between elements is not changed when elements are inserted into the bucket.

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

Fastest: when the input data can be evenly distributed to each bucket.

Slowest: When the input data is allocated to the same bucket.

Algorithm implementation

1. Algorithm description

  1. Set a quantitative array as an empty bucket;
  2. Iterate through the sequence and place the elements one by one into the corresponding bucket;
  3. Sort each bucket that is not empty;
  4. Put elements back into the original sequence from a bucket that is never empty.

2, graphic

3. Algorithm space complexity and time complexity

Time complexity:

  • Worst: o (n2n^{2}n2)
  • Better: o (NNN) or O (n+kn+kn+k)
  • Average: O (NNN) or O (n+kn+kn+k)

Space complexity (auxiliary storage) : O (NNN) or O (n+ kN + KN + K)

The average time complexity of bucket sorting is O (n+n2/k+ kN +n^2/k+ KN +n2/k+ K) (divide range into n blocks on average + sort + remerge elements), and is O (NNN) when k is approximately equal to n.

Stability: stability

sample

Print the following numbers in ascending order using bucket sort:

66,13,51,76,81,26,57,69,23

Java code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Test {
    public static void bucketSort(int[] arr){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        / / barrels
        int bucketNum = (max - min) / arr.length + 1;
        List<List<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }

        // Put each element into the bucket
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        // Sort each bucket
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }

        // Combine elements from each non-empty bucket
        int k=0;
        for(int i=0; i<bucketNum; i++){if(bucketArr.get(i).size()! =0) {for(intn:bucketArr.get(i)){ arr[k]=n; k++; }}}}public static void main(String[] args) {
        int[] arr=new int[] {123.45.6.22.99.1.38.41, -6.0};
        / / bucket sorting
        bucketSort(arr);

        System.out.println("The result of bucket sorting is :"); System.out.println(Arrays.toString(arr)); }}Copy the code