算法

　　目录汇总
　　序号
　　排序算法
　　平均时间
　　最好情况
　　最差情况
　　稳定度
　　额外空间
　　备注
　　相对时间
　　1hr冒泡算法
　　O（n2）
　　O（n）
　　O（n2）
　　稳定
　　O（1）
　　n越小越好
　　182ms
　　2hr选择算法
　　O（n2）
　　O（n2）
　　O（n2）
　　不稳定
　　O（1）
　　n越小越好
　　53ms
　　3hr插入算法
　　O（n2）
　　O（n）
　　O（n2）
　　稳定
　　O（1）
　　大部分排序好时好
　　16ms
　　4hr快速算法
　　O（nlog2n）
　　O（nlog2n）
　　O（n2）
　　不稳定
　　O（nlog2n）
　　n大时好
　　719ms
　　5hr归并算法
　　O（nlog2n）
　　O（nlog2n）
　　O（nlog2n）
　　稳定
　　O（n）
　　n大时好
　　550ms
　　6hr希尔算法
　　O（nlog2n）
　　O（n）
　　O（n2）
　　不稳定
　　O（1）
　　197ms4ms
　　7hr堆排序
　　O（nlog2n）
　　O（nlog2n）
　　O（nlog2n）
　　不稳定
　　O（1）
　　n大时好
　　3ms
　　8hr计数排序
　　O（nk）
　　O（nk）
　　O（nk）
　　稳定
　　O（nk）
　　k是桶的数量
　　2ms
　　9hr桶排序
　　O（nk）
　　O（n）
　　O（n2）
　　稳定
　　O（nk）
　　11ms
　　10hr基数排序
　　O（nk）
　　O（nk）
　　O（nk）
　　稳定
　　O（nk）
　　4ms
　　11hr优先队列
　　不稳定
　　O（n）
　　9ms
　　12hrJavaAPI
　　O（1）
　　4ms1。冒泡排序
　　每轮循环确定最值；publicvoidbubbleSort（int〔〕nums）｛booleanisS优化，发现排序好就退出for（inti0；inums。length1；i）｛for（intj0；jnums。length1i；j）｛每次排序后能确定较大值if（nums〔j〕nums〔j1〕）｛isStempnums〔j〕；nums〔j〕nums〔j1〕；nums〔j1〕｝｝if（！isSort）｛｝else｛isS｝｝｝2。选择排序
　　每次选出最值，再交换到边上；publicvoidselectSort（int〔〕nums）｛for（inti0；inums。length1；i）｛intminNumnums〔i〕；for（intji1；jnums。j）｛if（nums〔j〕minNum）｛minNumnums〔j〕；｝｝if（index！i）｛nums〔index〕nums〔i〕；nums〔i〕minN｝｝｝3。插入排序
　　对循环的每个数找到属于自己的位置插入；publicvoidinsertionSort（int〔〕nums）｛for（inti1；inums。i）｛intinsertNumnums〔i〕；while（j10nums〔j1〕insertNum）｛nums〔j〕nums〔j1〕；j；｝nums〔j〕insertN｝｝4。快速排序
　　选一个基本值，小于它的放一边，大于它的放另一边；publicvoidquickSortDfs（int〔〕nums，intleft，intright）｛if（leftright）｛｝intbaseNumnums〔left〕；while（lr）｛必须右边先走while（nums〔r〕baseNumlr）｛r；｝while（nums〔l〕baseNumlr）｛l；｝inttempnums〔l〕；nums〔l〕nums〔r〕；nums〔r〕｝nums〔left〕nums〔l〕；nums〔l〕baseNquickSortDfs（nums，left，r1）；quickSortDfs（nums，l1，right）；｝5。归并排序
　　分治算法；归publicvoidmergeSortDfs（int〔〕nums，intl，intr）｛if（lr）｛｝intm（lr）2；mergeSortDfs（nums，l，m）；mergeSortDfs（nums，m1，r）；merge（nums，l，m，r）；｝并privatevoidmerge（int〔〕nums，intleft，intmid，intright）｛int〔〕tempnewint〔rightleft1〕；intmmid1；inti0；while（lmidmright）｛if（nums〔l〕nums〔m〕）｛temp〔i〕nums〔l〕；｝else｛temp〔i〕nums〔m〕；｝｝while（lmid）｛temp〔i〕nums〔l〕；｝while（mright）｛temp〔i〕nums〔m〕；｝System。arraycopy（temp，0，nums，left，temp。length）；｝6。希尔排序
　　引入步长减少数字交换次数提高效率；6。1希尔冒泡排序（慢）publicvoidshellBubbleSort（int〔〕nums）｛for（intstepnums。length2；step0；step2）｛for（inums。i）｛for（j0；jstep）｛if（nums〔j〕nums〔jstep〕）｛inttempnums〔j〕；nums〔j〕nums〔jstep〕；nums〔jstep〕｝｝｝｝｝6。2希尔插入排序（快）publicvoidshellInsertSort（int〔〕nums）｛for（intstepnums。length2；step0；step2）｛for（inums。i）｛intinsertNumnums〔i〕；while（jstep0nums〔jstep〕insertNum）｛nums〔j〕nums〔jstep〕；｝nums〔j〕insertN｝｝｝7。堆排序
　　大顶堆实现升序，每次将最大值移到堆的最后一个位置上；publicvoidheapSort2（int〔〕nums）｛for（intinums。length21；i0；i）｛sift（nums，i，nums。length）；｝for（intinums。length1；i0；i）｛inttempnums〔0〕；nums〔0〕nums〔i〕；nums〔i〕sift（nums，0，i）；｝｝privatevoidsift（int〔〕nums，intparent，intlen）｛intvaluenums〔parent〕；for（intchild2parent1；childchild21）｛if（child1lennums〔child1〕nums〔child〕）｛｝if（nums〔child〕value）｛nums〔parent〕nums〔child〕；｝else｛｝｝nums〔parent〕｝8。计数排序
　　按顺序统计每个数出现次数；publicvoidcountSort（int〔〕nums）｛intmaxInteger。MINVALUE；intminInteger。MAXVALUE；for（intnum：nums）｛maxMath。max（max，num）；minMath。min（min，num）；｝int〔〕countMapnewint〔maxmin1〕；for（intnum：nums）｛countMap〔nummin〕；｝inti0；intj0；while（inums。lengthjcountMap。length）｛if（countMap〔j〕0）｛nums〔i〕i；countMap〔j〕；｝else｛j；｝｝｝9。桶排序
　　类似计数排序，不同点在于统计的是某个区间（桶）里的数；publicvoidbucketSort（int〔〕nums）｛intmaxInteger。MINVALUE；intminInteger。MAXVALUE；for（intnum：nums）｛maxMath。max（max，num）；minMath。min（min，num）；｝intbucketCount（maxmin）nums。length1；ListListIntegerbucketListnewArrayList（）；for（inti0；ibucketCi）｛bucketList。add（newArrayList（））；｝for（intnum：nums）｛intindex（nummin）nums。bucketList。get（index）。add（num）；｝for（ListIntegerbucket：bucketList）｛Collections。sort（bucket）；｝intj0；for（ListIntegerbucket：bucketList）｛for（intnum：bucket）｛nums〔j〕j；｝｝｝10。基数排序
　　按个、十、百位依次归类排序；publicvoidradixSort（int〔〕nums）｛intminInteger。MAXVALUE；intmaxInteger。MINVALUE；for（intnum：nums）｛minMath。min（min，num）；maxMath。max（max，num）；｝for（inti0；inums。i）｛nums〔i〕｝intmaxLen（max）。length（）；int〔〕〔〕bucketnewint〔nums。length〕〔10〕；int〔〕bucketCountnewint〔10〕；for（inti0，n1；imaxLi，n10）｛for（intnum：nums）｛intdigitValnumn10；bucket〔bucketCount〔digitVal〕〕〔digitVal〕bucketCount〔digitVal〕；｝intindex0；for（intj0；jbucketCount。j）｛if（bucketCount〔j〕0）｛for（intk0；kbucketCount〔j〕；k）｛nums〔index〕bucket〔k〕〔j〕；｝｝bucketCount〔j〕0；｝｝for（inti0；inums。i）｛nums〔i〕｝｝11。使用集合或API11。1优先队列publicvoidpriorityQueueSort（int〔〕nums）｛PriorityQueueIntegerqueuenewPriorityQueue（）；for（intnum：nums）｛queue。offer（num）；｝for（inti0；inums。i）｛nums〔i〕queue。poll（）；｝｝11。2JavaAPIpublicvoidarraysApiSort（int〔〕nums）｛Arrays。sort（nums）；｝