快速排序

最差情况（n2）：每次都只划分成（1个和剩下的），例如对排序好的数组，如果轴值每次都取第一个，那么每次都是分成1和剩下的，需要n次。
最差情况优化：可以随机取轴值（pivot）的位置，rand（）用来确定pivot的位置。
最好情况（nlogn）：每次都划分成等大（或者差1）的两块。树深为logn。

  1. class Solution {
  2. public: 
  3.     int partition(vector<int>& nums,int l,int r){
  4.         int pivot = nums[r];
  5.         int i = l;
  6.         for(int j=l;j<r;j++){
  7.             if(nums[j]<pivot){
  8.                 swap(nums[i++],nums[j]);
  9.             }
  10.         }
  11.         swap(nums[i],nums[r]);
  12.         return l;
  13.     }
  14.     void qSort(vector<int>& nums,int l,int r){
  15.         if(l>=r){
  16.             return ;
  17.         }
  18.         int mid = partition(nums,l,r);
  19.         qSort(nums,l,mid-1);
  20.         qSort(nums,mid+1,r);
  21.     }
  22.     vector<int> sortArray(vector<int>& nums) {
  23.         qSort(nums,0,nums.size()-1);
  24.         return nums;
  25.     }
  26. };

堆排序

升序排序：建一大顶堆，然后，每次把堆顶元素（最大）的换到最后，size-1后调整堆。

  1. public:
  2.     void maxHeapify(vector<int>& nums,int father,int heapSize){
  3.         int l = father*2+1,r=father*2+2,largest=father;
  4.         if(l<heapSize&&nums[l]>nums[largest]){
  5.             largest = l;
  6.         }
  7.         if(r<heapSize&&nums[r]>nums[largest]){
  8.             largest = r;
  9.         }
  10.         if(largest!=father){
  11.             swap(nums[father],nums[largest]);
  12.             maxHeapify(nums,largest,heapSize);
  13.         }
  15.     }
  16.     void buildMaxHeap(vector<int>& nums,int heapSize){
  17.         for(int i=heapSize/2;i>=0;i--){
  18.             maxHeapify(nums,i,heapSize);
  19.         }
  20.     }
  21.     vector<int> sortArray(vector<int>& nums) {
  22.         int n = nums.size();
  23.         int heapSize = n;
  24.         buildMaxHeap(nums,heapSize);
  25.         for(int i=n-1;i>=0;i--){
  26.             swap(nums[0],nums[heapSize-1]);
  27.             heapSize--;
  28.             maxHeapify(nums,0,heapSize);
  29.         }
  30.         return nums;
  31.     }
  32. };