《数据结构之排序算法--C#实现(6页).docx》由会员分享，可在线阅读，更多相关《数据结构之排序算法--C#实现(6页).docx（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-数据结构之排序算法-C#实现-第 6 页更多信息请浏览数据结构之排序算法-C#实现原文出处：本文中介绍的排序方法主要有以下几种：冒泡排序、选择排序、插入排序、希尔排序、归并排序、堆排序、快速排序。排序算法之一：冒泡排序（Bubble Sort）冒泡排序算法是可用的最慢的排序算法之一，但是是最容易理解和实现的一种排序算法。这种排序的得名是由于数值像气泡“一样升至队列的顶端或者底端而得名，通过多次遍历整个列，并且比较相邻的数据，如果左边的数值大于右边的数值就进行交换（升序）。实现代码如下：1. /BubbleSortCode2. publicstaticvoidBubbleSort(intarr
2、)3. for(inti=0;iarr.Length;i+)4. for(intj=0;jarrj+1)6. inttemp=arrj;7. arrj=arrj+1;8. arrj+1=temp;排序算法之二：选择排序（Selection Sort)以数组为例（当然其他的集合类型也是一样），这种排序是从数组的起始处开始，把第一个元素与数组中其他元素进行比较。然后将最小的元素放在第0个位置，接着再从第一个位置开始再次进行排序操作。直到数组的最后一个元素为止。1. /SelectionSortCode2. publicstaticvoidSelectSort(intarr)3. intmin;4.
3、 for(inti=0;iarr.Length-1;i+)5. min=i;6. for(intj=i+1;jarrj)/若写成if(arriarrj)是错误的！注意！8. min=j;/保存最小数的下标9. if(min!=i)10. inttemp=arrmin;11. arrmin=arri;12. arri=temp;排序算法之三：插入排序（Insertion Sort）其基本操作为将一个记录插入到一个已经排序好的序列中，从而得到一个新的、记录数增1的新序列。如下图所示插入排序的过程：（图片源自网络）csharpview plaincopy1. /InsertionSortCode2.
4、 publicstaticvoidInsertionSort(intarr)3. intinner,temp;4. for(inti=1;i0&arrinner-1temp)8. arrinner=arrinner-1;9. inner-=1;10. arrinner=temp;总结：选择排序是如上三种排序算法中效率最高的一种，其次是冒泡和插入。如上三种排序算法对小型数据集合适用，若是大型数据集合，由于其性能瓶颈，最好选用其他高级排序算法。排序算法之四：希尔排序（Shells Sort）又称“缩小增量排序”（Diminshing Increment Sort）是一种对插入排序的改进算法。基本思
5、想为：设待排序记录序列有n个记录，首先取一个整数gap0)6. for(intouter=h;outerh-1)&arrinner-h=temp)10. arrinner=arrinner-h;11. inner-=h;12. arrinner=temp;13. Console.WriteLine();14. Console.WriteLine(h=+h.ToString();15. DisplayArray(arr);16. h=(h-1)%3;排序算法之五：归并排序算法（Merge Sort)归并排序法是将两个（或多个）有序集合合并成一个新的有序集合。即把待排序集合分为若干个子集合，对每个
6、集合进行排序，然后再把这些有序的子集合合并为整体集合。是分治法（Divide and COnquer)的典型应用。若将两个集合合并成一个集合称为2-路归并。百度百科关于归并排序算法的介绍，非常的详细，请参阅：本处以2-路归并算法为例给出C#源代码，供大家学习。csharpview plaincopy1. /MergeSortCode2. publicstaticvoidMergeSort(intarr)3. intarrLength1,arrLength2;4. arrLength1=arr.Length/2;5. if(arr.Length%2=0)6. arrLength2=arrLeng
7、th1;7. else8. arrLength2=arrLength1+1;9. intarr1=newintarrLength1;10. intarr2=newintarrLength2;11. Array.Copy(arr,0,arr1,0,arrLength1);12. Array.Copy(arr,arrLength1,arr2,0,arrLength2);13. Console.WriteLine(narr1BeforeSort:);14. DisplayArray(arr1);15. Console.WriteLine(narr2BeforeSort:);16. DisplayAr
8、ray(arr2);17. /应用冒泡排序法为其排序18. BubbleSort(arr1);19. BubbleSort(arr2);20. Console.WriteLine(narr1AfterSort:);21. DisplayArray(arr1);22. Console.WriteLine(narr2AfterSort:);23. DisplayArray(arr2);24. /合并操作arr作为目标数组25. intarrIndex=0;26. intarr1Index=0,arr2Index=0;27. while(arr1IndexarrLength1&arr2Indexar
9、rLength2)28. /选择较小项存入arr29. if(arr1arr1Indexarr2arr2Index)30. arrarrIndex=arr1arr1Index;31. arr1Index+;32. else33. arrarrIndex=arr2arr2Index;34. arr2Index+;35. arrIndex+;36. /对arr1或者arr2中的没有存入arr中的元素进行追加37. if(arr1Index!=arrLength1)38. while(arr1IndexarrLength1)39. arrarrIndex=arr1arr1Index;40. arrI
10、ndex+;41. arr1Index+;42. elseif(arr2Index!=arrLength2)43. while(arr2IndexarrLength2)44. arrarrIndex=arr2arr2Index;45. arrIndex+;46. arr2Index+;47. DisplayArray(arr);归并排序算法的时间复杂度为O(nlogn),空间复杂度为O(n).排序算法之六：堆排序（Heap Sort）首先介绍堆的概念，如果有一个关键字集合k0,k1,k2,.,kn-1,把其所有元素按完全二叉树的顺序存储在一个一维数组中，当且仅当ki=K2i并且ki=0;i-)
11、14. /交换首尾15. inttemp=arri;16. arri=arr0;17. arr0=temp;18. /调整除尾部之后的特定的堆19. Heap.MinHeapAdjust(arr,0,i);20. Heap.DisplayHeap(arr);21. Console.ReadLine();22. publicstaticclassHeap23. /24. /将传入的数组调节为最小堆25. /26. /待调解数组27. /待调节的最大索引，最大索引之后的数据将不会调节28. publicstaticvoidMinHeapAdjust(intarr,intstartIndex,int
12、maxIndex)29. /Console.WriteLine(BeforeAdjust);30. /DisplayHeap(arr);31. /首先需要获得倒数第一个分枝节点32. intcurrentBranchIndex=maxIndex/2-1;33. /调整分枝节点及其子节点34. for(;currentBranchIndex=startIndex;currentBranchIndex-)35. AdjustSubHeap(arr,currentBranchIndex,maxIndex);36. /Console.WriteLine(AfterAdjust);37. /Displa
13、yHeap(arr);38. /39. /FliterDown算法，调整以startIndex为要的子树为最小堆40. /41. /42. /43. /44. publicstaticvoidAdjustSubHeap(intarr,intcurrentIndex,intmaxIndex)45. vartemp=arrcurrentIndex;46. if(2*currentIndex+1arr2*currentIndex+1)48. arrcurrentIndex=arr2*currentIndex+1;49. arr2*currentIndex+1=temp;50. temp=arrcur
14、rentIndex;/若本子树顶部的键值已经改变，则将此键值存入临时区51. AdjustSubHeap(arr,2*currentIndex+1,maxIndex);52. if(2*currentIndex+2arr2*currentIndex+2)54. arrcurrentIndex=arr2*currentIndex+2;55. arr2*currentIndex+2=temp;56. AdjustSubHeap(arr,2*currentIndex+2,maxIndex);57. /58. /显示Heap59. /60. /61. publicstaticvoidDisplayHe
15、ap(intarr)62. foreach(intvalinarr)63. Console.WriteLine(val+);排序算法之七：快速排序（quick sort)快速排序也是分治法的一个实例，其主要思想为，选取一个值，将大于其的值放在其后，小于其的值放在其前。并对其前和其后的数据段进行迭代，直至分到数据段为一个数字。【它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。】（如上括号里面的为引用自别处，人家写的比俺写的好多了。
16、）其具体做法如下：设要排序的数组是A0AN-1，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。一趟快速排序的算法是：1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；2）以第一个数组元素作为关键数据，赋值给key，即key=A0；3）从J开始向前搜索，即由后开始向前搜索（J=J-1即J-），找到第一个小于key的值Aj，Aj与Ai交换；4）从I开始向后搜索，即由前开始向后搜索（I=I
17、+1即I+），找到第一个大于key的Ai，Ai与Aj交换；5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。）csharpview plaincopy1. /QuickSortCode2. usingSystem;3. usingSystem.Collections.Generic;4. usingSystem.Linq;5. usingSystem.Text;6. namespaceQuickSort7. classProgram8. s
18、taticvoidMain(stringargs)9. intarr=97,76,13,27,20,10,9,90,49,65;10. QuickSort.sort(arr,0,arr.Length-1);11. QuickSort.DisplayArr(arr,0,arr.Length);12. Console.ReadLine();13. publicstaticclassQuickSort14. publicstaticvoidsort(intarr,intlowIndex,intupperIndex)15. if(lowIndex=upperIndex)return;16. intke
19、y,i,j,temp;17. i=lowIndex;18. key=arrlowIndex;19. j=upperIndex;20. boolleftToRight=false;21. while(ij)22. /从右向左检索，查找右边第一个小于key的元素23. if(!leftToRight)24. if(arrjkey)35. temp=arri;36. arri=arrj;37. arrj=temp;38. j=upperIndex;39. leftToRight=false;40. else41. i+;42. if(lowIndexupperIndex)43. sort(arr,lowIndex,i-1);44. sort(arr,i+1,upperIndex);45. /输出数组46. publicstaticvoidDisplayArr(intarr,intlowindex,intupperindex)47. Console.WriteLine();48. for(inti=lowindex;i关键字可分解。2记录的关键字位数较少，如果密集更好3如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。