[eight sorts ④] merge sort, sort not based on comparison (count sort, cardinal sort, bucket sort)

Catalog

One 、 Merge sort  

Two 、 Count sorting

3、 ... and 、 Radix sorting  

Four 、 Bucket sort

---

One 、 Merge sort  

  Merge sort （MERGE-SORT） It's based on Merge operation An effective sorting algorithm on , The algorithm adopts Divide and conquer method A very typical application . Merges ordered subsequences , You get a perfectly ordered sequence ; So let's make each subsequence in order , Then make the subsequence segments in order .

If two ordered tables are merged into one ordered table , It's called a two-way merge . The core steps of merging and sorting ：

• decompose
• Merge

 

  Code （ recursive ）

// Merge sort 
    public static void merge(int[] array,int low, int mid ,int high){
        int s1 = low;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = high;
        int[] tmpArr = new int[high-low+1];
        int k = 0;
        // Prove that both segments have data 
        while(s1 <= e1 && s2 <= e2){
            if(array[s1] < array[s2]){
                tmpArr[k++] = array[s1++];
            }else {
                tmpArr[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2){
            tmpArr[k++] = array[s2++];
        }

        for(int i = 0; i < k; i++){
            array[i+low] = tmpArr[i];
        }

    }
    public static void  mergeSortInternal(int[] array,int low, int high){
        if(low >= high) return;  // Recursion end condition 
        int mid = low + ((high-low) >>> 1) ;

        mergeSortInternal(array,low,mid);
        mergeSortInternal(array,mid+1,high);

        merge(array,low,mid,high);
    }
    public static void mergeSort(int[] array){
        mergeSortInternal(array,0,array.length-1);
    }

 

Code （ Non recursive ）

 public static void merge(int[] array,int low, int mid ,int high){
        int s1 = low;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = high;
        int[] tmpArr = new int[high-low+1];
        int k = 0;
        // Prove that both segments have data 
        while(s1 <= e1 && s2 <= e2){
            if(array[s1] < array[s2]){
                tmpArr[k++] = array[s1++];
            }else {
                tmpArr[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2){
            tmpArr[k++] = array[s2++];
        }

        for(int i = 0; i < k; i++){
            array[i+low] = tmpArr[i];
        }

    }
// Merge sort （ Non recursive ）
    public static void mergeSortNor(int[] array){
        int gap = 1;
        while(gap < array.length){
            for(int i = 0; i < array.length; i += 2*gap){
                int left = i;
                int mid = left+gap-1;
                // correct mid, To prevent cross-border 
                if(mid >= array.length){
                    mid = array.length-1;
                }
                int right = mid+gap;
                // correct right
                if(right >= array.length){
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
        }
    }

 

Merge sort summary

1. The disadvantage of merging is that it requires O(N) Spatial complexity of , The thinking of merge sort is more about solving the problem of external sort in disk .
2. Time complexity ：O(N*logN)
3. Spatial complexity ：O(N)
4. stability ： Stable

   

Two 、 Count sorting

thought ： Counting sorting is also called pigeon nest principle , It is a variant application of hash direct addressing method . Operation steps ：
1. Count the number of occurrences of the same element
2. According to the statistical results, the sequence is recycled into the original sequence

The steps of the algorithm are as follows ：

• （1） Find the largest and smallest elements in the array to be sorted
• （2） Each value in the statistics array is i The number of times an element of , Save to array C Of the i term
• （3） Add up all the counts （ from C The first element in begins , Add each item to the previous one ）
• （4） Reverse fill target array ： Put each element i Put it in the first... Of the new array C(i) term , Every time an element is placed, it will C(i) subtract 1

  Code

   public static void countSort(int[] array){
        //1. Get the maximum and minimum values 
        int maxVal = array[0];
        int minVal = array[0];
        for(int i = 1; i < array.length;i++){
            if(maxVal < array[i]){
                maxVal = array[i];
            }
            if(minVal > array[i]){
                minVal = array[i];
            }
        }
        //2. Start counting 
        int range = maxVal-minVal+1;
        int[] count = new int[range];
        for (int i = 0; i < array.length; i++) {
            count[array[i] - minVal]++;
        }
        //3. Traverse the array of this count , Put the data back array
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while(count[i]>0) {
                array[index++] = i + minVal;
                count[i]--;
            }
        }
    }

 【 Summary of the characteristics of count sorting 】
1. When the count sort is in the data range set , It's very efficient , However, the scope of application and scenarios are limited .
2. Time complexity ：O(MAX(N, Range ))
3. Spatial complexity ：O( Range )
4. stability ： Stable

   

3、 ... and 、 Radix sorting  

Radix sort is sorted in order of low order first , Then collect ; And then sort by the highest order , And then collect ; By analogy , Up to the highest bit . Sometimes some properties are prioritized , Let's start with low priority , And then sort by high priority . The last order is the one with the highest priority , High priority equals low priority equals high priority . 

Algorithm description

• Gets the largest number in the array , And get digit ;
• Press a bit first , Bits are 0 Put it in 0 The subscript place , Bits are 1 Put it in 1 The subscript place , Bits are n Put it in n The subscript place
• Then traverse the subscript , Take out each number one by one
• Press ten more , Ten are 0 Put it in 0 The subscript place , Ten are 1 Put it in 1 The subscript place , Ten are n Put it in n The subscript place
• Then traverse the subscript , Take out each number one by one
• Repeat the above steps , Until the highest order is finished

 

Four 、 Bucket sort

  thought ：

Divide multiple intervals with the same range , Each subinterval is self sorted , Final merger .

Figure source network