Summary: algorithm practice summary

AcWing785 Quicksort

The title

Given you a sequence of integers of length N.

Use quicksort to sort the number from smallest to largest.

And the ordered sequence is output in order.

The sample

Example Input:

5, 3, 1, 2, 4, 5Copy the code

Example output:

One, two, three, four, fiveCopy the code

Train of thought

Find a value against which each operation is based:

  • If the number is less than the reference value, the number is placed on the left;
  • If the number is greater than the reference value, the number is placed to the right;
  • After each sorting, the front digit of the array is less than the reference value, and the back digit of the array is greater than the reference value;
  • Continue recursively for the next quicksort of front and back;

code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int nums[N];

void quick_sort(int x, int y) {
    // End the recursion when there is only one number in the interval
    if(x >= y) return;
    // Select the middle value as the reference value each time
    int t = nums[(x+y)/2];
    // To avoid overflow, preprocess in advance
    int l = x- 1;
    int r = y+1;
    // The double pointer checks the front and back of the array
    while(l < r) {
        // Find a number whose front part is larger than the base value
        while(nums[++l] < t);
        // Find a number whose back is less than the reference value
        while(nums[--r] > t);
        // Switch the two numbers
        if(l < r) {
            swap(nums[l], nums[r]); }}// Continue the quicksort on the front
    quick_sort(x, r);
    // Continue the quicksort on the back
    quick_sort(r+1, y);
}

int main(a) {
    int n;
    cin>>n;
    for(int i = 0; i < n; ++i) {
        cin>>nums[i];
    }
    quick_sort(0, n- 1);
    for(int i = 0; i < n; ++i) {
        cout<<nums[i]<<"";
    }
    return 0;
}
Copy the code