#include <iostream>#include <vector>using namespace std;void show(vector<int>& a) { for (int i = 0; i <= a.size() - 1; i ++) { cout << a[i] << " "; } cout << endl;}int quick_sort(vector<int>& a, int left, int right) { if (left > right) { return -1; } int pivot = a[left]; int i = left; int j = right; while (i != j) { while(i < j && a[j] >= pivot) { j--; } a[i] = a[j]; while (i < j && a[i] <= pivot) { i++; } a[j] = a[i]; } a[i] = pivot; quick_sort(a, left, i - 1); quick_sort(a, i + 1, right);}int main() { vector<int> a; int t; for(int i = 1; i <= 5; i++) { cin >> t; a.push_back(t); } quick_sort(a, 0, a.size() - 1); show(a);}
第一层排序 左边排序 右边排序 一共o(n)
第二层 也是o(n)
第三层 也是o(n)
一共 log(2)n层
时间复杂度== o(nlogn)