What exactly is a good sort
Maybe one person thinks it’s a pile, and another thinks it’s a fast pile, because their average time is O(nlogn), but they’re all different. The heap is basically stable at O(nlogn), and the worst case of fast sorting will be O(n squared), under the case of large data volume, fast sorting will be slightly better, in fact, the two combined together, you can achieve a possibly better sorting algorithm. The idea is to create a counting variable in quicksort to record the number of recursions, and then convert to the heap when the number of recursions reaches a critical value. So you can see that no single sorting algorithm is going to be great, but combined, it’s going to be great
What I think is the best order
Insert sort + quick sort + heap row, of course, is the biggest of the skeleton, then step by step he becomes 🐂
How does a simple quickrow become unsimple
Basic principles everywhere else, I show code directly
function quick_sort_v1(arr, l, r)
{
if (r-l<=0) {
return;
}
let x = l;let y = r; let base = arr[l];
//x is a header pointer, y is a tail pointer
while (x < y) {
// the tail pointer looks forward
while (x < y && arr[y] >= base) --y;
if (x < y) arr[x++] = arr[y];
// the head pointer looks back
while (x < y && arr[x] <= base) ++x;
if (x < y) arr[y--] = arr[x];
}
// The first and last Pointers overlap
arr[x] = base;
quick_sort_v1(arr, l, x - 1);
quick_sort_v1(arr, x + 1, r);
return ;
}
Copy the codeAll right, now the thing to do is to make this simple quick row not simple. So what are the optimization methods?
- Unilateral recursion (saves space complexity)
- Unsupervised partition
- Base value of three points in the middle (random)
Unilateral recursive
The code above will have two lines of recursive statements, quick to the left and quick to the right. What’s wrong with this? In fact, the speed is basically the same as not using unilateral recursion, but it will consume a lot of space. Unilateral recursion is essentially, you’re doing it in a loop, and you’re doing it recursively, and you’re saving a lot of space. Unilateral recursion sounds good, but it’s almost unheard of because it’s so poorly readable.
Unsupervised partition
Partition believes that everyone who understands the idea of fast row basically knows, but what is unsupervised? Speaking human language is essentially eliminating boundary judgment. Why do you leave out the boundary judgment? The CPU executes a sequential program (without branches like if), which is smooth and very fast, but when it encounters an if branch, the CPU suddenly brakes and slows down a lot. Allowing more time. If there are few boundary judgments, the program must be faster.
Base three points
The base value in the above plain quicksort is the leftmost by default. If the left-hand side is always the smallest or the largest value of the quicksort interval, it’s actually kind of awkward, and the time complexity is going to approach n squared. Pick the middle of arR [l],arr[(l+r)/2],arr[r]. It can’t be the worst, and it can’t be as bad as O(n squared).
Simple quicksort + unilateral recursion + unsupervised + three-point selection = quicksort of 🐂
show the code
function quick_sort_v2(arr, l, r) {
while (r - l >= 0) {
let x = l;
let y = r;
let base = medium_number(arr, l, r)// The function is not expanded when three points are taken
do {
while (arr[x] < base) x++;
while (arr[y] > base) y--;
if (x <= y) {
swap(arr[x], arr[y]);// The exchange of two values is not expandedx++; y--; }}while (x <= y)
quick_sort_v2(arr, l, y)
l = x;
}
return ;
}
Copy the codeQuicksort of 🐂 + unsupervised insertion sort = sort more than 🐂
What?? It’s probably a little surprising that this sort of cliche can be optimized again. Essentially the interpolation of the boundary judgment can be avoided Yang village head wrote the interpolation [escape
function unguard_final_insert_sort(arr, l, r) {
for(let cx=l+1; cx<=r; cx++)// Why is it called cx because of the number of loops in cx recently found in "preview assembly"
{
if(arr[cx]<arr[l])
{
let temp=arr[l]
arr[l]=arr[cx]
arr[cx]=temp
}
}
let preIndex,current
for(let i=l+2; i<=r; i++) { preIndex=i-1
current=arr[i]
while(preIndex>=l&&arr[preIndex]>current)
{
arr[preIndex+1]=arr[preIndex];
preIndex--; }
arr[preIndex+1]=current;
}
return ;
}
Copy the codeBack to the point, why is unsupervised interpolation plus 🐂 quicksort a better sort than 🐂? Because the speed of fast sorting is very fast, but as the data is divided again and again, the data will gradually be relatively orderly, fast sorting appears to be a waste of expression, so when the partition is very small, in fact, we can use unguard_insert_sort to sort. The combined code is as follows:
function quick_sort_v2(arr, l, r) {
while (r - l >= 16) {
let x = l;
let y = r;
let base = medium_number(arr, l, r)// The function is not expanded when three points are taken
do {
while (arr[x] < base) x++;
while (arr[y] > base) y--;
if (x <= y) {
swap(arr[x], arr[y]);// The exchange of two values is not expandedx++; y--; }}while (x <= y)
quick_sort_v2(arr, l, y)
l = x;
}
if (l < r) unguarded_final_insert_sort(arr, l, r);
return ;
}
Copy the codeUnsupervised insertion + heap +🐂 quicksort = I think 🐂 sort
I’ll leave it to you to realize, hey hey, in fact, I gave you the idea at the beginning. That’s the end of the day