阿包说算法之排序

　　排序的方法有很多，本文主要介绍三种：冒泡排序，快速排序，归并排序。在很多算法中，都会用到递归算法，因此递归不再单独讲。1。冒泡排序
　　算法思路
　　冒泡排序的思想是最符合常人思维的，比如一个数组：3，6，8，2，1。首先选择第一个数3，然后从后面的数开始遍历，如果比数组第一个数小，就交换位置，否则继续：比如，第一次比较3和6，3小，继续，3和8比，继续，3和2比，2小，就交换3和2的位置，数组变成2，6，8，3，1，这时数组第一个数是2，2和1比，1小，交换2和1的位置，变成1，6，8，3，2，此时第一轮遍历结束，可以看到一轮遍历可以把最小的数选出。
　　第二次从第2个数开始遍历，与后面的数比较，就是6依次和8，3比，跟3换位置，然后3和2比，又换位置，次轮结束后1，2，8，6，3。继续下一轮，直到遍历结束。可见第一次把最小的数放到第一位，第二次把第二小的数放到第二位，第N次把第N小的数放到第N位。voidBubbleSort（intarr，intcounts）｛inttmp0；for（inti0；icounts1；i）｛for（intji1；jcounts；j）｛如果后面的数比前面的小，就交换位置if（arr〔i〕arr〔j〕）｛tmparr〔i〕；arr〔i〕arr〔j〕；arr〔j〕tmp；｝｝｝｝intmain（）｛intarr〔〕｛7，3，8，2，9，6，0，2，4，7｝；BubbleSort（arr，10）；for（inti0；i10；i）coutarr〔i〕；return0；｝
　　最终输出
　　0223467789hr说明：冒泡排序的时间复杂度为O（N2），冒泡排序写法可能不一定是跟上面的一样，但是思想是一致的2。快速排序
　　算法思路
　　快速排序法的思想是把数组的第一个数取出来作为分界点，让数组中小于他的数放在他左边，大于他的数放在他右边，比如53974这组数字，选5为分界点，然后让34在5左边，97在5右边，变成34597然后，对左右两部分34和97，分别继续重复上面的步骤，直到有序。这里可以看出应该用到递归。
　　步骤如下，有一串数字3，6，8，2，7，首先把第一个数3取出来作为分界点，然后从最右边开始找小于3的数，7大于3跳过，继续看2，2小于3，就把2放到3的位置，2的位置空出来【2，6，8，，7】，再从左边开始，6大于3，就把6放到原来2的位置，6的位置空出来【2，，8，6，7】，再从右边8开始，8大于3跳过，下一个，是空了，则此轮结束，把3放到空位【2，3，8，6，7】。
　　然后对3左右两边的2和8，6，7分别按上面的步骤进行排序，就变成【2，3，6，7，8】voidFastSort（intarr，intcounts）｛if（counts1）return；intnumarr〔0〕；取数组的第一个数字作为分界点intnullPos0；空位在此intleft1，rightcounts1；左右开始的位置while（true）｛从右边开始找，直到有小于num的，或者遇到空位就结束while（right！nullPosarr〔right〕num）right；if（rightnullPos）结束了break；否则就是找到了小的arr〔nullPos〕arr〔right〕；nullPosright；再从左边找，左边的得大于num才挪while（left！nullPosarr〔left〕num）left；if（leftnullPos）结束了break；arr〔nullPos〕arr〔left〕；当前值放到空位nullPosleft；｝跳出了，把num放到空位arr〔nullPos〕num；if（nullPos0）有前半段FastSort（arr，nullPos）；前半段排序if（nullPoscounts1）有后半段FastSort（arrnullPos1，countsnullPos1）；后半段排序｝intmain（）｛intarr〔〕｛7，3，8，2，9，6，0，2，4，7｝；FastSort（arr，10）；for（inti0；i10；i）coutarr〔i〕；return0；｝
　　最终输出
　　0223467789hr说明：这种排序的方式是一种分治的思想，把大问题拆分成多个解法一样的小问题，这里是把大数组拆成前后2个解法一样的小数组，分成两部分的分治法又叫二分法，但是跟下面的二分法排序又不一样。
　　另外，快速排序代码会有多种不同的写法，但是思想是一致的，快速排序中有2个while，在极端情况下（比如数组是有序的，会遍历整个数组）的算法复杂度是O（N2），一般情况下是O（NlogN），但实际上乱序的情况下，很快就能跳出while，所以被称为快速排序，此排序最实用，请读者牢记。3。归并排序（二分法排序）
　　算法思路
　　归并排序思路是：将数组一分为二，再对分出来的2个子数组继续拆分，2分，拆分直到子数组只有一个数字，然后把所有的数字两两组合成有序小数组，最后合成一个完整数组，是典型的二分法，所以又叫做二分法排序
　　这里的思想是拆分后就变成有序数组（一个数字肯定有序），然后就是对有序数组的合并操作。比如83652，拆分成836，52，继续拆分成8，3，6，5，2。然后8和3组合成38，38和6组合成368，52组合成25，。最后把368和25组合成23568。voidMerge（intarr1，intcounts1，intarr2，intcounts2，intmerge）｛开始组合inti0，j0，pos0；较小的数给tmp，小的指针，tmp指针while（icounts1jcounts2）merge〔pos〕arr1〔i〕arr2〔j〕？arr1〔i〕：arr2〔j〕；跳出，如果某个数组还有，加到tmp后面while（icounts1）merge〔pos〕arr1〔i〕；while（jcounts2）merge〔pos〕arr2〔j〕；｝voidSort（intarr，intcounts，intout）｛if（counts1）返回条件｛out〔0〕arr〔0〕；return；｝intmidcounts2；中点作为拆分点intout1newint〔mid〕；intout2newint〔countsmid〕；Sort（arr，mid，out1）；左边排序Sort（arrmid，countsmid，out2）；右边排序Merge（out1，mid，out2，countsmid，out）；左右合并delete〔〕out1；delete〔〕out2；｝voidMergeSort（intarr，intcounts）｛intoutnewint〔counts〕；Sort（arr，counts，out）；for（inti0；icounts；i）arr〔i〕out〔i〕；delete〔〕out；｝intmain（）｛intarr〔〕｛7，3，8，2，9，6，0，2，4，7｝；MergeSort（arr，10）；for（inti0；i10；i）coutarr〔i〕；return0；｝
　　最终输出
　　0223467789hr说明：归并排序用的是二分法，把数组分成2个子数组分别排序，实际上可以用三分法四分法，把数组分成3个子数组，4个子数组等都可以，读者可以自行思考如何使用三分法归并排序。
　　归并排序的时间复杂度是O（NlogN）