《数据结构之排序算法--C#实现.docx》由会员分享，可在线阅读，更多相关《数据结构之排序算法--C#实现.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、更多信息请浏览数据结构之排序算法-C#实现原文出处：本文中介绍的排序方法主要有以下几种：冒泡排序、选择排序、插入排序、希尔排序、归并排序、堆排序、快速排序。排序算法之一：冒泡排序（Bubble Sort）冒泡排序算法是可用的最慢的排序算法之一，但是是最容易理解和实现的一种排序算法。这种排序的得名是由于数值像气泡“一样升至队列的顶端或者底端而得名，通过多次遍历整个列，并且比较相邻的数据，如果左边的数值大于右边的数值就进行交换（升序）。实现代码如下：1. /BubbleSortCode2. publicstaticvoidBubbleSort(intarr)3. 4. for(inti=0;iar
2、r.Length;i+)5. 6. for(intj=0;jarrj+1)9. 10. inttemp=arrj;11. arrj=arrj+1;12. arrj+1=temp;13. 14. 15. 16. 排序算法之二：选择排序（Selection Sort)以数组为例（当然其他的集合类型也是一样），这种排序是从数组的起始处开始，把第一个元素与数组中其他元素进行比较。然后将最小的元素放在第0个位置，接着再从第一个位置开始再次进行排序操作。直到数组的最后一个元素为止。1. /SelectionSortCode2. publicstaticvoidSelectSort(intarr)3. 4.
3、 intmin;5. for(inti=0;iarr.Length-1;i+)6. 7. min=i;8. for(intj=i+1;jarrj)/若写成if(arriarrj)是错误的！注意！11. 12. min=j;/保存最小数的下标13. 14. 15. if(min!=i)16. 17. inttemp=arrmin;18. arrmin=arri;19. arri=temp;20. 21. 22. 排序算法之三：插入排序（Insertion Sort）其基本操作为将一个记录插入到一个已经排序好的序列中，从而得到一个新的、记录数增1的新序列。如下图所示插入排序的过程：（图片源自网络）
4、csharpview plaincopy1. /InsertionSortCode2. 3. publicstaticvoidInsertionSort(intarr)4. 5. intinner,temp;6. for(inti=1;i0&arrinner-1temp)11. 12. arrinner=arrinner-1;13. inner-=1;14. 15. arrinner=temp;16. 17. 总结：选择排序是如上三种排序算法中效率最高的一种，其次是冒泡和插入。如上三种排序算法对小型数据集合适用，若是大型数据集合，由于其性能瓶颈，最好选用其他高级排序算法。排序算法之四：希尔排序
5、（Shells Sort）又称“缩小增量排序”（Diminshing Increment Sort）是一种对插入排序的改进算法。基本思想为：设待排序记录序列有n个记录，首先取一个整数gap0)7. 8. for(intouter=h;outerh-1)&arrinner-h=temp)14. 15. arrinner=arrinner-h;16. inner-=h;17. 18. arrinner=temp;19. 20. Console.WriteLine();21. Console.WriteLine(h=+h.ToString();22. DisplayArray(arr);23. h=
6、(h-1)%3;24. 25. 排序算法之五：归并排序算法（Merge Sort)归并排序法是将两个（或多个）有序集合合并成一个新的有序集合。即把待排序集合分为若干个子集合，对每个集合进行排序，然后再把这些有序的子集合合并为整体集合。是分治法（Divide and COnquer)的典型应用。若将两个集合合并成一个集合称为2-路归并。百度百科关于归并排序算法的介绍，非常的详细，请参阅：本处以2-路归并算法为例给出C#源代码，供大家学习。csharpview plaincopy1. /MergeSortCode2. publicstaticvoidMergeSort(intarr)3. 4. i
7、ntarrLength1,arrLength2;5. arrLength1=arr.Length/2;6. if(arr.Length%2=0)7. 8. arrLength2=arrLength1;9. 10. else11. 12. arrLength2=arrLength1+1;13. 14. intarr1=newintarrLength1;15. intarr2=newintarrLength2;16. Array.Copy(arr,0,arr1,0,arrLength1);17. Array.Copy(arr,arrLength1,arr2,0,arrLength2);18. Co
8、nsole.WriteLine(narr1BeforeSort:);19. DisplayArray(arr1);20. Console.WriteLine(narr2BeforeSort:);21. DisplayArray(arr2);22. /应用冒泡排序法为其排序23. BubbleSort(arr1);24. BubbleSort(arr2);25. Console.WriteLine(narr1AfterSort:);26. DisplayArray(arr1);27. Console.WriteLine(narr2AfterSort:);28. DisplayArray(arr2
9、);29. /合并操作arr作为目标数组30. intarrIndex=0;31. intarr1Index=0,arr2Index=0;32. while(arr1IndexarrLength1&arr2IndexarrLength2)33. 34. /选择较小项存入arr35. if(arr1arr1Indexarr2arr2Index)36. 37. arrarrIndex=arr1arr1Index;38. arr1Index+;39. 40. else41. 42. arrarrIndex=arr2arr2Index;43. arr2Index+;44. 45. arrIndex+;
10、46. 47. /对arr1或者arr2中的没有存入arr中的元素进行追加48. if(arr1Index!=arrLength1)49. 50. while(arr1IndexarrLength1)51. 52. arrarrIndex=arr1arr1Index;53. arrIndex+;54. arr1Index+;55. 56. 57. elseif(arr2Index!=arrLength2)58. 59. while(arr2IndexarrLength2)60. 61. arrarrIndex=arr2arr2Index;62. arrIndex+;63. arr2Index+
11、;64. 65. 66. DisplayArray(arr);67. 归并排序算法的时间复杂度为O(nlogn),空间复杂度为O(n).排序算法之六：堆排序（Heap Sort）首先介绍堆的概念，如果有一个关键字集合k0,k1,k2,.,kn-1,把其所有元素按完全二叉树的顺序存储在一个一维数组中，当且仅当ki=K2i并且ki=0;i-)19. 20. /交换首尾21. inttemp=arri;22. arri=arr0;23. arr0=temp;24. /调整除尾部之后的特定的堆25. Heap.MinHeapAdjust(arr,0,i);26. 27. Heap.DisplayHea
12、p(arr);28. Console.ReadLine();29. 30. 31. publicstaticclassHeap32. 33. /34. /将传入的数组调节为最小堆35. /36. /待调解数组37. /待调节的最大索引，最大索引之后的数据将不会调节38. publicstaticvoidMinHeapAdjust(intarr,intstartIndex,intmaxIndex)39. 40. /Console.WriteLine(BeforeAdjust);41. /DisplayHeap(arr);42. /首先需要获得倒数第一个分枝节点43. intcurrentBran
13、chIndex=maxIndex/2-1;44. /调整分枝节点及其子节点45. for(;currentBranchIndex=startIndex;currentBranchIndex-)46. 47. AdjustSubHeap(arr,currentBranchIndex,maxIndex);48. 49. /Console.WriteLine(AfterAdjust);50. /DisplayHeap(arr);51. 52. /53. /FliterDown算法，调整以startIndex为要的子树为最小堆54. /55. /56. /57. /58. publicstaticvo
14、idAdjustSubHeap(intarr,intcurrentIndex,intmaxIndex)59. 60. vartemp=arrcurrentIndex;61. if(2*currentIndex+1arr2*currentIndex+1)63. 64. arrcurrentIndex=arr2*currentIndex+1;65. arr2*currentIndex+1=temp;66. temp=arrcurrentIndex;/若本子树顶部的键值已经改变，则将此键值存入临时区67. AdjustSubHeap(arr,2*currentIndex+1,maxIndex);68
15、. 69. if(2*currentIndex+2arr2*currentIndex+2)72. 73. arrcurrentIndex=arr2*currentIndex+2;74. arr2*currentIndex+2=temp;75. 76. AdjustSubHeap(arr,2*currentIndex+2,maxIndex);77. 78. 79. /80. /显示Heap81. /82. /83. publicstaticvoidDisplayHeap(intarr)84. 85. foreach(intvalinarr)86. 87. Console.WriteLine(va
16、l+);88. 89. 90. 91. 92. 排序算法之七：快速排序（quick sort)快速排序也是分治法的一个实例，其主要思想为，选取一个值，将大于其的值放在其后，小于其的值放在其前。并对其前和其后的数据段进行迭代，直至分到数据段为一个数字。【它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。】（如上括号里面的为引用自别处，人家写的比俺写的好多了。）其具体做法如下：设要排序的数组是A0AN-1，首先任意选取一个数据（通常选
17、用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。一趟快速排序的算法是：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+1即I+），找到第一个大于key的Ai，Ai与Aj交换；5）重复第3、4、
18、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. 7. namespaceQuickSort8. 9. classProgram10. 11. staticvoidMain(stringargs)12
19、. 13. intarr=97,76,13,27,20,10,9,90,49,65;14. QuickSort.sort(arr,0,arr.Length-1);15. QuickSort.DisplayArr(arr,0,arr.Length);16. Console.ReadLine();17. 18. 19. publicstaticclassQuickSort20. 21. publicstaticvoidsort(intarr,intlowIndex,intupperIndex)22. 23. if(lowIndex=upperIndex)return;24. intkey,i,j,
20、temp;25. i=lowIndex;26. key=arrlowIndex;27. j=upperIndex;28. boolleftToRight=false;29. while(ij)30. 31. /从右向左检索，查找右边第一个小于key的元素32. if(!leftToRight)33. if(arrjkey)48. 49. temp=arri;50. arri=arrj;51. arrj=temp;52. j=upperIndex;53. leftToRight=false;54. 55. else56. 57. i+;58. 59. 60. if(lowIndexupperIn
21、dex)61. 62. sort(arr,lowIndex,i-1);63. sort(arr,i+1,upperIndex);64. 65. 66. /输出数组67. publicstaticvoidDisplayArr(intarr,intlowindex,intupperindex)68. 69. Console.WriteLine();70. for(inti=lowindex;iupperindex;i+)71. 72. Console.Write(arri+);73. 74. 75. 76. 排序方法的选择因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要 (
22、1)若n较小，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数；但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。这两种都是稳定排序算法。(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可