内部排序算法学习总结

《内部排序算法学习总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SortingalgorithmSortingbyCounting通过计数的方式来排序ComparisonCounting假设对A[1...N]数组进行排序，用一个数组count[1...N]来统计每个数应该出现的位置，1Setcount[1...N]=0;2fori=N;i>1;i--2forj=i-1;j>=1;j--;ifA[j]>A[i]count[j]++;elsecount[i]++;例如对于数组23415第一次统计后count为：00004第二次统计后count为：11104第三次统计后count为：11304第四次统计

2、后count为：12304最后的count则对应了其出现的下标值显然该算法时间复杂度为O(n^2）空间复杂度为O(n)，很烂的算法，没啥用处，不过不需要移动记录DistributionCounting该方法是对上面方法的改进，假设数组A的最大值和最小值分别为minmax，设置一个count[min...max]数组来统计每个数应该出现的位置1Setcount[min...max]=0;2for(i=1;i<=N;i++)count[A[i]+=1;3for(i=min+1;i<=max;i++)count[i]=count[i]+co

3、unt[i-1];该方法不需要进行任何比较操作，有点像后面要提到的RadixSortingSortingbyInsertion插入排序，该算法的基本思想和我们打扑克牌的时候插牌的方法类似，当我们要接到第i个牌的时候，我们手上的i-1个牌已经是有序的了，那么我们找到合适的位置，把第i张牌插进去。Straightinsertion直接插入for(i=2;i<=N;i++)pivote=A[i];for(j=i-1;j>=1;j--)if(A[j]>A[i])A[j+1]=A[j];elsebreak;A[j+1]=pivote;该算法最坏

4、情况就是输入数组为逆序的情况，则比较和移动的次数为1+2+...+N-1=N*(N-1)/2O(n^2)平均下来，对于i，每次比较和移动次数为i/2，则总的次数为N*(N-1)/4约为(N^2)/4该算法在N不是很大，且数组基本有序的情况下，可以获得最好的效率，因此很多排序算法在对数据进行部分排序时，通常使用该算法。BinaryInsertionandtwo-wayInsertion对于第i个数，因为前i-1个数都是有序的了，我们需要找到合适的位置来将i插入进去，因此我们可以使用二分查找的方式在i-1中寻找合适的位置，例如对于i=64

5、，则比较A[32]，如果大于A[64]则比较A[16]否则比较A[48]，这样查找相应的插入位置只需要log2N次比较。但是即使我们找到了合适的插入位置，我们仍然需要将后面的记录往后挪一个位置，来腾出空间给要插入的数A[i]，因此总的时间复杂度并没有降低。ShellSorting希尔排序如果某个排序算法，一次只移动一个位置的话，那么其时间复杂度是O(n)，因此如果我们要提高效率的话，那么每次比较不能只是移动一个位置，而应该移动尽可能多的位置。希尔排序就是这样的算法，也称为Diminishingincrementsortion例如对于1

6、6条记录，我们将其分为8组(A1,A9)(A2,A10)...(A8,A16)分别对每一组进行排序之后分为4组（A1,A5,A9,A13)...(A4,A8,A12,A16)分别对每一组进行排序然后分为2组，分别对每一组排序最后对整个数组排序对于每一个小组的排序可以使用直接插入排序。对于组的选取可以根据数据的不同来选取，但是最后一定是1，例如此处是8421当然也可以划分为7531等等。//histhegroupnumberShellSort(arrayA,intN,inth){for(i=1;i

7、;j+=h)pivote=A[j];for(k=j-h;k>0;k-=h)if(A[k]>A[j])A[k+h]=A[k];elsebreak;A[k+h]=pivote;}//assumearrayhstoresthegroupnumberShell(arrayA,intN,arrayh,intg_num){for(i=1;i<=g_num;i++)ShellSort(A,N,h[i]);}shell排序最关键的就是分组数目的选取，我们可以想象，当分组为N的时候，该算法就退化成了直接插入排序算法。理论上证明当数组hi=2^i-1的时

8、候，算法时间为N^(3/2)SortingbyExchanging交换排序的基本思想是交互一对outoforder的数，直到待排序列中没有outoforder的对为止直接插入排序也可以看成是交换排序：对于A[i]每次和它