计数排序算法

​
 

文章目录

1. 算法思想
2. 算法图解
3. 代码实现
4. 算法特点
5. 算法思想

一提到排序，大多的思路都离不开数据之间的比较，今天分享一种不需要比较的排序思路

计数排序就是一个排序时不比较元素大小的排序算法

对一定范围内的整数排序的时候速度非常快，优于其他算法。同时局限性也比较大，只能对于整数进行排序，并且待排序元素分布较连续，跨度小的情况

如果一个数组里所有元素都是整数，且在0—k以内，那对于这个数组的每个元素来说，如果能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置

具体操作步骤

我们来看这个数组

 对于这个数组，元素5之前有8个元素小于或等于5，包含5，因此排序后5所在的位置肯定是7

因此我们构造一个（5+1）大小的数组，里面存下所有对应A中每个元素之前的元素个数，就能在线性时间内完成排序

1. 算法图解

 升序图示：

接下来我们的操作是：初始化一个大小为（5+1）的计数数组，所有元素值为0，遍历整个数组，将原始数组中的每个元素值转化为计数数组的下标，并将计数数组下标对应的元素值大小+1

接下来我们开始遍历计数数组，然后对原数组进行操作

计数数组0位置的值是2，我们在原始数组的前两个位置放入0，放入一个值后，计数数组该位置的值就减1，原始数组索引向后移动准备存放下一个值

当计数数组的0位置元素值减为0时，计数数组索引向后移动指向下一个位置，如果下一个位置元素为0 ，即证明没有当前下标的元素，索引继续后移

每次在原始数组放进一个元素时，计数数组的某个位置的元素值都会减一，直到计数数组的值全为0时，排序已经完成

1. 代码实现

在实际应用中，我们会同时找出数组中的max和min，主要为了节省空间。如果[1004,1020,1070]这样的数据要排序，是不需要建立1070+1这样的计数数组的，只需要长度为1070-1004+1=67的数组，就能囊括从最小到最大元素之间的所有元素了

如果待排序数组的元素值跨度太大了，就不要用计数排序了，太浪费空间了

我们看计数排序的代码:

import java.util.Arrays;

public class CountingSort {

public int[] sortArray(int[] nums){
    if(nums.length==0)return nums;
    //寻找最大值和最小值
    //bias：偏移量，用于定位每个元素在计数数组中的下标位置
    int bais,min=nums[0],max = nums[0];
    for (int i = 1; i < nums.length ; i++) {
        if(nums[i]>max)
            max = nums[i];
        if(nums[i]<min)
            min = nums[i];
    }
    bais = 0-min;
    //获得计数数组内容
    int[] counterArray = new int[max-min+1];
    Arrays.fill(counterArray,0);

    //遍历整个数组，将原始数组每个元素转化为计数数组的下标
    //并将计数数组下标对应的元素值大小进行累加
    for (int i = 0; i < nums.length; i++) {
        counterArray[nums[i]+bais]++;
    }
    System.out.println("计数数组为");
    PrintArray.print(counterArray);
    System.out.println("-----------");
    int index = 0;//访问原始数组的下标计数器
    int i = 0;//访问计数数组的下标计数器
    //开始访问计数数组，将计数数组的元素转换后，重新写回原始数组
    while(index<nums.length){
        //只要计数数组当前下标元素的值不是0，就将计数数组的元素转换后重新写回原始数组
        if(counterArray[i]!=0){
            nums[index] = i-bais;
            counterArray[i]--;
            index++;
        }
        else i++;
        PrintArray.print(counterArray);
        PrintArray.print(nums);
        System.out.println("---------");
    }

    return nums;
}

public static void main(String[] args) {
    int[] array = {2,5,3,0,2,3,0,3};
    CountingSort countingSort = new CountingSort();
    countingSort.sortArray(array);
}

}
class PrintArray{

public static void print(int[] nums){
    System.out.println(Arrays.toString(nums));
}

}
结果：

1. 算法特点

时间复杂度为O(n+k)，空间复杂度为O(n)，适合数据范围跨度较小的排序

​