7.5 数组排序算法
视频讲解：光盘\TM\lx\7\05数组排序算法．mp4
数组有很多常用的算法，本节将介绍常用的排序算法，包括冒泡排序法、直接插入排序法和选择排序法。
7.5.1 冒泡排序
冒泡排序方法以简洁的思想与实现方法而备受青睐，是广大初学者最先接触的一个排序算法。这种方法排序数组元素的过程总是小数往前放，大数往后放，类似水中气泡往上升的动作，所以称作冒泡排序。
1．基本思想
冒泡排序的基本思想是对比相邻的元素值，如果满足条件就交换元素值，把较小的元素移动到数组前面，把大的元素移动到数组后面（也就是交换两个元素的位置），这样较小的元素就像气泡一样从底部上升到顶部。
2．算法示例
冒泡算法由双层循环实现，其中外层循环用于控制排序轮数，一般是要排序的数组长度减1次，因为最后一次循环只剩下一个数组元素，不需要对比，同时数组已经完成排序了。而内层循环主要用于对比数组中每个临近元素的大小，以确定是否交换位置，对比和交换次数以排序轮数而减少。例如，一个拥有6个元素的数组，在排序过程中每一次循环的排序过程和结果如图7.13所示。
图7.13 6个元素数组的排序过程
第一轮外层循环时把最大的元素值63移动到了最后面（相应的比63小的元素向前移动，类似气泡上升），第二轮外层循环不再对比最后一个元素值63，因为它已经确认为最大（不需要上升），应该放在最后，需要对比和移动的是其他剩余元素，这次将元素24移动到了63的前一个位置。其他循环将依此类推，继续完成排序任务。
3．算法实现
下面来介绍一下冒泡排序的具体用法。
【例7.19】创建一个控制台应用程序，使用冒泡法对数组中的元素从小到大进行排序。程序代码如下。（实例位置：光盘\TM\sl\7\9）
static void Main(string[] args)
{
int[] arr=new int[]{63, 4, 24, 1, 3, 15}; //定义一个一维数组，并赋值
//定义两个int类型的变量，分别用来表示数组下标和存储新的数组元素
int j, temp;
for (int i=0; i<arr.Length-1;i++) //根据数组下标的值遍历数组元素
{
j = i + 1;
id: //定义一个标识，以便从这里开始执行语句
if (arr[i]>arr[j]) //判断前后两个数的大小
{
temp=arr[i]; //将比较后大的元素赋值给定义的int变量
arr[i]=arr[j]; //将后一个元素的值赋值给前一个元素
arr[j]=temp; //将int变量中存储的元素值赋值给后一个元素
goto id; //返回标识，继续判断后面的元素
}
eIse
if (j<arr.Length-1) //判断是否执行到最后一个元素
{
j++; //如果没有，则再往后判断
goto id; //返回标识，继续判断后面的元素
}
}
foreach (int n in arr) //循环遍历排序后的数组元素并输出
Console.Write(n + " ");
Console.WriteLine();
}
按Ctrl+F5键查看运行结果，如图7.14所示。
图7.14 冒泡法排序实例运行结果
注意 在对数组进行遍历时，要用当前数组的Length属性来获取数组的元素个数。
从实例的运行结果来看，数组中的元素已经按从小到大的顺序排序好了。冒泡排序的主要思想就是：把相邻两个元素进行比较，如满足一定条件则进行交换（如判断大小或日期前后等），每次循环就将最大（或最小）的元素排在最后，下一次循环是对数组中其他的元素进行类似操作。
7.5.2 直接插入排序
直接排序方法是一种常用的数组排序算法，是初学者应该掌握的。
1．基本思想
直接插入排序是一种最简单的排序方法，其基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表，然后再从剩下的关键字中选取下一个插入对象，反复执行直到整个序列有序。
2．算法示例
插入排序法实现时，将n个有序数存放在数组a中，要插入的数为x，首先确定x插在数组中的位置p，数组中p之后的元素都向后移一个位置，空出a(p)，将x放入a(p)。这样即可实现插入后数列仍然有序。
举例：
初始数组资源 【63 4 24 1 3 15】
第一趟排序后 【4 63】 24 1 3 15
第二趟排序后 【4 24 63】 1 3 15
第三趟排序后 【1 4 24 63】 3 15
第四趟排序后 【1 3 4 24 63】 15
第五趟排序后 【1 3 4 15 24 63】
3．算法实现
下面来介绍一下直接插入排序的具体用法。
【例7.20】创建一个控制台应用程序，使用直接插入法对数组中的元素从小到大进行排序。程序代码如下。（实例位置：光盘\TM\sl\7\10）
static void Main(string[] args)
{
int[] arr=new int[]{63, 4, 24, 1, 3, 15}; //定义一个一维数组，并赋值
for (int i=0; i<arr.Length;++i) //循环访问数组中的元素
{
int temp=arr[i]; //定义一个int变量，并使用获得的数组元素值赋值
int j=i;
whiIe ((j>0)&&(arr[j-1]>temp)) //判断数组中的元素是否大于获得的值
{
arr[j]=arr[j-1]; //如果是，则将后一个元素的值提前
--j;
}
arr[j]=temp; //最后将int变量存储的值赋值给最后一个元素
}
Console.WriteLine("排序后结果为：");
foreach (int n in arr) //循环访问排序后的数组元素并输出
Console.Write("{0}", n + " ");
Console.WriteLine();
}
按Ctrl+F5键查看运行结果，如图7.15所示。
图7.15 直接插入法排序实例运行结果
闯关训练：使用希尔排序算法对一维数组“63, 4, 24, 1, 3, 15”进行排序。希尔排序又称“缩小增量排序”，其基本思想是，先将整个待排序的一组序列分割成为若干子序列，然后分别进行直接插入排序，待整个序列中的数“基本有序”时再对全体记录进行一次直接插入排序。
7.5.3 选择排序法
选择排序方法的排序速度要比冒泡排序快一些，也是常用的排序算法，是初学者应该掌握的。
1．基本思想
选择排序的基本思想是将指定排序位置与其他数组元素分别对比，如果满足条件就交换元素值，注意这里有别于冒泡排序，不是交换相邻元素，而是把满足条件的元素与指定的排序位置交换（如从第一个元素开始排序），这样排序好的位置逐渐扩大，最后整个数组都成为已排序好的格式。
这就好比有一个小学生，从包含数字1~10的乱序的数字堆中分别选择合适的数字，组成一个从1~10的排序，而这个学生首先从数字堆中选出1，放在第一位，然后选出2（注意这时数字堆中已经没有1了），放在第二位，依次类推，直到其找到数字9，放到8的后面，最后剩下10，就不用选择了，直接放到最后就可以了。
与冒泡排序相比，选择排序的交换次数要少很多，所以速度会快些。
2．算法示例
每一趟在n个记录中选取关键字最小的记录作为有序序列的第I个记录，并且令I为1~n-1，进行n-1趟选择操作。
例如：
初始数组资源 【63 4 24 1 3 15】
第一趟排序后【1】 4 24 63 3 15
第二趟排序后【1 3】 24 63 4 15
第三趟排序后【1 3 4】 63 24 15
第四趟排序后【1 3 4 15】 24 63
第五趟排序后【1 3 4 15 24】 63
3．算法实现
下面来介绍一下选择排序法的具体用法。
【例7.21】创建一个控制台应用程序，使用选择排序法对数组中的元素从小到大进行排序，程序代码如下。（实例位置：光盘\TM\sl\7\11）
static void Main(string[] args)
{
int[] arr=new int[]{63, 4, 24, 1, 3, 15}; //定义一个一维数组，并赋值
int min; //定义一个int变量，用来存储数组下标
for (int i=0; i<arr.Length-1; i++) //循环访问数组中的元素值（除最后一个）
{
min=i; //为定义的数组下标赋值
for (int j=i+1; j<arr.Length; j++) //循环访问数组中的元素值（除第一个）
{
if (arr[j]<arr[min]) //判断相邻两个元素值的大小
min=j;
}
int t=arr[min]; //定义一个int变量，用来存储比较大的数组元素值
arr[min]=arr[i]; //将小的数组元素值移动到前一位
arr[i]=t; //将int变量中存储的较大的数组元素值向后移
}
Console.WriteLine("排序后结果为：");
foreach (int n in arr) //循环访问排序后的数组元素并输出
Console.Write("{0}", n + " ");
Console.WriteLine();
}
按Ctrl+F5键查看运行结果，如图7.16所示。
图7.16 选择排序法实例运行结果