排序算法之计数排序

作者：屎壳郎 miaosg01@163.com

日期：July 2021

版次：初版

简介： 根据数据结构和排序目的不同，排序过程的处理手法也各异。有的场合只需知道数据的位置信息，那我们可以采用计数排序，用一个辅助表统计各项的位置信息，而不用移动数据。有时数据结构较大，移动数据的开销很大，这就很适合链接排序，加入一个地址链接，通过改变链接来排列数据，从而避免大量数据的移动。本文重点介绍了采用辅助表统计的计数排序和分布统计排序。

1.计数排序

??计数排序的基本思想很朴素，其原理是统计序列中比某项小（或大）的项的数量，从而确定该项在排序时（升序或降序）应该放置的位置。例：序列$(R_1,R_2,R_3,R_4,R_5)$，其值为$(1,3,5,4,2)$。如何确定$R_2(=3)$的位置呢？我们把$R_2(=3)$与$R$中其它项逐一比较，统计出比$R_2(=3)$小的项$(R_1(=1),R_5(=2))$共两项，故在升序排序中$R_2(=3)$应该排在$R_1,R_5$之后，居第三的位置。

??该算法需要一个与$R$相同容量辅助表$COUNT$来记录统计结果，还以上面$R$为例，首先以$R_5$为基准，与$R_4,R_3,R_2{R}_1$逐一比较，如果$R_5>R_j(j=4,3,2,1)$，则$COUNT[5]=COUNT[5]+1$；否则$COUNT[j]=COUNT[j]+1$。依次取 R 4 , R 3 , R 2 R_4,R_3,R_2