Freshman details on Algorithms - Quick Sorting - Notes

Why_ does_ it_ work 2021-11-25 15:31:16


sort() Basic usage
sort() The function can sort all elements of a given interval . It has three parameters sort(begin, end, cmp), among begin To point to the to be sort() Pointer to the first element of the array ,end To point to the to be sort() Pointer to the next position of the last element of the array ,cmp The parameter is sorting criteria ,cmp Parameters can be left blank , If not , Sort from small to large by default . If we want to sort from large to small, we can sort cmp The parameters are written as greater<int>() That's right int Array to sort , Of course <> We can also write double、long、float wait . If we need to follow other sorting criteria , Then we need to define a bool Type to pass in . For example, we sort an integer array from large to small :

using namespace std;
int main(){
int num[10] = {6,5,9,1,2,8,7,3,4,0};
for(int i=0;i<10;i++){
cout<<num[i]<<" ";
}// Output results :9 8 7 6 5 4 3 2 1 0
return 0;

Quick sort

In a string of numbers , The length is     Left end point ------------------------------------------------------------------ Right endpoint

1. Determine the cut-off point : Determine the median , Determine the left and right endpoints , random number    x

2. Adjustment interval : Less than or equal to x On the left , Greater than or equal to on the right    ( above all )

3. recursive : Recursively sort the left and right sides , The whole interval is in order

for example

1. Two arrays   a[],b[];

2. Scan all the numbers in the interval , If it is greater than x Just put it on the right , Less than x Just put it on the left

3. Finally, put all the numbers of the two arrays into the interval , Just sort it all

If you don't open up space, you can allocate both sides ?  The pointer allocates space , Small on the left, big on the right

Set two pointers ,i,j Put them on the left and right ends , Both hands go to the middle at the same time , If i Less than x It must end up on the left , After moving all the time , A value greater than x When , It should move to the right ,j It's the same , until i The number pointed to should be to the right ,j It's on the left , So let's take two numbers swap, until i and j meet , Just divide the interval into two

i The previous number must be less than x,j The number after must be greater than x

Example :3 1 2 3 5 In a string of numbers , set up x=3

First set the pointer i Point to 3,j Pointer to 5, here j Already equal to x=3,j yes 5, that j Move to the next 3, We'll exchange two numbers

secondly i Move to 1, Satisfaction is less than 3, Point to 2, Satisfaction is less than 3, here we are 3 When , stop ,j Move to 2, Dissatisfaction is greater than 3, stop , At this time, you have missed no merge , So not satisfied

Now separate the two groups ,3 1 2                   /             3 5 

Then separate and continue to arrange


using namespace std;
const int N=1e6+10;
typedef long long ll;
ll q[N];int n;
void quick_sort(int l,int r){
if(l>=r) return;
ll x=q[(l+r)>>1];
int i=l-1,j=r+1;
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}// Boundary treatment
int main(){
for(int i=0;i<n;i++) scanf("%lld",&q[i]);
for(int i=0;i<n;i++) printf("%lld ",q[i]);

Please bring the original link to reprint ,thank
Similar articles