Blue Bridge Cup Quick sort (code completion)

requirement ： Complete the code to achieve fast scheduling

Need to complete the code ：

#include <stdio.h>

void swap(int a[], int i, int j)
{
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

int partition(int a[], int p, int r)
{
    int i = p;
    int j = r + 1;
    int x = a[p];
    while(1){
        while(i<r && a[++i]<x);
        while(a[--j]>x);
        if(i>=j) break;
        swap(a,i,j);
    }
    _____________________;
    return j;
}

void quicksort(int a[], int p, int r)
{
    if(p<r){
        int q = partition(a,p,r);
        quicksort(a,p,q-1);
        quicksort(a,q+1,r);
    }
}
    
int main()
{
    int i;
    int a[] = {50,49,48,48,47,46,1,3,5,2,4,6,30,30,30,30};
    int N = 16;
    
    quicksort(a, 0, N-1);
    
    for(i=0; i<N; i++) printf("%d.", a[i]);
    printf("\n");
    
    return 0;
}

answer ： swap(a,j,p);

analysis ：

  First

What is the process of quick platoon ？

1. Two points

2. Set benchmark

3. If it is smaller than the reference point, put it to the left of the reference point , If it is larger than the reference point, put it to the right of the reference point , And this process is realized by constantly finding qualified element exchange

Note that it is placed on both sides of the benchmark , One thing must be done after the exchange of qualified elements ： Is the benchmark I selected not necessarily in the center of the eligible element , So we must exchange again , Let the benchmark go where it should be , The answer comes out

Sorting algorithm ：https://blog.csdn.net/qq_59700927/article/details/122638158