《算法导论(第三版)》第八章8.2，计数排序

Zedd

《算法导论(第三版)》第八章8.2，计数排序
. C5 G' `$ j& W6 Q& j由于MATLAB本身语法的限制，MATLAB不存在A(0)这种操作，所以区别于书中的范围规定，修改为：
计数排序假设n个输入元素中的每一个都是在1~k区间内的一个整数，其中k为某个整数
* P, H1 {$ C5 O+ lmain
9 \; c  ?; y0 }/ a7 g9 W. n# a% e

• clear;clc
• A=[2 5 3 1 2 3 1 3]%测试数组，必须全部为正整数
• k=5;%MAX(A)
• A=COUNTING_SORT(A,k)
  - t9 P& t1 o9 b; j+ p0 M

( M4 A7 n" K+ j; k) u6 i3 @3 o6 l
" w1 [- T. F) m+ E0 F$ R
& `+ j7 C  ]9 T/ iCOUNTING_SORT
4 |# R& ~, i, d  {- P7 k) r9 B

• function [B] = COUNTING_SORT(A,k)%不需要存放的输出B
• %由于MATLAB不存在C(0)这种操作，所以书中的算法，需要调整为：
• %计数排序假设n个输入元素中的每一个都是在1~k区间内的一个整数，其中k为某个整数。
• C=zeros(1,k);%初始A中的相同元素个数为0
• for j=1:length(A)
•     C(A(j))=C(A(j))+1;%计算A中相同元素的个数
• end
• for i=2:k
•     C(i)=C(i)+C(i-1);%个数累加，为了区分相同个数，在不同的位置
• end
• for j=length(A):-1:1
•     B(C(A(j)))=A(j);%从后到前挨个存入输出中
•     C(A(j))=C(A(j))-1;%相同元素计数-1
• end
• end
  

  I, `1 y. Y; T5 q3 o1 g

wu68aq

学习一下计数排序，非常感谢楼主分享。