数据结构之排序算法--C#实现

更多信息请浏览数据结构之排序算法--C#实现原文出处：本文中介绍的排序方法主要有以下几种：冒泡排序、选择排序、插入排序、希尔排序、归并排序、堆排序、快速排序。排序算法之一：冒泡排序（BubbleSort）冒泡排序算法是可用的最慢的排序算法之一，但是是最容易理解和实现的一种排序算法。这种排序的得名是由于数值像气泡“一样升至队列的顶端或者底端而得名，通过多次遍历整个列，并且比较相邻的数据，如果左边的数值大于右边的数值就进行交换（升序）。实现代码如下：1.//BubbleSortCode2.publicstaticvoidBubbleSort(int[]arr)3.{4.for(inti=0;iarr.Length;i++)5.{6.for(intj=0;jarr.Length-i-1;j++)7.{8.if(arr[j]arr[j+1])9.{10.inttemp=arr[j];11.arr[j]=arr[j+1];12.arr[j+1]=temp;13.}14.}15.}16.}排序算法之二：选择排序（SelectionSort)以数组为例（当然其他的集合类型也是一样），这种排序是从数组的起始处开始，把第一个元素与数组中其他元素进行比较。然后将最小的元素放在第0个位置，接着再从第一个位置开始再次进行排序操作。直到数组的最后一个元素为止。1.//SelectionSortCode2.publicstaticvoidSelectSort(int[]arr)3.{4.intmin;5.for(inti=0;iarr.Length-1;i++)6.{7.min=i;8.for(intj=i+1;jarr.Length;j++)9.{10.if(arr[min]arr[j])//若写成if(arr[i]arr[j])是错误的！注意！！11.{12.min=j;//保存最小数的下标13.}14.}15.if(min!=i)16.{17.inttemp=arr[min];18.arr[min]=arr[i];19.arr[i]=temp;20.}21.}22.}排序算法之三：插入排序（InsertionSort）其基本操作为将一个记录插入到一个已经排序好的序列中，从而得到一个新的、记录数增1的新序列。如下图所示插入排序的过程：（图片源自网络）[csharp]viewplaincopy1.//InsertionSortCode2.3.publicstaticvoidInsertionSort(int[]arr)4.{5.intinner,temp;6.for(inti=1;iarr.Length;i++)7.{8.temp=arr[i];9.inner=i;10.while(inner0&&arr[inner-1]temp)11.{12.arr[inner]=arr[inner-1];13.inner-=1;14.}15.arr[inner]=temp;16.}17.}总结：选择排序是如上三种排序算法中效率最高的一种，其次是冒泡和插入。如上三种排序算法对小型数据集合适用，若是大型数据集合，由于其性能瓶颈，最好选用其他高级排序算法。排序算法之四：希尔排序（Shell‘sSort）又称“缩小增量排序”（DiminshingIncrementSort）是一种对插入排序的改进算法。基本思想为：设待排序记录序列有n个记录，首先取一个整数gapn作为间隔，将全部记录分为gap个子序列，所有间隔为gap的记录放在同一子序列中，在每一子序列中分别执行直接插入排序。重复上述的子序列划分和排序工作，直到gap==1将所有记录放在同一个序列中排序为止。C#实现代码如下：[csharp]viewplaincopy1.//Shell'sSortCode2.publicstaticvoidShellSort(int[]arr)3.{4.intinner,temp;5.inth=3;6.while(h0)7.{8.for(intouter=h;outer=arr.Length-1;outer++)9.10.{11.temp=arr[outer];12.inner=outer;13.while((innerh-1)&&arr[inner-h]=temp)14.{15.arr[inner]=arr[inner-h];16.inner-=h;17.}18.arr[inner]=temp;19.}20.Console.WriteLine();21.Console.WriteLine(h=+h.ToString());22.DisplayArray(arr);23.h=(h-1)%3;24.}25.}排序算法之五：归并排序算法（MergeSort)归并排序法是将两个（或多个）有序集合合并成一个新的有序集合。即把待排序集合分为若干个子集合，对每个集合进行排序，然后再把这些有序的子集合合并为整体集合。是分治法（DivideandCOnquer)的典型应用。若将两个集合合并成一个集合称为2-路归并。百度百科关于归并排序算法的介绍，非常的详细，请参阅：本处以2-路归并算法为例给出C#源代码，供大家学习。[csharp]viewplaincopy1.//MergeSortCode2.publicstaticvoidMergeSort(int[]arr)3.{4.intarrLength1,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.int[]arr1=newint[arrLength1];15.int[]arr2=newint[arrLength2];16.Array.Copy(arr,0,arr1,0,arrLength1);17.Array.Copy(arr,arrLength1,arr2,0,arrLength2);18.Console.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);29.//合并操作arr作为目标数组30.intarrIndex=0;31.intarr1Index=0,arr2Index=0;32.while(arr1IndexarrLength1&&arr2IndexarrLength2)33.{34.//选择较小项存入arr35.if(arr1[arr1Index]arr2[arr2Index])36.{37.arr[arrIndex]=arr1[arr1Index];38.arr1Index++;39.}40.else41.{42.arr[arrIndex]=arr2[arr2Index];43.arr2Index++;44.}45.arrIndex++;46.}47.//对arr1或者arr2中的没有存入arr中的元素进行追加48.if(arr1Index!=arrLength1)49.{50.while(arr1IndexarrLength1)51.{52.arr[arrIndex]=arr1[arr1Index];53.arrIndex++;54.arr1Index++;55.}56.}57.elseif(arr2Index!=arrLength2)58.{59.while(arr2IndexarrLength2)60.{61.arr[arrIndex]=arr2[arr2Index];62.arrIndex++;63.arr2Index++;64.}65.}66.DisplayArray(arr);67.}归并排序算法的时间复杂度为O(nlogn),空间复杂度为O(n).排序算法之六：堆排序（HeapSort）首先介绍堆的概念，如果有一个关键字集合｛k0,k1,k2,...,kn-1｝,把其所有元素按完全二叉树的顺序存储在一个一维数组中，当且仅当ki=K2i并且ki=k(2i+1)称为最小堆。相反称为最大堆。堆性质1：大顶堆的堆顶关键字肯定是所有关键字中最大的，小顶堆的堆顶关键字是所有关键字中最小的。堆排序的思想：堆排序的思想：利用如上堆的性质1为基础，使每次从无序中选择最大记录（或最小记录）变得简单。构建初始堆和调整堆是堆排序的两个最重要的过程。并且初始堆也是对堆中所有元素的调整过程。所以算法的核心也正是堆的调整。如下摘自海子的园子()下面举例说明：给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。首先根据该数组元素构建一个完全二叉树，得到然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：20和16交换后导致16不满足堆的性质，因此需重新调整这样就得到了初始堆。即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。此时3位于堆顶不满堆的性质，则需调整继续调整这样整个区间便已经有序了。C#实现代码如下：[csharp]viewplaincopy1.//HeapSortCode2.3.usingSystem;4.usingSystem.Collections.Generic;5.usingSystem.Linq;6.usingSystem.Text;7.8.namespaceHeapSort9.{10.classProgram11.{12.staticvoidMain(string[]args)13.{14.int[]arr={53,17,78,09,45,65,87,23};15.//调整初始数据为最小堆（或者最大堆）16.Heap.MinHeapAdjust(arr,0,arr.Length);17.//交换首尾数字输出排序结果18.for(inti=arr.Length-1;i=0;i--)19.{20.//交换首尾21.inttemp=arr[i];22.arr[i]=arr[0];23.arr[0]=temp;24.//调整除尾部之后的特定的堆25.Heap.MinHeapAdjust(arr,0,i);26.}27.Heap.DisplayHeap(arr);28.Console.ReadLine();29.}30.}31.publicstaticclassHeap32.{33.///summary34.///将传入的数组调节为最小堆35.////summary36.///paramname=arr待调解数组/param37.///paramname=maxIndex待调节的最大索引，最大索引