《Visual C# 最佳实践》第三章 数组结构 (二)：排序
时间：2010-10-17 来源：邹俊才
本章的学习重点：
◆ 排序概念
◆ 冒泡排序
◆ 插入排序
3.2排序
C#排序算法一般都涉及到循环，以及赋值。通过排序，能进行简单的统计与分类，具有极其重要的价值。这里将介绍两种不同的C#排序算法代码，希望对大家有所帮助。
3.2.1排序概述
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。良好排序方法可以有效提高排序速度，提高排序效果。排序主要分两种：内部排序和外部排序。
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；
反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
内排序的方法有许多种，按所用策略不同，可归纳为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
其中，插入排序主要包括直接插入排序和希尔排序两种；选择排序主要包括直接选择排序和堆排序；交换排序主要包括气（冒）泡排序和快速排序。
3.2.2冒泡排序
在许多程序设计中，我们需要将一个数列进行排序，以方便统计，常见的排序方法有冒泡排序，二叉树排序，选择排序等等。而冒泡排序一直由于其简洁的思想方法和比较高的效率而倍受青睐。
基础思想：将相邻记录的关键码进行比较，若前面记录的关键码大于后面记录的关键码，则将它们交换，否则不交换。设待排序的顺序表List中有n个记录，初始时子序列中只有一个记录List[0]，第一次排序时，把List[1]与List[0]比较大小，若List[0]<=List[1]，说明不需要排序，否则交换List[0]与List[1]的值，第二次排序的时候，List[2]与List[1]比较大小，若List[2]<=List[1]，则交换List[1]与List[2]的值。
那么第一趟排完后就会确定最大的数已经放在最后一个了，然后第二次排的话就会少循环一次，所以冒泡要二重循环，每一次都会少比较一次。
原始数组： 21 54 76 12 34 44 12 15 28 3 10 68
第一次交换： 21 54 76 12 34 44 12 15 3 28 10 68
第二次交换： 21 54 76 12 34 44 12 3 15 28 10 68
第三次交换： 21 54 76 12 34 44 3 12 15 28 10 68
第四次交换： 21 54 76 12 34 3 44 12 15 28 10 68
第五次交换： 21 54 76 12 3 34 44 12 15 28 10 68
第六次交换： 21 54 76 3 12 34 44 12 15 28 10 68
第七次交换： 21 54 3 76 12 34 44 12 15 28 10 68
第八次交换： 21 3 54 76 12 34 44 12 15 28 10 68
第九次交换： 3 21 54 76 12 34 44 12 15 28 10 68
第一趟排序： 3 21 54 76 12 34 44 12 15 28 10 68
第十次交换： 3 21 54 76 12 34 44 12 15 10 28 68
第十一次交换： 3 21 54 76 12 34 44 12 10 15 28 68
第十二次交换： 3 21 54 76 12 34 44 10 12 15 28 68
第十三次交换： 3 21 54 76 12 34 10 44 12 15 28 68
第十四次交换： 3 21 54 76 12 10 34 44 12 15 28 68
……
第二趟排序： 3 10 21 54 76 12 34 44 12 15 28 68
第三趟排序： 3 10 12 21 54 76 12 34 44 15 28 68
……
最后一趟排序： 3 10 12 12 15 21 28 34 44 54 68 76
下面我们来看一个范例：
01 using System;
02 public class TestBubbleSort
03 {
04 public static void Main(string[] args)
05 {
06 int[] list = new int[] { 2, 6, 3, 8, 2, 7, 3 }; //定义int类型的数组
07 BubbleSort(list); //进行排序
08 for (int i = 0; i < list.Length; i++) //循环输出排序后的数组
09 {
10 Console.WriteLine(list[i]); //输出结果
11 }
12 }
13 public static void BubbleSort(int[] list) //冒泡排序算法
14 {
15 for (int i = 0; i < list.Length; i++) //控制第几趟交换
16 {
17 for (int j = i; j < list.Length; j++) //控制第几趟的第几次交换
18 {
19 if (list[i] < list[j]) //比较数组前后项的大小，如果小，则交换
20 {
21 int temp = list[i]; //创建一个临时变量保存数据
22 list[i] = list[j]; //把后面的数据放在前面
23 list[j] = temp; //把前面的数据放在后面
24 }
25 }
26 }
27 }
28 }
上述代码中，由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为(n*n)。
优点：稳定，比较次数已知；
缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。
3.2.3插入排序
基本思路：顺序地将待排序的记录按其关键码的大小插入到已排序的记录子序列的适当位置。设待排序的顺序表List中有n个记录，初始时子序列中只有一个记录List[0]，第一次排序时，把List[1]与List[0]比较大小，若List[0]<=List[1]，说明不需要排序，否则把位置改变过来，第二次排序的时候，List[2]与List[1]比较大小，如果List[2]比List[1]小，再和List[0]比，然后插入到合适的位置。
原始数组： 23 53 73 11 34 44 11 15 28 3 10 66
↓
第一次插入： 23 53 73 11 34 44 11 15 28 3 10 66
↓
第二次插入： 23 53 73 11 34 44 11 15 28 3 10 66
↓--------------|
第三次插入： 11 23 53 73 34 44 11 15 28 3 10 66
↓--------|
第四次插入： 11 23 34 53 73 44 11 15 28 3 10 66
↓--------|
第五次插入： 11 23 34 44 53 73 11 15 28 3 10 66
↓----------------------------|
第六次插入： 11 11 23 34 44 53 73 15 28 3 10 66
↓----------------------|
第七次插入： 11 11 15 23 34 44 53 73 28 3 10 66
……
最后结果： 3 10 11 11 15 23 28 34 44 53 66 73
下面我们来看一个范例：
01 using System;
02 public class TestInsertionSort
03 {
04 public static void Main(string[] args)
05 {
06 int[] list = new int[] { 2, 6, 3, 8, 2, 7, 3 }; //定义int类型的数组
07 InsertionSort(list); //进行排序
08 for (int i = 0; i < list.Length; i++) //循环输出排序后的数组
09 {
10 Console.WriteLine(list[i]); //输出结果
11 }
12 }
13 public static void InsertionSort(int[] list) //插入排序算法
14 {
15 for (int i = 1; i < list.Length; i++) //从第一个元素开始，该元素可认为已排序
16 {
17 int t = list[i];
18 int j = i;
19 while ((j > 0) && (list[j - 1] > t)) //在已排序的元素序列中从后向前扫描
20 {
21 list[j] = list[j - 1]; //将新元素插入到该位置中
22 --j;
23 }
24 list[j] = t;
25 }
26 }
27 }
上述代码中，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置中
6. 重复步骤2
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1)次。平均来说插入排序算法复杂度为(n*2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。
相关阅读 更多 +
