分治

• 归并排序

  #include<iostream>
  using namespace std;
  void merge(int a[],int start,int mid, int end,int temp[]){
      int L = start,R = mid+1;
      int pb = 0;
      while(L<=mid && R<= end){
          if(a[L] < a[R]){
              temp[pb++] = a[L++];
          }
          if(a[L] >= a[R]){
              temp[pb++] = a[R++];
          }
      }
      //如果归并的两个数组长度不一样
      while (L <= mid)
      {
          temp[pb++] = a[L++];
      }
      while (R <= end)
      {
          temp[pb++] = a[R++];
      }
      //把temp中的值赋值给a
      //赋给a的从start到end
      for(int i = start;i <= end;i++){
          a[i] = temp[i-start];
      }
      //return;
  }
  void sort(int a[],int start,int end,int temp[]){
      if(start < end){
          
          int mid = start +(end-start)/2;
          sort(a,start,mid,temp);
          sort(a,mid+1,end,temp);
          merge(a,start,mid,end,temp);
      }
      //return;
  }
  int a[10] ={2,4,3,1,5,7,8,0,33,22};
  int b[10];
  int main(){
      int size = sizeof(a)/sizeof(int);
      //传参跟函数实现有关系
      sort(a,0,size-1,b);
      for(int i = 0;i<size;i++){
          cout << a[i] << ' ';
      }cout << endl;
      return 0; 
  }
  

  左闭右开算法

  # include<iostream>
  using namespace std;
  void Merge(int a[],int start,int mid,int end,int temp[]){
      int L = start,R = mid;
      int pb = 0;
      while(L < mid && R< end){
          if(a[L]<a[R]){
              temp[pb++] = a[L++];
          }else{
              temp[pb++] = a[R++];
          }
      }
      //两个数组不等长
      while(L < mid){
          temp[pb++] = a[L++];
      }
      while(R < end){
          temp[pb++] = a[R++];
      }
      //把temp复制给a
      for(int i = start;i < end;i++){
          a[i] = temp[i-start];
      }
      //return;
  }
  void MergeSort(int a[],int start,int end,int temp[]){
      if(end - start > 1){
          int mid = start + (end-start)/2;
          // [start,mid)
          MergeSort(a,start,mid,temp);
          MergeSort(a,mid,end,temp);
          Merge(a,start,mid,end,temp);
      }
      //return;
  }
  int main(){
      int a[10] ={2,4,3,1,3,7,8,0,33,22};
      int b[10];
      //int size = sizeof(a)/sizeof(int);
      //传参跟函数实现有关系
      MergeSort(a,0,10,b);
      for(int i = 0;i<10;i++){
          cout << a[i] <<' ';
      }cout << endl;
      return 0; 
  }
  

• 快速排序

# include<iostream>
using namespace std;
void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}
void QuickSort(int a[],int start,int end){
    if(end <= start) return;
    int k = a[start];
    int L = start,R = end;
    while (L != R){
        //如果没有这个等号，当数组里有相等的元素时，会出现死循环
        while (a[R] >= k && L<R){
            R--;
        }
        swap(a[R],a[L]);
        while (a[L] <= k && L<R){
            L++;
        }
        swap(a[L],a[R]);
    }
    int pivote = L;
    QuickSort(a,start,pivote-1);
    QuickSort(a,pivote+1,end); 
}
int main(){
    int a[10] ={2,4,3,1,3,7,8,0,33,22};
    QuickSort(a,0,9);
    for(int i = 0;i<10;i++){
        cout << a[i] << ' ';
    }
}