计数排序

痛定思痛。 2023-02-20 10:43 56阅读 0赞

# 计数排序 #

冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序，平均时间复杂度最低是O(nlogn)。

计数排序、桶排序、基数排序，都不是基于比较的排序，它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比O(nlogn)更低。

计数排序（Counting Sort）于1954年由Harold H. Seward提出，适合对一定范围内的整数进行排序。

计数排序的核心思想：统计每个整数在数组中出现的次数，进而推导出每个整数在有序数组中的索引。

## 最简单的实现 ##

具体实现步骤如下：

1.  找出数组array中的最大值max。
2.  开辟一个数组countsArray，数组大小为max+1,用于存放数组array中每个元素出现的次数，数组countsArray的索引为数组array的元素，数组countsArray值为数组array的元素出现的次数。
3.  遍历数组countsArray就可以得到有序数组。

![计数排序][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]  
代码实现如下：

// 找出最大值
    int max = array[0];
    
    for (int i = 1; i < array.length; i++) { 
        if (array[i] > max) { 
            max = array[i];
        }
    }
    
    // 开辟一个数组，用于存放每个元素出现的次数
    int[] countsArray = new int[max + 1];
    
    // 统计每个元素出现的次数
    for (int i = 0; i < array.length; i++) { 
        countsArray[array[i]]++;
    }
    
    // 排序
    int cur = 0;
    for (int i = 0; i < countsArray.length; i++) { 
        while (countsArray[i]-- > 0) { 
            array[cur++] = i;
        }
    }

这个实现存在以下问题：

*  无法对负整数进行排序，上面的实现中数组countsArray的索引为元素，而索引不可能出现负整数。
 *  极其浪费内存空间，最小的元素以下的空间都是浪费。
 *  是一个不稳定的排序。

## 计数排序优化 ##

假设array中的最小值为min，最大值为max：

1.  开辟的计数数组countsArray大小为max-min+1，减少了空间的浪费。
2.  array中的元素k对应的countsArray索引是k–min，值为元素出现的次数，与简单实现一样。
3.  数组countsArray中每个索引的值叠加前一个索引的值，这样所有值就对应有序数组中的索引。
4.  遍历数组array，array中的元素k在有序数组newArray（要新开辟一个数组来存放有序元素）中的索引为countsArray\[k–min\]–p，p代表着是倒数第几个k。

比如元素8在有序数组中的索引为countsArray\[8–3\]–1，结果为7。

倒数第1个元素7在有序序列中的索引countsArray\[7-3\]–1，结果为6。

倒数第2个元素7在有序序列中的索引countsArray\[7–3\]–2，结果为5。

![计数排序优化][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]  
代码实现如下：

// 找出最大值
    int max = array[0];
    // 找出最小值
    int min = array[0];
    for (int i = 1; i < array.length; i++) { 
        if (array[i] > max) { 
            max = array[i];
        }
    
        if (array[i] < min) { 
            min = array[i];
        }
    }
    
    // 开辟一个数组，用于存放每个元素出现的次数
    int[] countsArray = new int[max - min + 1];
    
    // 统计每个元素出现的次数
    for (int i = 0; i < array.length; i++) { 
        countsArray[array[i]]++;
    }
    
    // 每个次数叠加前面的次数
    for (int i = 1; i < countsArray.length; i++) { 
        countsArray[i] += countsArray[i - 1];
    }
    
    // 开辟一个新数据用来存放有序数组
    int[] newArray = new int[array.length];
    
    for (int i = array.length; i >= 0; i++) { 
        newArray[--countsArray[array[i] - min]] = array[i];
    }
    
    // 将新数组数据覆盖旧数组
    for (int i = 0; i < newArray.length; i++) { 
        array[i] = newArray[i];
    }

计数排序的最好、最坏、平均时间复杂度为O(n+k)，空间复杂度为O(n+k)（其中k是整数的取值范围），属于稳定排序。

更多精彩内容关注本人公众号：架构师升级之路  
![公众号][20200626084551697.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200626084351285.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200626084418358.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[20200626084551697.jpg]: https://img-blog.csdnimg.cn/20200626084551697.jpg