O (n) complexity hand tear sorting interview questions | an article will help you understand counting sorting

Count sorting And Radix sorting It is a special method of bucket sorting

It's really cold these two nights ...

that , What sort of sort is count sort ？

Counting sort is not a comparison sort algorithm , The algorithm is based on 1954 Year by year Harold H. Seward Put forward , The time complexity is reduced to O(N).

What are the steps of the counting sorting algorithm ？

• First step ： Find out the largest element in the original array , Write it down as max.
• The second step ： Create a new array count, Its length is max Add 1, The default values of its elements are 0.
• The third step ： Go through the elements in the original array , Take the elements in the original array as count Index of array , Take the number of elements in the original array as count The element value of the array .
• Step four ： Create an array of results result, Starting index index.
• Step five ： Traverse count Array , Find out that the element value is greater than 0 The elements of , Fill its corresponding index as the element value to result Go to... In the array , Every time I deal with ,count The value of this element in minus 1, Until the value of the element is not greater than 0, Sequential processing count The rest of the elements in .
• Step six ： Return result array result.

It's abstract , Is there an easy way to understand , For example, illustration ？

But it's a waste of space ！

Like a set of data {101,109,108,102,110,107,103}, The maximum value is 110, Follow the previous thinking , We need to create a length of 111 Count array of , But we can see , The one in front of it [0,100] That's a complete waste of space .

So how to optimize ？

Set the length of the array to max-min+1, That is to find out not only the maximum value , And find the minimum , Determine the length of the count array based on the difference between the two .

---

Let's make a joke and relax

---

Next, we will use the optimized idea to solve a common hand tearing sorting problem in the interview

Topic  

Submission

Count sort code （ optimization ）

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        int max = nums[0], min = nums[0];
        for(int i=1; i<n; i++) {
            if(nums[i] > max)  max = nums[i];
            if(nums[i] < min)  min = nums[i];
        }
        vector<int> count(max-min+1,0);
        for(int i=0; i<n; i++)
            count[nums[i]-min]++;
        int k=0;
        for(int i=0; i<max-min+1; i++) {
            while(count[i]--) {
                nums[k++] = i+min;
            }
        }
        return nums;
    }
};

---

Corresponding cardinality sorting code

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        int max = abs(nums[0]);
        for(int i=1; i<n; i++) 
            if(max<abs(nums[i]))
                max = abs(nums[i]);
        
        int w = 0;
        while(max>0) {
            max /= 10;
            w++;
        }

        int flag = 1;
        vector<int> ans(n);
        for(int i=0; i<w; i++) {
            vector<int> bucket(19,0);
            for(int j=0; j<n; j++) {
                int temp = nums[j]/flag%10+9;
                bucket[temp]++;
            }
            for(int j=1; j<19; j++)
                bucket[j] += bucket[j-1];
            for(int j=n-1; j>=0; j--) {
                int temp = nums[j]/flag%10+9;
                ans[--bucket[temp]] = nums[j];
            }
            nums.swap(ans);
            flag*=10;
        }
        return nums;
    }
};

Refer to the boss's A paper to understand the counting and sorting algorithm ！ - Programmer Ogawa - Blog Garden