java shell算法_排序算法复习（Java实现）(三）：插入，冒泡，选择，Shell,快速排序...

冷不防 2022-11-11 14:47 45阅读 0赞

packagealgorithms;importjava.util.Arrays;/\*\*\*@authoryovn

\*\*/publicclassRadixSorter \{publicstaticbooleanUSE\_LINK=true;/\*\*\*

\*@paramkeys

\*@paramfrom

\*@paramlen

\*@paramradix  key's radix

\*@paramd      how many sub keys should one key divide to\*/publicvoidsort(int\[\] keys,intfrom ,intlen,intradix,intd)

\{if(USE\_LINK)

link\_radix\_sort(keys,from,len,radix,d);

\}else\{

array\_radix\_sort(keys,from,len,radix,d);

\}privatefinalvoidarray\_radix\_sort(int\[\] keys,intfrom,intlen,intradix,intd)

\{int\[\] temporary=newint\[len\];int\[\] count=newint\[radix\];intR=1;for(inti=0;i

System.arraycopy(keys, from, temporary,0, len);

Arrays.fill(count,0);for(intk=0;k

\{intsubkey=(temporary\[k\]/R)%radix;

count\[subkey\]++;

\}for(intj=1;j

count\[j\]=count\[j\]+count\[j-1\];

\}for(intm=len-1;m>=0;m--)

\{intsubkey=(temporary\[m\]/R)%radix;--count\[subkey\];

keys\[from+count\[subkey\]\]=temporary\[m\];

R\*=radix;

\}privatestaticclassLinkQueue

\{inthead=-1;inttail=-1;

\}privatefinalvoidlink\_radix\_sort(int\[\] keys,intfrom,intlen,intradix,intd) \{int\[\] nexts=newint\[len\];

LinkQueue\[\] queues=newLinkQueue\[radix\];for(inti=0;i

queues\[i\]=newLinkQueue();

\}for(inti=0;i

nexts\[i\]=i+1;

nexts\[len-1\]=-1;intfirst=0;for(inti=0;i

link\_radix\_sort\_distribute(keys,from,len,radix,i,nexts,queues,first);

first=link\_radix\_sort\_collect(keys,from,len,radix,i,nexts,queues);

\}int\[\] tmps=newint\[len\];intk=0;while(first!=-1)

tmps\[k++\]=keys\[from+first\];

first=nexts\[first\];

System.arraycopy(tmps,0, keys, from, len);

\}privatefinalvoidlink\_radix\_sort\_distribute(int\[\] keys,intfrom,intlen,intradix,intd,int\[\] nexts, LinkQueue\[\] queues,intfirst) \{for(inti=0;i

\{intval=keys\[from+first\];for(intj=0;j

val=val%radix;if(queues\[val\].head==-1)

queues\[val\].head=first;

\}else\{

nexts\[queues\[val\].tail\]=first;

queues\[val\].tail=first;

first=nexts\[first\];

\}privateintlink\_radix\_sort\_collect(int\[\] keys,intfrom,intlen,intradix,intd,int\[\] nexts, LinkQueue\[\] queues) \{intfirst=0;intlast=0;intfromQueue=0;for(;(fromQueue

first=queues\[fromQueue\].head;

last=queues\[fromQueue\].tail;while(fromQueue

fromQueue+=1;for(;(fromQueue

nexts\[last\]=queues\[fromQueue\].head;

last=queues\[fromQueue\].tail;

\}if(last!=-1)nexts\[last\]=-1;returnfirst;

\}/\*\*\*@paramargs\*/publicstaticvoidmain(String\[\] args) \{int\[\] a=\{1,4,8,3,2,9,5,0,7,6,9,10,9,135,14,15,11,222222222,1111111111,12,17,45,16\};

USE\_LINK=true;

RadixSorter sorter=newRadixSorter();

sorter.sort(a,0,a.length,10,10);for(inti=0;i

System.out.print(a\[i\]+",");