【算法】快排

题目

快排

思路

如果输入为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; }