今天写个排序方法总结

一、冒泡排序
时间复杂度O（n^2），相邻两个元素一一比较，不断把大的元素往后排，经过第一轮后，最大值就出来了。

 vector<int> BuddersortArray(vector<int>& nums) {
     //冒泡
     for(int i=0;i<nums.size()-1;i++){
         for(int j=0;j<nums.size()-1-i;j++){
             if(nums[j] > nums[j+1]) swap(nums[j],nums[j+1]);
         }
     }
     return nums;
 }

选择排序
时间复杂度O（n^2），不断最小的元素，依次往前放，经过第一轮会把最小的元素给放出来.
若要改成从大到小，把<改成>即可。

  vector<int> sortArray(vector<int>& nums) {
      //选择
      for(int i = 0;i<nums.size();i++){
          int index = i;
          for(int j = i;j<nums.size();j++){
              if(nums[j] < nums[index]){
                  index = j;//找最小元素
              }
          }
          swap(nums[i],nums[index]);
      }
      return nums;
  }

插入排序
时间复杂度O（n^2）,当新来一个元素时，从后面两两比较已经排好序的元素，然后往前插入。
若要改成降序，把<改成>即可。

  vector<int> sortArray(vector<int>& nums) {
      //插入排序
      for(int i=0;i<nums.size();i++){
          for(int j=i;j>0;j--){
              if(nums[j] < nums[j-1]) swap(nums[j],nums[j-1]);
              else break;
          }
      }
      return nums;
  }

快速排序
鼎鼎大名的快排来了，对于C++中algorithm库中的sort函数用的就是快排，时间复杂度O（NlogN）
不断让队首元素v到该去的位置j上，同时，使得数组的j之前的元素都小于v，j后面的元素都大于v

  vector<int> sortArray(vector<int>& nums) {
      quickSort(nums,0,nums.size()-1);
      return nums;
  }

  void quickSort(vector<int>& nums,int l,int r){
      if(l >= r) return;
      int mid = partion(nums,l,r);
      quickSort(nums,l,mid-1);
      quickSort(nums,mid+1,r);
  }

  int partion(vector<int>& nums,int l,int r){
      //将l放到正确的位置上j上，同时让j左端的全部小于l，让j右边的全部大于等于j
      int v = nums[l];
      int j = l;//j表示当前数组中小于v的最右边界
      for(int i=l+1;i<=r;i++){
          if(nums[i] < v){
              swap(nums[i],nums[++j]);
          }
      }
      //让v到自己该到的位置上
      swap(nums[l],nums[j]);
      return j;
  }

为了改善近乎有序数组的性能退化，在partion中，不选择l元素，随机选一个元素，
int v = nums[rand()%(r-l)+l];

双路快排
针对数组中有大量的重复元素的时候，快排会退化为O（n^2）的算法，因此针对上述问题设计双路快速排序算法和三路快速快排，此处先只列双路快排

  vector<int> sortArray(vector<int>& nums) {
      quickSort(nums,0,nums.size()-1);
      return nums;
  }

  void quickSort(vector<int>& nums,int l,int r){
      if(l >= r) return;
      int mid = partion(nums,l,r);
      quickSort(nums,l,mid-1);
      quickSort(nums,mid+1,r);
  }

  int partion(vector<int>& nums,int l,int r){
      int v = nums[l];
      int i = l+1,j=r;
      while(1){
          while(i<=r && nums[i] <= v) i++;
          while(j>=l+1 && nums[j] >= v) j--;
          if(i > j) break;
          swap(nums[i],nums[j]);
          i++;
          j--;
      }
      swap(nums[l],nums[j]);
      return j;
  }

注意在partion中右边的边界左移时
while(j>=l+1 && nums[j] >= v) j--;
j要大于等于的l+1，因为此时移动的左边界为l，且l为要改变位置的数字。

归并排序
时间复杂度O（NlogN）的排序算法还有归并排序，利用分治和递归的思想，将数组一份为2。

  vector<int> sortArray(vector<int>& nums) {
      mergesort(nums,0,nums.size()-1);
      return nums;
  }
  void mergesort(vector<int>& nums,int l,int r){
      if(l >= r) return;
      int mid = l + (r-l)/2;
      mergesort(nums,l,mid);
      mergesort(nums,mid+1,r);
      merge(nums,l,r,mid);
  }

  void merge(vector<int>& nums,int l,int r,int mid){
      vector<int> copynum(r-l+1);
      for(int i = l;i<=r;i++){
          copynum[i-l] = nums[i];
      }
      int i = l,j = mid+1;
      for(int k=l;k<=r;k++){
          //注意数组索引的溢出
          if(i > mid){
              nums[k] = copynum[j-l];
              j++;
          }else if(j > r){
              nums[k] = copynum[i-l];
              i++;
          }else if(copynum[i-l] > copynum[j-l]){
              nums[k] = copynum[j-l];
              j++;
          }else{
              nums[k] = copynum[i-l];
              i++;
          }
      }
  }

由底向上的归并排序
vector<int> sortArray(vector<int>& nums) {</int></int>

  mergesortBU(nums);
  return nums;

}
//不知道为什么，在leetcode上,内循环如果变量和运算符之间不加空格不能通过编译
void mergesortBU(vector<int>& nums){</int>

  for(int sz = 1;sz <= nums.size();sz += sz){
      for(int i=0 ; i<nums.size() ;i += 2*sz){
          int t = i+2*sz-1 < nums.size()-1? i+2*sz-1: nums.size()-1;
          merge(nums, i, t,i+sz-1);
      }
  }

}

void merge(vector<int>& nums,int l,int r,int mid){</int>

  vector<int> copynum(r-l+1);
  for(int i=l;i<=r;i++){
      copynum[i-l] = nums[i];
  }
  int i = l,j = mid + 1;
  for(int k = l;k<=r;k++){
      if(i > mid){
          nums[k] = copynum[j-l];
          j++;
      }else if(j > r){
          nums[k] = copynum[i-l];
          i++;
      }else if(copynum[i-l] > copynum[j-l]){
          nums[k] = copynum[j-l];
          j++;
      }else{
          nums[k] = copynum[i-l];
          i++;
      }
  }

}
先缓一缓，写不下去了，等回头补上三路快排、堆排序