Go straight to the theme , In the world “ Most beautiful ” Sort algorithm , Only 6 That's ok .

*void stooge_sort(int arr[], int i, int j){
*

* if (arr[i]>arr[j]) swap(arr[i], arr[j]);*

* if (i+1>=j) return;*

* int k=(j-i+1)/3;*

* stooge_sort(arr, i, j-k);*

* stooge_sort(arr, i+k, j);*

* stooge_sort(arr, i, j-k);*

*}*

《 Introduction to algorithms 》 In exercises “ Perfect sequencing ”, from Howard、Fine Wait for several professors to put forward , It's called “ Perfect sequencing ”, Because of its ** Code implementation **, grace 、 Neat 、 beautiful .

The code is not easy to understand , Explain your ideas step by step .

** First **, The parameter passed in by sorting is the array to be sorted arr[i, j];

** First step **： Compare i And j The element of location , Decide whether to replace according to the sorting rules .

* Voice over ： Chestnut , Suppose the collation is from small to large .*

After the replacement , Determine whether the sorting is over , When i and j Adjacent time , End of sort .

** The second step **： take arr[i, j] Three equal parts ;

* Voice over ： The total number of elements is j-i+1.*

** The third step **： recursive arr Before 2/3 Half area .

** Step four **： recursive arr After 2/3 Half area .

** Step five **： recursive arr Before 2/3 Half area .

End of sort .

** Magic is not magic ！！！**

Look again. , Impressive, No ？

*void stooge_sort(int arr[], int i, int j){
*

* if (arr[i]>arr[j]) swap(arr[i], arr[j]); // Compare *

* if (i+1>=j) return; // Is it over? *

* int k=(j-i+1)/3; // Three equal parts *

* stooge_sort(arr, i, j-k); // front 2/3 Half area *

* stooge_sort(arr, i+k, j); // after 2/3 Half area *

* stooge_sort(arr, i, j-k); // front 2/3 Half area *

*}*

But it is of no damn use , Except for the code , Perfect sorting is useless , Because it's a very slow algorithm .

It's easy to see from the code ：

（1） When only 1 Element time , The perfect sort of time is also 1;

（2） When there is n Element time , The perfect sort is calculated by a constant , Plus three recursions , The amount of data per recursion is (2/3)*n;

namely , Its time ** Complexity recursion ** by ：

T(1) = 1;

T(n) = 3T(2/3n) + 1;

Through recursive calculation method , The resulting , Perfectly sorted ** The time complexity is **O(n^2.7), Than O(n^2) The order of is slow .

Proof of perfect ordering , Don't expand in the article . From the code, you can feel , adopt swap And triple recursion , On trend , Small elements move forward , Large elements will move back , Until sorting is complete .

* Voice over ： The quick sort process is partition+ Two recursions , It's also a small element moving forward , Big elements go back , Until sorting is complete .*

I hope this minute , You have something to gain .

Architect's way - Share technical articles that can be implemented

Only 6 Perfect sorting of rows , Have you learned ？

* Voice over ： In the future, handwritten sorting of interview is no longer a problem .*