排序算法 - 简书

一、归并排序
时间复杂度O(N*logN),空间复杂度O(N)

void merge(vector<int> arr, int left, int mid, int right){
  vector<int> help(right-left+1,0);
  int i=0;
  int p1=left;  //p1表示左部分下标
  int p2=mid+1;
  while(p1<=mid && p2<=right){//p1 p2都不越界
    help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
  }
  while(p1 <= mid) help[i++] = arr[p1++];
  while(p2 <= right)  help[i++] = arr[p2++];
  for(i = 0;i < help.size();i++)  {
    arr[left+i] = help[i];//把help里的内容拷贝到arr
  }
}
void mergSort(vector<int> &arr, int left, int right){
  if(left==right)  return;
  int mid=left+((right-left)>>1);
  mergeSort(arr,left,right);
  mergeSort(arr,mid+1,right);
  merge(arr,left,mid,right);
}
//主函数
void mergeSort(vector<int>& arr){
  if(arr.empty() || arr.size()<2){
    return;
  }
  mergeSort(arr,0,arr.size()-1);
}

归并排序的扩展
1、小和问题（p392）
2、逆序对问题

二、快速排序
1、partition（p411）
2、荷兰国旗问题
（1）当前值==key（划分值），cur直接跳下一个
（2）cur<key, cur与<区域下一个换，<区域扩，cur++
（3）cur>key, cur与>区域前一个换，>区域扩，cur不变
（4）当前区域的位置和>的区域位置碰上，结束

void partition(vector<int>& arr, int L, int R, int p){
  int less = L-1;//<区的右边界
  int more = R+1;//>区的左边界
  while(L < more){//L是当前数的下标
    if(arr[L] < p){
      swap(arr, ++less, L++);
    }else if(arr[L] > p){
      swap(arr, --more, L);
    }else{
      L++;
    }
  }
}

3、快速排序

void quickSort(vector<int> &arr){
  if(arr.empty()||arr.size()<2){
    return;
  }
quickSort(arr, 0, arr.size()-1);
}
void quickSort(vector<int>& arr, int L, int R){
  if(L < R){
    swap(arr, L+(int)random()*(R-L+1),R);//L..R上随机选一个值交换，随机选一个数作为划分值
    vector<int> p=oartutuin(arr, L, R);
    quickSort(arr, L, p[0] - 1);  // < 区
    quickSort(arr, p[1] + 1,R);  // > 区
  }
}
vector<int> partition(vector<int>& arr, int L, int R, int p){
  int less = L-1;//<区的右边界
  int more = R+1;//>区的左边界
  while(L < more){//L是当前数的下标
    if(arr[L] < p){
      swap(arr, ++less, L++);
    }else if(arr[L] > p){
      swap(arr, --more, L);
    }else{
      L++;
    }
  }
swap(arr, more, R);
vector<int> res{less+1, more};
return res; 
}

三、桶排序思想下的排序算法
1、计数排序

void countSort(vector<int>&arr){
  if(arr.empty() || arr.size()<2){
    return;
  }
  int max = INT_MIN;
  for(int i=0; i < arr.size(); i++){
    max = max(max, arr[i]);
  }
  vector<int> bucket(max+1, 0);
  for(int i=0; i<arr.size();i++){
    bucket[arr[i]]++;
  }
  int i=0;
  for(int j=0;j<bucket.size();j++){
    while(bucket[j]-- > 0){
      arr[i++]=j;
    }
  }
}

2、基数排序

主函数
void radixSort(vector<int> &arr){
  if(arr.empty() || arr.size()<2){
   return; 
  }
  radixSort(arr, 0, arr.size()-1, maxbits(arr));
}

int maxbits(vector<int> &arr){
//最大值是几个十进制位的函数
  int max = INT_MIN;
  for(int i=0;i<arr.size();i++){
    max = max(max,arr[i]);
  }
  int res = 0;
  while(max != 0){
    res++;
    max /= 10;
  }
  return res;
 }
//arr[begin...end]排序
void radixSort(vector<int>& arr, int begin, int end, int digit) {
  const int radix = 10;
  int i = 0, j = 0;
  //有多少个数准备多少个辅助空间
  vector<int> bucket(end-begin+1, 0);
  for(int d = 1; d <= digit; d++){ //有多少位就进出多少次
    //10个空间
    //count[0] 当前位（d位）是 0 的数字有多少个
    //count[1] 当前位（d位）是 0或1 的数字有多少个
    //count[2] 当前位（d位）是 0、1和2 的数字有多少个
    //count[i] 当前位（d位）是 0~i 的数字有多少个
    vector<int> count(radix, 0);  //count[0..9]
    for(i = begin; i<=end; i++){ //个位上统计词频 
      j = getDigit(arr[i], d);
      count[j]++;
     }
    for(i = 1; i<radix; i++){  //count记录 0-0的个数，0-1的个数，0-2的个数...
      count[i] = count[i] + count[i-1];
    }
    for(i = end; i>=begin; i--){
      j = getDigit(arr[i],d);
      bucket[count[j] - 1] = arr[i];
      count[j]--;
    }
    for(i = begin, j = 0; i<=end; i++, j++){
       arr[i] = bucket[j];
    }
  }
}

int getDigit(int x, int d){
  return ((x/((int)pow(10, d-1))) %10);
}