# wonder! The most beautiful sorting algorithm in the world!

58 Shen Jian 2021-10-14 04:57:54

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 .