排序（Count Sort）

  • 平均时间复杂度：O(n+k)
  • 最好情况：O(n+k)
  • 最坏情况：O(n+k)
  • 空间复杂度：O(k)
  • 排序方式：外部

  • 稳定性：稳定

    C++代码实现

    1. int countSort(vector<int>& arr,int min=NULL,int max=NULL)
    2. {
    3.   if(min == NULL) min = *min_element(arr.begin(), arr.end());
    4.   if(max == NULL) max = *max_element(arr.begin(), arr.end());
    5.   int len = max - min + 1, offset = 0;
    6.   if(min < 0) offset = abs(min);
    7.   int barrel[len];
    8.   memset(barrel, 0, sizeof(barrel));
    10.   for(const auto& val:arr){
    11.       barrel[val + offset]++;
    12.   }
    14.   /* //不稳定
    15.   vector<int>::iterator it=arr.begin();
    16.   for(int i=0;i<len;i++){
    17.       while(barrel[i]!=0){
    18.           *it=i-offset;
    19.           it++;
    20.           barrel[i]--;
    21.       }
    22.   }
    23.   */
    24.   //稳定写法 
    25.   vector<int> record(arr.begin(),arr.end());
    26.   for(int i = 1; i < len; i++) {
    27.       barrel[i] += barrel[i-1]; 
    28.   }
    30.   for(int i = record.size() -1; i >= 0; i--){
    31.       arr[--barrel[record[i] + offset]] = record[i];
    32.   }
    33. }

1. 算法步骤

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数，存入数组barrel的第i项
  3. 对所有的计数累加（从barrel中的第一个元素开始，每一项和前一项相加）(为了稳定)
  4. 反向填充目标数组：将每个元素i放在新数组的第barrel[i]项，每放一个元素就将barrel[i]减去1

2. 动图演示

countingSort.gif