【算法】快排

题目

快排

思路

如果输入为0或1直接返回；否则取一个基准值，可以取中间位置，如果输入是有序的可以避免时间过长，然后移动指针，先让i指针右移，如果小于基准值就继续右移，j指针左移同理。如果指针都停住，再看i<j，就交换。

代码

#include<iostream>
using namespace std;
void quick_sort(int q[], int l, int r)
{if (l >= r)return;int x = q[(l+r)/2], 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()
{int n;cin >> n;int q[n];for (int i = 0;i < n;i++){cin>>q[i];}quick_sort(q, 0, n - 1);for (int i = 0;i < n;i++){cout << q[i] << " ";}return 0;
}