(排序汇总1.docVIP

各种排序算法汇总 简介： 排序是计算机内常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 分内部排序和外部排序。 若整个排序过程不需要访问外存便能完成，则称此类排序为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序为外部排序。 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri = rj，且ri 在rj 之前，而在排序后的序列中，ri 仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。 分类： 稳定排序： 假定在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同的关键字的元素的相对排序仍然不变，则这种排序方法是稳定的。 其中冒泡、插入、基数、归并属于稳定排序，选择、快速、希尔、堆属于不稳定排序。 就地排序： 若排序算法所需的辅助空间并不依赖于问题的规模ri ，即辅助空间为O（1），则成为就地排序。 （交换排序）冒泡排序 已知一组无序数据a[1] , a[2] , …… , a[n] ，需将其按升序排列。首先比较a[1] 与a[2] 的值，若a[1] 大于a[2] 则交换两者的值，否则不变，再比较a[2] 与a [3] 的值，若a[2] 大于a[3] 则交换两者的值，否则不变。再比较a[3] 与a[4] ，以此类推，最后比较a[n-1] 与a[n] 的值。这样处理一轮后，a[n] 的值一定是这组数据中最大的。再对a[1] ~ a[n-1] 以相同的方法进行处理一轮，则a[n-1] 一定是a[1] ~ a[n-1] 中最大的。再对a[1] ~ a[n-2] 以相同的方法处理一轮，以此类推。共处理 n - 1轮后a[1] , a[2] , …… , a[n] 就以升序排列了。降序排列与升序排列相类似，若a[1] 小于a[2] 则交换两者的值，否则不变，后面以此类推。总的来讲，每一轮排序后最大（或最小）的数将移动到数据的最后，理论上总共要进行n(n - 1) / 2次交换。 代码实现： //summary //冒泡排序 ///summary //param name = arry要排序的整数数组 /param public static void BubbleSort(this int[] arry) { for (int i = 0 ;i arry.Length-1 ;i++ ) { for (int j = 0;jarry.Length-1 ; j++) { //比较相邻的两个元素，如果前面的比后面的大，则交换位置 if (arry[j] arry[j+1]) { int temp = arry[j+1]; arry[j+1] = arry[j]; arry[j] = temp; } } } } 简单测试： class Program2 { static void Main(String[] args) { int[] arry = new int[]{1,2,3,4,1,-1}; arry.BubbleSort(); for (int i = 0;i arry.Length ;i++ ) { Console.Write(t + arry[i]); } Console.Read(); } } 结果： -1 1 1 2 3 4 这里采用的为整数型数组添加扩展方法实现的冒泡排序。 优点：稳定 缺点：慢，每次只能移动相邻的两个元素。 时间复杂度：理想情况下（数组本来就是有序的），此时最好的时间复杂度为O（n），最坏的时间复杂度（数据时反序的），此时的时间复杂度为O（n2）。冒牌排序的平均复杂度为O（n2） 快速排序 设要排序的数组是A[0]……A[ N-1 ] ，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它晓得数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序，值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相应位置也许会在算法结束时产生变动。 一趟快速排序的算法是： 设置两个变量i、j ，排序开始的时候 i = 0 ，j = N - 1； 以第一个数组元素作为关键数据，赋值给key，即key = A[0]； 从j 开始向前有哪些信誉好的足球投注网站，即由后开始向前有哪些信誉好的足球投注网站（j - -），找到第一个小于key的值A[