计数排序算法,顾名思义就是通过计算数值出现的次数来进行排序。计数排序算法原理是这样的,计算数组中每个数值的出现次数来对数组进行排序,相同数值计数+1,计算的次数存储在辅助数组中,辅助数组的长度为初始数组的最大值+1,最后根据辅助数组的位数和每一位的数值来排序。
计数排序算法原理
指定数组[4,2,2,8,3,3,1],遍历数组找到最大值是8,则辅助数组的长度为9。
辅助数组,如图:
开始遍历和统计初始数组每一位数值,
第0位数值是4,在辅助数组的第4位数值+1,此时第4位就是1;
第一位数值是2,在辅助数组的第2位数值+1;此时第2位就是1;
第二位数值是2,在辅助数组的第2位数值+1,此时第2位就是2;
第三位数值是8,在辅助数组的第8位数值+1,此时第8位就是1;
第四位数值是3,在辅助数组的第3位数值+1,此时第3位就是1;
第五位数值是3,在辅助数组的第3位数值+1,此时第3位就是2;
第六位数值是1,在辅助数组的第1位数值+1,此时第1位就是1;
辅助数组变成[0,1,2,2,1,0,0,0,1]
遍历辅助数组,输出每个数组的下标,每一位的数组是几,就输出几次。最终排序好的结果是0,1,2,2,3,3,4,8。