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