您现在的位置是：首页 >学无止境 >十大排序算法(下)：计数排序，基数排序，桶排序网站首页学无止境

十大排序算法(下)：计数排序，基数排序，桶排序

是布谷阿 2024-06-17 11:19:00
简介十大排序算法(下)：计数排序，基数排序，桶排序

文章目录

5. 其他非基于比较的排序

5.1 计数排序

有n个数，取值范围是 0~n，写出一个排序算法，要求时间复杂度和空间复杂度都是O(n)的

我们知道，前面介绍的基于比较的排序算法中，最好的算法，其平均时间复杂度都在O(N)，达到线性的时间复杂度就要使用新的排序算法，而这种方法，就称为是计数排序。

计数排序的思路：对于每一待排序元素a，如果知道了待排序数组中有多少比它小的数，就可以直接知道排序后的数组中，a在什么位置上。比如，如果一个数组中有三个数比a小，那么排序后的数组中，a一定会出现在第4位。

那么现在问题转化成，堆排序数组里的数，如何能快速的指导比它小的数字有多少。要解决这个问题，我们不能用比较的办法，因为时间复杂度会高于O(N)，只有一个思路，就是用空间来换取时间。不妨设一个大小为(max - min + 1)的数组（其中max是数组中的最大值，min是数组中的最小值）来统计每个数字出现的次数。这就类似于直方图，因此计数排序被称作是基于统计的排序。

假设计数排序算法的输入是数组arr，大小为n，而存放排序结果的数组为B，还需要一个 存放临时结果，也就是我们上面提到的直方图结果的数组count。那么计算排序的步骤如下：

  1. 在C中记录A中各值元素的数目

    在这里插入图片描述

    for (int i = 0; i < len; i++) {
    count[arr[i]]++;
}

  2. 将count[i]转换成小于等于i的元素个数

    在这里插入图片描述

    for (int i = 1; i < max + 1; i++) {
    count[i] += count[i-1];
}

  3. 为A数组从后向前的每个元素找到对应的B中的位置。每次从A中复制一个元素到B中，C中相应的数-1。

    在这里插入图片描述

    for (int i = len - 1; i >= 0; i--) {
    int n = count[arr[i]];
    b[n - 1] = arr[i];
    count[arr[i]]--;
}

  4. 当A中的元素都复制到B中后，B就是排好序的结果。然后再将结果赋值给A。

    在这里插入图片描述

下面为完整代码

public void countSort(int[] arr) {
    int len = arr.length;
    int max = arr[0];
    for(int i = 1; i < len; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }
    }
    int[] count = new int[max + 1];//以数据的范围作为计数数组的大小
    int[] b = new int[len];
    for (int i = 0; i < len; i++) {
        count[arr[i]]++;
    }
    for (int i = 1; i < max + 1; i++) {
        count[i] += count[i-1];
    }
    for (int i = len - 1; i >= 0; i--) {
        int n = count[arr[i]];
        b[n - 1] = arr[i];
        count[arr[i]]--;
    }
    for (int i = 0; i < len; i++) {
        arr[i] = b[i];
    }
}

需要注意的是,出现多个元素相同的情况时，每当arr[i]放入b中，count[arr[i]]都要减一，这样，下一个与arr[i]相等的元素出现的时候，被放在arr[i]的前面，从而保证了数组的稳定性。

总结：

  1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
  2. 时间复杂度：O(N)
  3. 空间复杂度：O(N)
  4. 稳定。

计数排序还有另外一种做法：只需要一个待排数组和一个计数数组就能做。

大体思路就是：

  1. 找出待排序元素中的最大值和最小值，确定待排序元素的数据范围，然后根据范围确定计数数组的大小。

    int min = arr[0];
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
    if(arr[i] < min) {
        min = arr[i];
    }
    if (arr[i] > max) {
        max = arr[i];
    }
}
int len = max - min + 1;
int[] count = new int[len];

  2. 遍历arr数组，记录每个待排序元素出现的次数。这里要注意的是，怎么将count数组下标和arr[i]的之联系起来。

    举个例子：

    arr = [91,92,99,92,93,92,99,98，94], max = 99, min = 91

    我们应该这样进行计数：

    在这里插入图片描述

    我现在要记录91出现的次数，91应该放在计数数组的0下标，也就是count[0]，91 - min = 0，所以我们可以推出来一个等式，设count下标为n，设当前待排序元素的数值为val，n + min = val

    for (int i = 0; i < arr.length; i++) {
    count[arr[i] - min]++;
}

  3. 上述循环走完，计数数组已经存好了对应关系，遍历计数数组，给arr数组重新赋值。

    int k = 0;
for (int i = 0; i < len; i++) {
    int n = count[i];//记录元素出现的次数
    while (n != 0) {
        arr[k++] = i + min;//运用等式关系
        n--;
    }
}

下面为完整代码：

public static void countArray(int[] arr) {
    int min = arr[0];
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if(arr[i] < min) {
            min = arr[i];
        }
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int len = max - min + 1;
    int[] count = new int[len];
    for (int i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }
    int k = 0;
    for (int i = 0; i < len; i++) {
        int n = count[i];
        while (n != 0) {
            arr[k++] = i + min;
            n--;
        }
    }
}

这个方法写出来的排序不一定是稳定的，但是计数排序一定是稳定的。

5.2 桶排序

桶排序的思想就是：划分成多个范围相同的区间，将待排序元素放入对应的区间，每个区间内部进行排序，最后合并。

桶排序可以看成计数排序的扩展版本，计数排序可以看作每个桶放相同的元素，而桶排序中每个桶储存一定范围内的元素。

在这里插入图片描述

知道了思想，我们就可以写出相应代码：

  1. 得出最大值和最小值。

    int max = arr[0];
int min = arr[0];
for(int i = 1; i < arr.length; i++){
    max = Math.max(max, arr[i]);
    min = Math.min(min, arr[i]);
}

  2. 计算桶的数量，桶可以用ArrayList来表示。

    int count = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(count);
for(int i = 0; i < count; i++){
    bucketArr.add(new ArrayList<>());//分配内存
}

  3. 将每个元素放入相应桶内

    for(int i = 0; i < arr.length; i++){
    int num = (arr[i] - min) / (arr.length);
    bucketArr.get(num).add(arr[i]);
}

  4. 对每个桶进行排序

    for(int i = 0; i < bucketArr.size(); i++){
    Collections.sort(bucketArr.get(i));
    //这个方法是专门对实现List接口的数据结构进行排序
}

  5. 将桶中的元素赋值给原数组

    int index = 0;
for(int i = 0; i < bucketArr.size(); i++){
    for(int j = 0; j < bucketArr.get(i).size(); j++){
        arr[index++] = bucketArr.get(i).get(j);
    }
}

完整代码：

public static void bucketSort(int[] arr){
    int max = arr[0];
    int min = arr[0];
    for(int i = 1; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    int count = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(count);
    for(int i = 0; i < count; i++){
        bucketArr.add(new ArrayList<>());//分配内存
    }

    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }

    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
        //这个方法是专门对实现List接口的数据结构进行排序
    }

    int index = 0;
    for(int i = 0; i < bucketArr.size(); i++){
        for(int j = 0; j < bucketArr.get(i).size(); j++){
            arr[index++] = bucketArr.get(i).get(j);
        }
    }
}

总结

  1. 时间复杂度：O(N*(log(N/M)+1))

    设数组元素有N个，桶有M个，平均每个桶有N/M个元素。

    主要步骤有

    • 每个元素放入桶中O(N)
    • 对每个桶进行排序，一共有M次，每次复杂度为O((N/M)*log(N/M))，所以为O(M*(N/M)*log(N/M))

    O(N) + O(M*(N/M)*log(N/M)) = O(N*(log(N/M)+1))

    当N == M时，复杂度为O(N)

  2. 空间复杂度：O(M + N)

  3. 稳定性：取决于桶内排序的算法

5.3 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序也运用到了桶，根据元素的每位数字来分配桶

img

下面是具体步骤：

  1. 获得待排序元素中，最大元素的位数

    int maxDigit = getMaxDigit(arr);
private static int getMaxDigit(int[] arr) {
    int maxValue = getMaxValue(arr);//获取最大元素
    return getNumLength(maxValue);//获取最高位数
}
private static int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    return maxValue;
}
private static int getNumLength(long num) {
    if (num == 0) {
        return 1;
    }
    int length = 0;
    for (long temp = num; temp != 0; temp /= 10) {
        length++;
    }
    return length;
}

  2. 根据元素的每一位数字，对其进行排序。

    1.怎么遍历元素的每一位数字呢？

    我们可以创建一个循环，循环的次数是最大位数，在每一次循环中遍历元素的每位数字。

    2.那如何得到元素的每位数字呢？

    举个例子，假如我们要得到361这个数字的个位数字1，先%10，得到1，再/1；要得到十位数字6，先%100，得到61，再/10，得到6；要得到百位数字3，先%1000，得到361，再/100，得到3。

    发现规律了吗？随着位数从个位到百位，我们%的数字和/的数字也以10倍增长，这样我们便可以利用循环，在每次循环中，对此进行*10操作。

    3.现在我们得到了每位数字，如何对他进行排序呢？

    就如同上面的动图，我们可以创建一个二维数组arr[10][]，分别对应0~9，然后把相应的数字放入数组中，然后再从arr[0][]开始，将数组中的元素一个个放回到原数组，就完成了本轮排序。

    现在我们把比较重要的3步都已经理解清楚了，下面就是实现代码：

    private static int[] sort(int[] arr, int maxDigit) {
    int mod = 10;
    int dev = 1;

    for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        int[][] counter = new int[20][0];
        //这里设定成20，是因为考虑到了负数，[0,10)存储负数，[10,20)存储正数
        for (int j = 0; j < arr.length; j++) {
            int bucket = ((arr[j] % mod) / dev) + 10;
            //(arr[j] % mod) / dev：得到每位数字
            //+10是因为考虑了负数，比如说得到的该位数字为-1，就把他存储到arr[9]中。
            counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            //给数组扩容，因为一开始创建没有分配内存。然后添加元素
        }
        int pos = 0;
        for (int[] bucket : counter) {
            for (int value : bucket) {
                arr[pos++] = value;//重新赋值
            }
        }
    }
    return arr;
}
private static int[] arrayAppend(int[] arr, int value) {
    arr = Arrays.copyOf(arr, arr.length + 1);
    arr[arr.length - 1] = value;
    return arr;
}

完整代码如下：


	public static void radixSort (int[] arr){
	   int maxDigit = getMaxDigit(arr);
	    sort(arr, maxDigit);
	}
	
	private static int getMaxDigit(int[] arr) {
	    int maxValue = getMaxValue(arr);
	    return getNumLength(maxValue);
	}
	
	private static int getMaxValue(int[] arr) {
	    int maxValue = arr[0];
	    for (int value : arr) {
	        if (maxValue < value) {
	            maxValue = value;
	        }
	    }
	    return maxValue;
	}
	
	protected static int getNumLength(long num) {
	    if (num == 0) {
	        return 1;
	    }
	    int length = 0;
	    for (long temp = num; temp != 0; temp /= 10) {
	        length++;
	    }
	    return length;
	}
	
	private static int[] arrayAppend(int[] arr, int value) {
	    arr = Arrays.copyOf(arr, arr.length + 1);
	    arr[arr.length - 1] = value;
	    return arr;
	}
	
	private static int[] sort(int[] arr, int maxDigit) {
	    int mod = 10;
	    int dev = 1;
	
	    for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
	        int[][] counter = new int[20][0];
	        for (int j = 0; j < arr.length; j++) {
	            int bucket = ((arr[j] % mod) / dev) + 10;
	            counter[bucket] = arrayAppend(counter[bucket], arr[j]);
	        }
	        int pos = 0;
	        for (int[] bucket : counter) {
	            for (int value : bucket) {
	                arr[pos++] = value;//重新赋值
	            }
	        }
	    }
	    return arr;
	}

总结

  1. 时间复杂度：O(k*N)

    设最大位数为k位

    外层循环O(k)，内层循环O(N)，整体是O(k*N)

  2. 空间复杂度：O(N)

  3. 稳定性：稳定

十大排序算法已经全部更新完啦！?累鼠了累鼠了?

如果想了解其他的排序算法，可以移步到我的前两篇文章呦

  1. 十大排序算法（上）直接插入排序、希尔排序、直接选择排序、堆排序
  2. 十大排序算法（中）：冒泡排序，快速排序（递归和非递归）、归并排序（递归和非递归）

如果有什么疑问，欢迎在评论区给我留言，或者是私信我~

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐