【连载】（数组的排序算法，你要知道的都在这里）——乐创DIY　C语言讲义——5.4节

5.4 数组元素的排序

通常情况下，我们对数组的操作远远不止遍历判断大小或者判断奇偶数这么简单。比如，当我们需要求一个数组中所有元素的平均值时，操作很简单，只需要去遍历这个数组，并将其内部所有元素中存储的内容进行求和，最后用所有元素内容的和去除以元素个数，就可以得到最终数组的平均值。这个问题很简单。但是如果我们要求解这个数组中的中位数时，应该怎么做？此时我们来分析下，由于数组中的数值存放顺序并不是固定的，因此每个元素中存储的内容并不一定是按照存储数值从大到小存放的，也不一定是按照从小到大存放的。因此如果要求解中位数这样的算法，一定要对数组中的内容进行排序，而数组的排序操作是一种稍微有点难度的运算，因此这一小节的内容请大家开始全身贯注地看一下。

（1）冒泡排序法

冒泡算法，在传统的C语言教科书上讲的很多，它是一种比较稳定的排序算法。大家在使用这个排序算法的时候，可以从它的名字来联想一下它的实现形式。一说到冒泡，大家首先想到的是一条小鱼在水里游着，并且“布鲁布鲁”的吐出一串串小气泡，冒到水面上。其实冒泡排序法也和小于吐泡泡一样，每次只吐出一个，并且连续不断地一个接一个吐。

冒泡排序算法的中心思想，即是相邻的两个数进行比较后根据大小需求交换位置。

先从最简单的两个元素的数组看起，由此进行举一反三。假设一个数组内部只有两个元素“int array = {8, 0};”。对其进行排序时，我们仅需要做一次判断即可以知道哪个元素大，哪个元素小，假设我们从小到大进行排列，那么排列出的结果就应该是“array = {0, 8};”。

再看当有三个元素的数组。假设一个数组内部只有两个元素“int array = {8, 0, 1};”。那我们还是进行两两比较，第一次比较，可以得出数组应该为“array = {0, 1, 8};”，也是只需要一次比较就可以完成数组的排序。但如果数组改变一下元素的位置，即“int array = {8, 1, 0};”，那么我们再来看一下，第一次两两元素比较变成了“array = {1, 0, 8};”，因此碰到这种极端情况时，冒泡法一次比较完成不了排序，那么应该进行第二次比较，最终第二次比较我们可以得出结果“array = {0, 1, 8};”

再来看看四个元素时候数组的排序，这次我们举一个极端情况，即将一个从大到小排列的数组变成由小到大的顺序排列。数组为“int array = {9, 8, 1, 0};”。那么此时第一次相邻两个元素比较可以得出“array = {8, 1, 0, 9};”，第二次相邻元素两两比较可以得出“array = {1, 0, 8, 9};”，第三次两两比较可以得出“array = {0, 1, 8, 9};”。

基于上述的分析，我们可以知道，一个数组如果有n个元素需要进行排序时，其排序的极端情况应该是n-1次。具体的排序流程，见图5-4-1。

图5-4-1 冒泡排序法的流程

因此根据上述分析，我们可以写出代码如图5-4-2所示。

图5-4-2 冒泡法排序

接下来，我们将程序改装一下，让它在每一步相邻两个元素比较的过程打印出来，如图5-4-3所示。我们可以看到，越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同水里的小金鱼吐出的泡泡一串串慢慢浮出水面，故名“冒泡排序”。

图5-4-3 冒泡法排序单步打印

（2）选择排序

选择排序，俗称“硬着头皮排序”，当然这个“硬着头皮排序”是我给它取的名字，因为它是最最直观的排序方法，完美诠释了“暴力美学”这四个字。

要理解选择排序，先想象一下小学上体育课时，老师是怎么排列队伍的。先从小朋友里面随便拉一个老师认为最矮的同学出来，让他做排头，然后依次拿其他的同学和他比较，如果比他高，就放到其后面去，比他矮就放到前面，接着再来目测第二个，以此类推。当然上面这段话是描述的体育老师内心思路。

而我们对数组排序的时候，同样可以使用这种方式。我们可以先指定一个排头兵，假设我们要进行从小到大排列时，那我们先假设第一个元素为数组中最小的元素，接着分别去和剩余的其它元素比较，如果发现比它小的，那么将其自己和那个元素互换，用这种方式，只需要遍历完整个数组，就可以把最小的元素放到首个元素的位置了。如图5-4-4所示。

图5-4-4 选择排序做一次遍历比较

图5-4-4中，我们通过第一次的遍历比较，将最小的元素排列到了数组的最左端，而接下来要做的，只需要一次将剩余的9个元素进行比较，找出最小值，再放到0右边，以此类推，最后我们可以写出如图5-4-5所示的选择排序程序。

图5-4-5 选择排序法

对于数组的排序算法，我们目前就讲述这两种，其实还有很多现代的比较快速的排序算法，我们以后再说。这两种排序算法对于很多第一次接触C语言的读者来说，还是比较难理解的，因此还是需要多花功夫多多演练。