The Linux static link library USES a class template quicksort algorithm

The essence of quicksort is to take a reference value ref from the array, put it to the right of ref and the left of ref, and repeat the action on both sides

Let's first list the quicksort steps:

1. Select a reference value ref from the array, which is larger than the reference value, and place it to the right of ref.

The above action divides the array into two parts:

A ref B

A is a smaller set of array elements than ref, which is still an array, and B is a larger set of elements than ref, which is still an array

2. Repeat the above actions on the left and right sides of ref until there is only one element left in both A and B, and the sorting is complete.

The emphasis is on how to select two sets A and B respectively. This step is called the partition action in the introduction to the algorithm.

First of all, the introduction to the algorithm inside the pseudocode posted, we first look at 1:

Let's look at the first ref selection method, which is ref = a[r]

partition(a[], p, r)
{
i = p
j = p-1
ref = a[r]
for(; i<r; i++)
{　　
if(a[i]<ref)
{
j++
exchange(a[i], a[j])
}
}
exchange(a[r], a[j+1])
return j+1;
}

First, find a reference value, ref = a[r]. For the sake of simplicity, take the last one as the reference value. In fact, you can go to any one as the reference value. We'll come back to this one.

Then define two cursors, i and j. i = p, j = p - 1. Why do we define it that way? The reason is that since we picked the first one, a[p], we are traversing from the first element of the array.

The purpose of j is to know the current position of the last value smaller than ref. Since we selected a[r] as the reference value and traversed from the first element, temporarily j= ES65en-1 in order to track the cursor of the last number smaller than ref. And you can think about what that means in a second.

Looking at the above code, we can see that j always records the last cursor of a number smaller than ref, so finally return j+1, all cursors smaller than ref have less than j+1, and all cursors larger than ref have more than j+2.

In summary, the purpose of executing partition is to get A, B, and intermediate cursors so that we can repeat the above actions for A and B, respectively.

Let's consider two other ways to select ref. Select the last value a[r] from above as a reference value, and at the end of the move to swap a[r] and a[j+1], we always want to know where we select the reference value in the process of partition, so that we can swap the values of a[refId] and j [j+1] in the last step. refId here represents the cursor that selects the ref value in a[].

If we select ref as the last value, then the position of this value is fixed in all partition procedures. But what if refId of ref is a random number in the range of p to r?

Obviously, if we randomly select the value of ref, it is possible for refId to exchange ref with other values during partition. At this point we need to update the cursor corresponding to ref.

So if you start with 1, then you have a clear idea.

First, the pseudo-code of partition is given:

partition(a[], p, r){
refId = random(p,r)
i = p
j = p-1
for(; i<=r; i++)
{
if(a[i]<ref)
{
j++ if(j == refId)// At this time j Just etc. refId And you're going to have to do the same a[i] Swap, update refId { refId = i }
exchange(a[i], a[j])
}
}
exchange(a[j+1], a[refId])
return j+1
}

From the three methods of selecting ref, you can see that they are essentially one cursor, each with one cursor j to record the last traversal of data smaller than ref, and then exchange ref and a[j+1], returning j+1.

The code implementation of C++ is given below

#include <iostream>
#include <stack>
#include"stdlib.h"
#include <time.h>

using namespace std;
template<class T>
class SORT
{
public:
static void myQsort(T a[], int p, int r);
static void myQsortNoRecur(T a[], int p, int r);
private:
static int partition(T a[], int p, int r);
static void exchange(T a[], int i, int j);
};
template<class T>
void SORT<T>::exchange(T a[], int i, int j)
{
T temp = a[i];
a[i] = a[j];
a[j] = temp;
return;
}
template<class T>
int SORT<T>::partition(T a[],int p,int r)
{
int i = p;
int j = p-1;
T ref = a[p];
int refId = p;
srand((unsigned)time(NULL));
refId = (rand() % (r-p+1))+ p;
//cout<<refId<<endl;
ref = a[refId];
for(; i<=r; i++)
{
if(a[i] < ref)
{
j++;
exchange(a, i, j);
if(j == refId)
{
refId = i;
}
}
}
exchange(a, j+1, refId);
return j+1;
}
template<class T>
void SORT<T>::myQsort(T a[],int p,int r)
{
int q = 0;
if(p<r)
{
q = partition(a, p, r);
myQsort(a, p, q-1);
myQsort(a, p+1, r);
}
return;
}
template<class T>
void SORT<T>::myQsortNoRecur(T a[], int p, int r)
{
int start = p;
int end = r;
int mid = 0;
std::stack<int> sortStk;

sortStk.push(p);
sortStk.push(r);

while(!sortStk.empty())
{
end = sortStk.top();
sortStk.pop();
start = sortStk.top();
sortStk.pop();
if(start < end)
{
mid = partition(a, start, end);
sortStk.push(start);
sortStk.push(mid -1);
sortStk.push(mid + 1);
sortStk.push(end);
}
}
}
int main(int argc, char** argv)
{
int a[10];
int b[10];
srand((unsigned)time(NULL));
for(int i=0; i<9; i++)
{
a[i] = rand();
}

srand((unsigned)time(NULL));
for(int i=0; i<9; i++)
{
b[i] = rand();
}

SORT<int>::myQsort(a,0, 9);

SORT<int>::myQsortNoRecur(b,0, 9);

for(int i=0; i<10; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
for(int i=0; i<10; i++)
{
cout<<b[i]<<" ";
}
return 0;
}

In the above code, I directly present the recursive and non-recursive implementations of quicksort.
The recursive implementation is easy to understand, but if someone is interviewing you for a quicksort algorithm, you'll probably want to show them a non-recursive implementation. So let's talk about 1.

Look at how the recursion algorithm works in 1, each time calling the partition function on a smaller scope of 1 segment. So we need to know that every call to the partition function produces a new start and end cursor.

template<class T>
void SORT<T>::myQsort(T a[],int p,int r)
{
int q = 0;
if(p<r)
{
q = partition(a, p, r);
myQsort(a, p, q-1);
myQsort(a, p+1, r);
}
return;

}

In this way, we can use a generic container to hold the start and end cursors generated by each call to partition. You know that there are valid start and end cursors that both call the partition function as arguments. The so-called legal start and end are start < end...

For a non-recursive implementation of a recursive algorithm, the first data structure that comes to mind must be the stack. Other data structures, such as queues, can also be implemented. The implementation method of stack based on stl is given here. The following code

template<class T>
void SORT<T>::myQsortNoRecur(T a[], int p, int r)
{
int start = p;
int end = r;
int mid = 0;
std::stack<int> sortStk;

sortStk.push(p);
sortStk.push(r);

while(!sortStk.empty())
{
end = sortStk.top();
sortStk.pop();
start = sortStk.top();
sortStk.pop();
if(start < end)
{
mid = partition(a, start, end);
sortStk.push(start);
sortStk.push(mid -1);
sortStk.push(mid + 1);
sortStk.push(end);
}
}
}

The above code runs as each loop, taking 1 start and end from the container, and, if it is legal, placing them again in turn, knowing that the container is empty and unknown.

Give a running example, What I implemented in the code is to implement random number sorting, ref adopts the method of random selection.