C ＃: quick sort. If there is the same number, it will be ignored, and then continue the previous search direction to find the next number that meets the requirements for replacement

summary

Number of pits to be filled + Divide and conquer method

Summarize the number of pit excavation and filling

1. i =L; j = R; The first pit will be excavated a[i], For example, the first benchmark number is 0 Indexed
2. j– Find a smaller number from back to front , After finding it, dig out this number and fill the previous pit a[i] in .
3. i++ Find a larger number from front to back , After finding it, dig out this number and fill it in the previous pit a[j] in .
4. And repeat 2,3 Two steps , until i==j, Fill the reference number in a[i] in , When meeting, update the left half index according to the benchmark , And right half index
5. quick_sort(s, l, i - 1);quick_sort(s, i + 1, r); Recursively call , Until every recursive l And r equal , End recursion

void quick_sort(int s[], int l, int r)
{
    
    if (l < r){
    
        int i = l, j = r, x = s[l];
        while (i < j){
    
            while(i < j && s[j] >= x) //  Find the first less than... From right to left x Number of numbers 
                --j; 
            if(i < j)
               s[i++] = s[j];           
            while(i < j && s[i] < x) //  Find the first greater than or equal to... From left to right x Number of numbers 
                ++i; 
            if(i < j)
               s[j--] = s[i];
        }
 
        s[i] = x;
        quick_sort(s, l, i - 1); //  Recursively call 
        quick_sort(s, i + 1, r);
 
    }
}

What is the process of quick sorting if there are the same numbers

The same number will be ignored , Then continue the previous search direction to find the next number that meets the requirements for replacement

test

int[] array = new int[8] { 5 ,2, 2, 1, 7 ,3, 4, 4 };

Time complexity

O (nlogn)

O(log n) analysis
Another example O(log n), When the data increases n Times , Time consuming log n times （ there log In order to 2 At the bottom of the , such as , When the data increases 256 Times , Time consuming only increases 8 times , It's a lower time complexity than linearity ）. A binary search is O(log n) The algorithm of , Every time you look for it, rule out half of the possibilities ,256 Just look for 8 You can find the target in three times .

Easy to understand examples

This is like having a hundred keys , You suddenly feel , Is it too slow for me to look from the beginning , I looked in the middle , For example, I want to find 23 Room key No , I cut it in the middle , find 50 The position of the number , then 23 stay 150 Inside , I'll cut it from the middle into 25, then 23 stay 125 Between , I'll cut it into 12.5, then 23 stay 12.5~25 Between , Look down in turn , Until you find the key . The complexity of this method of finding keys is O(log^n)

O(n log n) analysis
O(n log n) Empathy , Namely n multiply log n, When the data increases 256 Times , Time consuming 256*8=2048 times . This complexity is higher than linear, lower than square . Merge sort is O(n log n) Time complexity of .

Source code

https://github.com/luoyikun/UnityForTest
SortScene scene