Quick sort_ sort

Quick sort

The algorithm idea of quick sort I want to introduce today is the divide and conquer idea , This can be achieved in three steps ;

1. Determine the cut-off point x：

The commonly used value dividing point is ： q[l] q[(l+r)/2] q[r];

2. Adjustment interval （ The core step ）：

Make all the sections to the left of the dividing point <=x, All sections to the right of the dividing point >=x;

3. Recursive left and right intervals ;

Core code

void quick_sort(int q[],int l,int r)
{
    
    if(l>=r)return;
    int x=q[l],i=l-1,j=r+1;
    while(i<j)
    {
    
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

Put on a classic fast board problem

Input
The first line is an integer n（1<=n<=100000）
The second line is n Integers separated by spaces qi（0<=qi<=10^9）

Output
Output the result of ascending sort in one row .

#include<iostream>
using namespace std;
const int N = 1e6+10;

int q[N];
int n;

void quick_sort(int q[],int l,int r)
{
    
    if(l>=r)return;
    int x=q[l],i=l-1,j=r+1;
    while(i<j)
    {
    
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}
int main()
{
    
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);

    quick_sort(q,0,n-1);

    for(int i=0;i<n;i++)printf("%d ",q[i]);
    
    return 0;
}

This is the basic quick sort introduced today , It can greatly reduce the time complexity of the algorithm , After learning the new algorithm, you'd better find some problem brushes , Keep the thought and board firmly in mind to achieve a stable effect .