Leetcode 912. 排序数组

  1. class Solution {
  2. public:
  3.     void quick_sort(vector<int>& q, int l, int r){
  4.         if(l >= r) return;
  5.         int x = q[l + r >> 1];
  6.         int i = l - 1, j = r + 1;
  7.         while(i < j){
  8.             do i++; while(q[i] < x);
  9.             do j--; while(q[j] > x);
  10.             if(i < j) swap(q[i],q[j]);
  11.         }
  12.         quick_sort(q,l,j);
  13.         quick_sort(q,j+1,r);
  14.     }
  15.     void merge_sort(vector<int>& q, int l, int r){
  16.         if(l >= r) return;
  17.         int mid = l + r >> 1;
  18.         merge_sort(q,l,mid);
  19.         merge_sort(q,mid+1,r);
  20.         int k = 0 , tmp[r-l+1];
  21.         int i = l , j = mid + 1;
  22.         while(i <= mid && j <= r){
  23.             if(q[i] <= q[j]) tmp[k++] = q[i++];
  24.             else tmp[k++] = q[j++];
  25.         }
  26.         while(i <= mid) tmp[k++] = q[i++];
  27.         while(j <= r) tmp[k++] = q[j++];
  28.         for(int i = l , j = 0 ; i <= r ; i++,j++) q[i] = tmp[j];
  29.     }
  30.     vector<int> sortArray(vector<int>& nums) {
  31.         merge_sort(nums,0,nums.size() - 1);
  32.         quick_sort(nums,0,nums.size() - 1);
  33.         return nums;
  34.     }
  35. };