数据结构之排序算法C实现.docxVIP

更多信息请浏览/wait009alone/article/details/7546462/wait009alone/article/details/7546462数据结构之排序算法--C#实现原文出处：/hfutwyy/archive/2012/04/25/2470173.html本文中介绍的排序方法主要有以下几种：冒泡排序、选择排序、插入排序、希尔排序、归并排序、堆排序、快速排序。排序算法之一：冒泡排序（Bubble Sort）冒泡排序算法是可用的最慢的排序算法之一，但是是最容易理解和实现的一种排序算法。这种排序的得名是由于数值像气泡“一样升至队列的顶端或者底端而得名，通过多次遍历整个列，并且比较相邻的数据，如果左边的数值大于右边的数值就进行交换（升序）。实现代码如下：//Bubble?Sort?Code???public?static?void?BubbleSort(int[]?arr)???{???for(int?i=0;iarr.Length;i++)???{???for(int?j?=?0;jarr.Length-i-1;j++)???{???if(arr[j]arr[j+1])???{???int?temp?=?arr[j];???arr[j]=arr[j+1];???arr[j+1]=temp;???}???}???}???}??排序算法之二：选择排序（Selection Sort)以数组为例（当然其他的集合类型也是一样），这种排序是从数组的起始处开始，把第一个元素与数组中其他元素进行比较。然后将最小的元素放在第0个位置，接着再从第一个位置开始再次进行排序操作。直到数组的最后一个元素为止。//Selection?Sort?Code???public?static?void?SelectSort(int[]?arr)???{???int?min;???for?(int?i?=?0;?i??arr.Length-1;?i++)???{???min?=?i;???for?(int?j?=?i?+?1;?j??arr.Length;?j++)???{???if?(arr[min]??arr[j])?//?若写成if?(arr[i]??arr[j])是错误的！注意！！??{???min?=?j;//保存最小数的下标??}???}???if?(min?!=?i)???{???int?temp?=?arr[min];???arr[min]?=?arr[i];???arr[i]?=?temp;???}???}???}??排序算法之三：插入排序（Insertion Sort）其基本操作为将一个记录插入到一个已经排序好的序列中，从而得到一个新的、记录数增1的新序列。如下图所示插入排序的过程：（图片源自网络）[csharp]?view plaincopy//Insertion?Sort?Code????public?static?void?InsertionSort(int[]?arr)???{???int?inner,?temp;???for?(int?i?=?1;?i??arr.Length;?i++)???{???temp?=?arr[i];???inner?=?i;???while?(inner??0??arr[inner?-?1]??temp)???{???arr[inner]?=?arr[inner?-?1];???inner?-=?1;???}???arr[inner]?=?temp;???}???}??总结：选择排序是如上三种排序算法中效率最高的一种，其次是冒泡和插入。如上三种排序算法对小型数据集合适用，若是大型数据集合，由于其性能瓶颈，最好选用其他高级排序算法。排序算法之四：希尔排序（Shell‘s Sort）又称“缩小增量排序”（Diminshing Increment Sort）是一种对插入排序的改进算法。基本思想为：设待排序记录序列有n个记录，首先取一个整数gapn作为间隔，将全部记录分为gap个子序列，所有间隔为gap的记录放在同一子序列中，在每一子序列中分别执行直接插入排序。重复上述的子序列划分和排序工作，直到gap==1将所有记录放在同一个序列中排序为止。C#实现代码如下：[csharp]?view plaincopy//Shells?Sort?Code???public?static?void?ShellSort(int[]?arr)???{???int?inner,?temp;???int?h?=?3;???while?(h??0)???{???for?(int?outer?=?h;?outer?=?arr.Length?-?1;?outer?++)??{???temp?=?arr[outer];??