【推荐】几种常用排序的代码.docxVIP

1. 桶排序（1）. 实现思路（2）. 复杂度与稳定性时间复杂度： O(n)空间复杂度：O(k)稳定性：稳定（3）. 代码实现2. 冒泡排序（4）. 实现思路（5）. 复杂度与稳定性时间复杂度：最差、平均都是O(n2)，最好是O(n)空间复杂度：1稳定性：稳定（6）. 代码实现3. 鸡尾酒排序CocktailSort（7）. 实现思路鸡尾酒排序（改进的冒泡排序），原理是对要排序的数组进行双向冒泡排序，双向冒泡排序又称为鸡尾酒排序。（8）. 复杂度与稳定性同冒泡排序（9）. 代码实现1. #include using namespace std;/*/鸡尾酒排序/双向冒泡排序（改进的冒泡排序）void CocktailSort(int *a,int nsize) int tail=nsize-1; for (int i=0;ii;-j) /第一轮，先将最小的数据排到前面 if (ajaj-1) int temp=aj; aj=aj-1; aj-1=temp; +i;/原来i处数据已排好序，加12. for (j=i;jaj+1) int temp=aj; aj=aj+1; aj+1=temp; 3. tail-;/原tail处数据也已排好序，将其减1 void OutPut(int *b,int nLength) for (int i=0;inLength;i+) coutbit; coutendl;int main() int nData=1,4,2,5,67,86,24,63,676,23,1,3,2,34;4. CocktailSort(nData,sizeof(nData)/sizeof(nData0); OutPut(nData,sizeof(nData)/sizeof(nData0); return 1;4. 插入排序（10）. 实现思路插入排序就是先是一个有序的数据，然后把要插入的数据插到指定的位置，而排序首先给的就是无序的，我们怎么确定先得到一个有序的数据呢？答案就是：如果只有一个，当然是有序的咯。我们先拿一个出来，他是有序的，然后把数据一个一个插入到其中，那么插入之后是有序的，所以直到最后都是有序的。哈哈。结果就出来了！当然在写的时候还是有一个技巧的，不需要开额外的数组，下标从第二个元素开始遍历知道最后一个，然后插入到前面已经有序的数据中。这样就不会浪费空间了。插入排序用处还是很多的，特别是链表中，因为链表是指针存放的，没有数组那么好准确的用下标表示，插入是简单有效的方法。嘻嘻。（11）. 复杂度与稳定性最差和平均时间复杂度：O(n2)，最好是O(n)空间复杂度：O(1) (用于记录需要插入的数据)稳定性：稳定（12）. 代码实现A. 从前向后查找的插入排序：cppview plaincopy5. /*6. *函数名称：InsertSort7. *参数说明：pDataArray无序数组；8. *iDataNum为无序数据个数9. *说明：插入排序10. */11. voidInsertSort(int*pDataArray,intiDataNum)12. 13. for(inti=1;iiDataNum;i+)/从第2个数据开始插入14. 15. intj=0;16. while(ji&pDataArrayj=pDataArrayi)/寻找插入的位置17. j+;18. 19. if(jj)/挪动位置24. 25. pDataArrayk=pDataArrayk-1;26. k-;27. 28. pDataArrayk=temp;/插入29. 30. 31. B. 从后面查找插入但楼主发现从后面查找插入的方式，代码复杂程度较低：cppview plaincopy1. /*2. *函数名称：InsertSort3. *参数说明：pDataArray无序数组；4. *iDataNum为无序数据个数5. *说明：插入排序6. */7. voidInsertSort(int*pDataArray,intiDataNum)8. 9. for(inti=1;i=0&pDataArrayjtemp)/从后向前，找到比其小的数的位置14. 15. pDataArrayj+1=pDataArrayj;/向后挪动16. j-;17. 18. 19. if(j!=i-1)/存在比其小的数20. pDataArrayj+1=temp;21. 22. C. 采用二分查找方法来寻找插入位置插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程；寻找插入位置采用顺序查找的方式（从前向后或者从后向前），既然需要插入的数组已经是有序的，那么可以采用二分查找方法来寻找插入位置，提高算法效率，但算法的时间复杂度仍为O(n2)。cppview plaincopy1. /查找数值iData在长度为iLen的pDataArray数组中的插入位置2. intFindInsertIndex(int*pDataArray,intiLen,intiData)3. 4. intiBegin=0;5. intiEnd=iLen-1;6. intindex=-1;/记录插入位置7. while(iBeginiData)11. iEnd=index-1;12. else13. iBegin=index+1;14. 15. if(pDataArrayindex=iData)16. index+;17. returnindex;18. 19. 20. /*21. *函数名称：BinaryInsertSort22. *参数说明：pDataArray无序数组；23. *iDataNum为无序数据个数24. *说明：二分查找插入排序25. */26. voidBinaryInsertSort(int*pDataArray,intiDataNum)27. 28. for(inti=1;iindex)/挪动位置37. 38. pDataArrayj=pDataArrayj-1;39. j-;40. 41. pDataArrayj=temp;/插入42. 43. 44. 5. 归并排序（13）. 实现思路归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。（14）. 复杂度和稳定性时间复杂度：O(N*logN)空间复杂度：O(N)稳定性：稳定（15）. 代码实现cppview plaincopy1. /将有序数组a和b合并到c中2. voidMemeryArray(inta,intn,intb,intm,intc)3. 4. inti,j,k;5. i=j=k=0;6. while(in&jm)7. 8. if(aibj)9. ck+=ai+;10. else11. ck+=bj+;12. 13. 14. while(in)15. ck+=ai+;16. 17. while(jm)18. ck+=bj+;19. 可以看出合并有序数列的效率是比较高的，可以达到O(n)。解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。cppview plaincopy1. /将有二个有序数列afirst.mid和amid.last合并。2. voidmergearray(inta,intfirst,intmid,intlast,inttemp)3. 4. inti=first,j=mid+1;5. intm=mid,n=last;6. intk=0;7. 8. while(i=m&j=n)9. 10. if(ai=aj)11. tempk+=ai+;12. else13. tempk+=aj+;14. 15. 16. while(i=m)17. tempk+=ai+;18. 19. while(j=n)20. tempk+=aj+;21. 22. for(i=0;ik;i+)23. afirst+i=tempi;24. 25. voidmergesort(inta,intfirst,intlast,inttemp)26. 27. if(firstlast)28. 29. intmid=(first+last)/2;30. mergesort(a,first,mid,temp);/左边有序31. mergesort(a,mid+1,last,temp);/右边有序32. mergearray(a,first,mid,last,temp);/再将二个有序数列合并33. 34. 35. 36. boolMergeSort(inta,intn)37. 38. int*p=newintn;39. if(p=NULL)40. returnfalse;41. mergesort(a,0,n-1,p);42. deletep;43. returntrue;44. 归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。6. 选择排序（16）. 实现思路选择排序和冒泡排序思路上有一点相似，都是先确定最小元素，再确定第二笑元素，最后确定最大元素。他的主要流程如下：1.加入一个数组A=5,3,6,2,4,7，我们对他进行排序2.确定最小的元素放在A0位置，我们怎么确定呢，首先默认最小元素为5,他的索引为0,然后用它跟3比较，比他打，则认为最小元素为3,他的索引为1，然后用3跟6比，发现比他小，最小元素还是3，然后跟2比，最小元素变成了2，索引为3，然后跟4比，跟7比。当比较结束之后，最小元素也尘埃落定了。就是2，索引为3，然后我们把他放在A0处。为了使A0原有数据部丢失，我们使A0(要放的位置)与A3（最小数据的位置）交换。这样就不可以了吗？3.然后我们在来找第二小元素，放在A1，第三小元素，放在A2。当寻找完毕，我们排序也就结束了。4.不过，在找的时候要注意其实位置，不能在找A2的时候，还用A2的数据跟已经排好的A0,A1比，一定要跟还没有确定位置的元素比。还有一个技巧就是我们不能每次都存元素值和索引，我们只存索引就可以了，通过索引就能找到元素了。呵呵。5.他和冒泡的相似和区别，冒泡和他最大的区别是他发现比他小就交换，把小的放上面，而选择是选择到最小的在直接放在确定的位置。选择是不稳定的排序。（17）. 复杂度与稳定性时间复杂度：都是O(n2)空间复杂度：O(1)稳定性：不稳定（18）. 代码实现32. #include#include/选择排序,pnData要排序的数据，nLen数据的个数intSelectSort(int*pnData,intnLen)/i从0,nLen-1)开始选择，确定第i个元素for(inti=0;inLen-1;+i)intnIndex=i;/遍历剩余数据，选择出当前最小的数据for(intj=i+1;jnLen;+j)if(pnDatajpnDatanIndex)nIndex=j;/如果当前最小数据索引不是i，也就