ambition-xx

qsort

Apr 18th, 2022 (edited)
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.67 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void print(vector<int> &arr){
  5.     for(auto &a : arr){
  6.         cout << a << " ";
  7.     }
  8.     cout << endl;
  9. }
  10.  
  11. void qsort(vector<int> &arr, int start, int end){
  12.     if(end - start <=  1) return ;
  13.     int val = arr[start];
  14.     int i = start, j = end - 1;
  15.     while(i < j){
  16.         // 1.应该让i从start开始 2.应该先缩小j的范围
  17.         while(i < j && arr[j] > val) j--;
  18.         while(i < j && arr[i] <= val) i++;
  19.         swap(arr[i], arr[j]);
  20.     }
  21.     print(arr);
  22.     swap(arr[start], arr[i]);
  23.     qsort(arr, start, i);
  24.     qsort(arr, i + 1, end);
  25. }
  26.  
  27. int main(){
  28.     vector<int> nums = {4,5,67,8,89,8999,3443};
  29.     qsort(nums, 0, nums.size());
  30.     print(nums);
  31.     return 0;
  32. }
Add Comment
Please, Sign In to add comment