鱼C论坛

 找回密码
 立即注册
查看: 2194|回复: 0

[学习笔记] 计算排序算法

[复制链接]
发表于 2018-10-18 21:03:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 影-死神 于 2018-10-18 21:03 编辑

一. 计数排序算法基本思路
                1. 遍历数组,找出最大值maxValue和最小值minValue,新建一个长度为maxValue-minValue+1的数组,并初始化为0
                2. 遍历数组,每个整数按照其值,对应新数组的下标(value-minvalue)加一
                3. 遍历新数组,每次输出新数组的下标值加minValue的值到原数组以更新原数组,对应的值是几就输出几次
        算法的时间复杂度:
                由于遍历了两遍原数组和一遍新数组,所以时间复杂度为 O(2N+M) = O(n)
        算法的空间复杂度:
                由于新建了一个数组,所以空间复杂度为 O(N+M) = O(n)
        Java代码实现:
  1. public class CountSort {
  2.         public static void sort(int[] array) {
  3.                 int minValue = array[0];
  4.                 int maxValue = array[0];
  5.                
  6.                 //遍历数组寻找最大值和最小值
  7.                 for (int i=1;i<array.length;i++) {
  8.                         if (array < minValue) {
  9.                                 minValue = array;
  10.                         }
  11.                         if (array > maxValue) {
  12.                                 maxValue = array;
  13.                         }
  14.                 }
  15.                
  16.                 //新的数组并计数
  17.                 int[] countList = new int[maxValue-minValue+1];
  18.                
  19.                 for (int i=0;i<array.length;i++) {
  20.                         countList[array-minValue]++;
  21.                 }
  22.                
  23.                 //输出到原数组
  24.                 int index = 0;
  25.                 for (int i=0;i<countList.length;i++) {
  26.                         for (int j=0;j<countList;j++) {
  27.                                 array[index] = minValue + i;
  28.                                 index++;
  29.                         }
  30.                 }
  31.         }
  32.       
  33.         public static void main(String[] args) {
  34.                 int[] list = {5, 8, 6, 3, 9, 2, 1, 7, 4};
  35.                
  36.                 sort(list);
  37.                
  38.                 for (int i=0;i<list.length;i++) {
  39.                         System.out.print(list + " ");
  40.                 }
  41.         }
  42. }
复制代码



二. 计数排序的适用场景
        由于计数排序是根据下标进行排序的所以只能排序整数,而如果最大值和最小值之间的差值太大时,又过于浪费内存空间,所以适用于一定范围内差值不太大的整数的排序,此时,排序速度甚至超过快速排序。

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 22:33

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表