计数排序(counting sort)

10大排序算法.png

计数排序于1954年由Harold H.Seward提出，适合对一定范围内整数进行排序，计数排序的核心思想是: 统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引

计数排序最简单实现.png

之前学习的冒泡、选择、插入、归并、快速、希尔、堆排序都是基于比较的排序，平均复杂度目前最低是O(nlogn)
计数排序、桶排序、基数排序则不是基于比较的排序算法，它们是典型的用空间换时间，在某些时候平均复杂度可以比O(nlogn)更低

计数排序最简单实现
private void sort() {

    //找出最大值
    int max = list[0];
   for(int i = 1; i < list.length;i++) {
       if(list[i] > max ) {  
          max = list[I]; 
       }
   }

   //开辟内存空间，存储每个整数出现的次数
   int counts = new int[1+max];
   //统计每个整数出现的次数
   for(int i = 0;i < list.length;i++)  {
     // int idx =  list[I];//取出数组中的值
     // int val = counts[idx];//以值为索引 取出出现次数
     //val++;//次数加加
      counts[list[i]]++;
   }

  //根据整数出现次数，对整数进行排序
  int idx = 0; //list数组可以放整说的索引位
  for(int i = 0;i < counts.length;i++) {
     while(counts[i]-- > 0) {
           list[idx] = I; 
           idx++；
     }
}

计数排序最简单实现缺点：

• 无法对负整数进行排序
• 极其浪费内存空间
• 是个不稳定排序

计数排序改进思路：
执行流程：
1.找到数组(array)中对最小值，counts的长度就是 max - min +1
2.计算array每个元素出现的次数 保存到counts中
3.让每个元素次数等于自己出现次数 + 前一个元素次数
4.每个array中元素排序后的索引就应该是: 元素次数 - (自己出现次数--) 且 自己出现次数 > 0

改进思路示例.png

假设array中最小值是min

• array中的元素 v 对应的在counts索引就是: v - min ; 理解 3-3 == 0 那么3在counts的索引就是0
• array中的元素v在将来有序序列中的索引递推公式是：counts[v-min] - p, p代表倒数第几个v

private void sort() {

    //1.找出最大值、最小值
    int max = array[0];
    int min = array[0];
   for(int i = 1; i < array;i++) {
       if(array[i] > max ) {  
          max = array[i]; 
       }
       if(array[i] < max ) {  
          min = array[i]; 
       }
   }

   //2.开辟内存空间，存储次数
   int counts = new int[max-min+1];
   //2.1统计每个整数出现的次数
   for(int i = 0;i < array.length;i++)  {
      int idx =  array[I] - min;
      counts[idx]++;
   }

  //2.2累加次数，每遍历一位就拿前一位的次数加当前元素出现次数
  for(int i = 1;i < counts.length;i++) {
      counts[i]  =   counts[i] + counts[i-1];
  }
  
//3.从后往前遍历元素，将它放在有序序列中的合适位置
 //技巧：从后往前遍历可以保证稳定性，相同数字相对位置不变
int[] output = new int[array.length];
for(int i = array.length - 1; i >=0;i--) {
     //array[i] - mid: array数组i位置的元素在counts数组中的索引
     //counts[array[i]-mid]: 索引位存储的次数
     //--(counts[array[i]-mid]): 索引位存储的次数减1后再把得到的值存起来, 这个减1后得到的值就是 array数组i位置的元素将来在有序序列中的索引
      int idx = --(counts[array[i]-mid]);
     // 将元素放在有序序列中的合适位置
      output[idx] = array[i];
}

//4.将排好序的数组覆盖掉array
for(int i = 0;i < array.length;i++) {
    array[I] = output[I];
}

改进后：

• 可以对负整数进行排序
• 不再对空间浪费
• 是稳定排序

复杂度分析：

• 最好、最坏、平均时间复杂度： O(n+k)
• 空间复杂度：O(n+k)
• k是整数的取值范围, 也可以理解是数据规模
• 属于稳定排序