那么到底要排几遍？看一看前面的“第一遍”、“第二遍”的过程你可发现，每进行一遍，可以明确地将一个当前的最大值推到末尾，所以如果排 Count 个数，则应排 Count 遍。当然，最后一遍是空走，因为仅剩一个元素，没得比较。
下面就动手写冒泡排序法的函数。写成函数是因为我们希望这个排序法可处理任意个元素的数组。
//冒泡排序(从小到大)：
//num: 要接受排序的数组
//count : 该数组的元素个数
void bubble(int num[],int count)
{
int tmp;
//要排Count个数，则应排Count遍：
for (int i = 0; i < count; i++)
{
for(int j = 0; j < count - i - 1; j++)
{
//比较相邻的两个数：
if(num[j+1] < num[j])
{
//对调两个数，需要有"第三者"参以
tmp = num[j+1];
num[j+1] = num[j];
num[j] = tmp;
}
}
}
}
注意在内层循环中j的结束值是 count - i - 1。 要理解这段代码，明白为什么结束在count - i -1？如果你忘了如何在CB进行代码调试，如果设置断点，如何单步运行，如何观察变量的值，那么你需要“严重”复习前面有关“调试”的章节；如果你一直是高度着每一章的程序到现在，那么你可以继续下面的内容。
排序函数写出一个了，如何调试这个函数？在CB里新建一空白控制台程序，然后在主函数里，让我们写一些代码来调用这个函数，并且观察排序结果。
#include <iostream.h>
……
void bubble(int num[],int count)
{
……
}
int main() //我实在有些懒得写main里两个参数，反正它们暂时对我们都没有用，
//反正CB会为你自动生成，所以从此刻起，我不写了,除非有必要。
{
int values[] = {2,5,1,4,3};
int count = sizeof(values[]) / sizeof(values[0]);
bubble(value,sizeof);
}
你要做的工作是单步跟踪上面的代码，看看整个流程是不是像我前面不厌其烦的写的“第一遍第二遍第三遍”所描述的。
完成上面的工作了吗？全部过程下来，只花20分钟应该算是速度快或者不认真的了（天知道你是哪一种？天知道你到底是不是没有完成就来骗我？）。现在让这个程序有点输出。我们加一个小小的函数：
//输出数组的元素值
//num :待输出的数组
//count:元素个数
void printArray(int num[],int count)
{
for(int i = 0; i < count; i++)
{
count << num[i] << ",";
}
cout << endl;
}
把这个函数加到main()函数头之前，然后我们用它来输出：
int main() //我实在有些懒得写main里两个参数，反正它们暂时对我们都没有用，
//反正CB会为你自动生成，所以从此刻起，我不写了,除非有必要。
{
int values[] = {2,5,1,4,3};
int count = sizeof(values[]) / sizeof(values[0]);
cout << "排序之前：" << endl;
printArray(values,count);
//冒泡排序：
bubble(value,sizeof);
cout << "排序之后:" << endl;
printArray(values,count);
system("PAUSE");
}
后面要讲的其它排序法也将用这个printArray()来作输出。
冒泡排序是效率最差劲的方法（速度慢），不过若论起不另外占用内存，则它当属第一。在交换元素中使用了一个临时变量（第三者），还有两个循环因子i和j，这些都属于必须品，其它的它一个变量也没多占。
我们现在讲讲如何避免数据其实已经排好，程序仍然空转的的局面。
首先要肯定一点，至少一遍的空转是不可避免的，这包括让人来排，因为你要发现结果已是1，2，3，4，5了，你也是用眼睛从头到尾抄了一遍（如果你视力不好，说不定还要扫两遍呢）。
接下来一点，我们来看看除了第一遍空转，后面的是否可以避免。冒泡排序法的空转意味着什么？因为算法是拿相邻的两个比较，一发现次序不合“从小到大”的目的（小的在大的后头），就进行对调。所以如果这个对调一次也没有进行，那就说明后面的元素必然是已经完全有序了，可以放心地结束。
让我们来加个变量，用于标志刚刚完成的这一遍是否空转，如果是空转，就让代码跳出循环。
//冒泡排序(从小到大，且加了空转判断)：
void bubble(int num[],int count)
{
int tmp;
bool swapped; //有交换吗？
//要排Count个数，则应排Count遍：
for (int i = 0; i < count; i++)
{
//第一遍开始之前，我们都假充本遍可能没有交换（空转）：
swapped = false;
for(int j = 0; j < count - i - 1; j++)
{
//比较相邻的两个数：
if(num[j+1] < num[j]) //后面的数小于前面的数
{
swapped = true; //还是有交换
//对调两个数，需要有"第三者"参以
tmp = num[j+1];
num[j+1] = num[j];
num[j] = tmp;
}
}
if (!swapped)
break;
}
}
加了swapped标志，这个算法也快不了多少，甚至会慢也有可能。冒泡排序还有一些其它的改进的可能，但同样作用不大，并且会让其丧失仅有优点“代码简单直观”。所以我个人认为真有需要使用冒泡排序时，仅用最原汁原味的“泡”就好。必竟，你选择了冒泡算法，就说明你对本次排序的速度并无多高的要求。
对于n个元素，原汁原味的“冒泡排序”算法要做的比较次数是固定的： （n - 1）* n/2 次的比较。
交换次数呢？如果一开始就是排好序的数据，则交换次数为0。
一般情况下为 3 * (n - 1) * n / 4;最惨时（逆序）为3 * (n - 1) * n / 2。
冒完泡以后——情不自禁看一眼窗台罐头瓶里那只胖金鱼——让我们开始中国人最直观的选择排序法吧。对了，补一句，如果你看到有人在说“上推排序”，那么你要知道，“上推排序”是“冒泡排序”的另一种叫法，惟一的区别是：它不会让我们联想到金鱼。
18.2.3 选择排序
本章前头我们讲了“求最值”的算法，包括最大值和最小值。其实，有了求最值的算法，排序不也完成了一半？想像一下桌子上摊开着牌，第一次我们从中换挑出大王放在手上，第二次我们挑出小王，然后是黑桃老K……黑桃Q，如此下去直到小A，手中的牌不也就已经排好次序了？
每次从中选出最大值或最小值，依此排成序，这就是选择排序法的过程描述。
不过，上述的过程有一点不合要求。我们说过手中只能过一张牌。因此，在程序实现时，我们找出一个最大值之后，就要把它放到数组中最末。那数组中最末位置原来的值？当然是把它放到最大值原来所在位置了。
为了再稍稍直观点，我们改为：每次找的是最小值，找出后改为放到数组前头。
//选择排序（从小到大）
void select(int num[], int count)
{
int tmp;
int minIndex; //用于记住最小值的下标
for (int i = 0; i < count; i++)
{
minIndex = i; //每次都假设i所在位置的元素是最小的
for (int j = i + 1; j < count; j++) //j 从i+1开始，i之前的都已排好,而i是本次的第一个元素
{
if (num[minIndex] < num[j])
minIndex = j;
}
//把当前最小元素和前面第i个元素交换：
if(minIndex != i)
{
tmp = num[i];
num[i] = num[minIndex];
num[minIndex] = tmp;
}
}
}
同样是两层循环，内层循环非常类似于前面讲的求最值的的方法，重要的区别在于求最小值时，可以直接用N记下最小值，而我们这里是记下最小值元素的下标（位置）。最后把这个位置上的元素值和前面第i个元素交换。这就完成把挑出的最小值放到前面的过程。
关于如何调试，如何输出，和“冒泡”那一节一样。大家一会儿再动手吧。我先在纸上简要模拟一番，这样大家调试起来会更加心中有数。
2，5，1，4，3
第一遍：找出最小值1（下标为2），将它和第一个元素（下标为0）进行交换，结果： 1,5,2,4,3
第二遍：找出最小值2（下标为2），将它和第二个元素进行交换，结果：1,2,5,4,3
第三遍：1,2,3,4,5
同样，我们发现现在已经排好了，但程序的循环过程还得继续。只是后面将是白忙活，什么也没变。最后一遍是剩下一个1，没得比较，外层循环结束，选择排序完成。
但是，由于选择排序中内层循环完成的工作仅是找出其中的最小值，如果它空转了，只是意味着这些剩下元素中中的第一个元素正好就是最小值，并不意味剩下的元素已经有序。所以我们也不就费心去加什么空转标志了。
同冒泡排序一样，选择排序的外层循环要进行 n-1次，而内层为 n / 2 次，所以总比较次数为： (n-1) * n / 2。
交换次数最好时为： 3 * (n-1)，最坏时为 n^2 /4 + 3 *(n-1)。
18.2.4 快速排序 （选修）
排序的算法还有不少。譬如“插入排序法”和“希尔排序法”。前者有点像我们抓牌，抓到新牌，往手中已有牌的合适位置插入，最终牌都到手时，也排好序。，后者是以它的创造者的名字命名。它们都不是最快的算法。我们不去说它了。还是来说说（一般说来是）号称最快的算法吧。
“最快”是有代价的。一个是其算法复杂，不直观，根本不是人脑所擅长的思维方式，因为它要求使用“递归”，我想就算是爱因斯坦在整理扑克时，估计也不爱用这种算法。
快速排序的基本思想是分割排序对象。先选择一个值，作为“分割值”。将所有大于该值的元素放到数组的一头，而所有小于该值的元素，放到数组的另一头。这样就把数组按这个分割值划为两段。接下来的事情是对这两段分别再进行前述的操作（找分割值，再划两段）……就这样一划二、二划四、四划八进行下去。直到最每一段都只剩一个元素，排序完成。
在分段的过程中，每一个数组又是如何被归到某一段中去呢？采用的也是巧妙的交换方法。
假设我们仍然是要进行“从小到大”的排序，那么当有了一个分割值以后，就应该把比分割值大的数扔到数组后头，而比分割值小的数扔到数组前头。在快速排序法中，这个扔的过程是一种“对扔”。即：先找好前面的有哪个数需要扔到后面；再找好后面有哪个数需要扔到前头。两个数都找好了，就把这两个数互相“扔”过去，其实还是交换两个数。知道的人明白我是在说“快速排序”，不知道的人还当我是在说小布和老萨扔板砖哪？
所以，每一遍的分割过程是：
1、指定一个“分割值”。
2、从当前分段的数组前头开始往后找，找到下一个大于分割值的元素（准备扔到后头去）；
3、从当前分段的数组后头开始往前找，找到下一个小于分割值的元素（准备扔到前头去）；
4、交换2，3步找到两个元素
5、反复执行2，3，4，步；直到两端都已找不到要扔的元素。
这样，就把数组在逻辑上分为两段，前头的所有小于分割值是一段，后头所有大于分割值的是段，程序接下来递归调用快速排序的函数，分别把这两段都再次进行分割。
函数的递归调用也是我们曾经的“选修课”，如果你有些遗忘，可以回头加以复习。
每次的分割值是什么并没有太死的限定，但得在当前段数组元素最小值和最大值（含二者）之间，否则，比如元素是： 5，4，3，而分割值取的是6，就会分不出两段了。我们下面做法比较通用：就取当前段最中间那个元素的值，比如5，4，3中的4。
我们按照书写顺序，把数组前端称为“左端”，后端称为“右”端。下面的代码中,left 和 L 用来表示数组前端，而right 和 R 表示后端。
void quick(int arr, int left, int right)
{
int tmp;
int L = left, R = right;
int V; //分割值。
V = arr[ (L + R) / 2]; //分割值取中间那个元素的值。
do
{
//找前端下一个小于分割值的元素：
while (L < right && arr[L] < V)
L++;
//找后端下一个大于分割值的元素：
while (R > left && arr[R] > V)
R++;
if （L > R) //跑出当前段了，结束本段的“互扔”过程
break;
//开始互换，但 L == R 的情况说明是同一个元素，不用交换。
if ( L < R)
{
tmp = arr[L];
arr[L] = arr[R];
arr[R] = tmp;
}
L++；
R--；
}
while (true);
//前面还可以分段，继续划分
//由于前面是在 L > R 情况下break出循环，所以R此时已经比L靠前,所以拿它
//来和是前头的left比较，以确定前面的元素是否超过1个。
if (left < R)
quick(left, R); //递归调用quick()
//后面还可以分段，继续划分
//同理，L此时其实比较靠后。
if (L > right)
quick(L, right); //递归调用quick()
}
快速排序的比较和交换的次数分别为：n * log(n) 和 n * log(n) / 6。远远少于前面的两种排序方法。
18.3 小结
必须承认，在我要写上面的这些排序法算法时，我需要小心冀冀地地进行，并多次测试。 我已经将上述三种排序算加入到“扑克牌排序”的程序中，你下载以后，可以通过菜单项“扑克”下找它三者，运行后程序将演示将用各种算法来排序1到K十三张牌。不管是哪一种算法，排序13个数，都是雷霆之速，所以我加了恐怖的延时，这样你看清扑克牌的交换过程。注意：每当交换两张牌时，届面上的第14个空白位置就起到交换中“第三者”的作用。
不过，对于快速排序的演示，你可能还是只能看到前一张后一张的牌在对换，而来不及预想出下一次该换哪两张牌。必竟这一算法复杂得很。
我写这些代码需要小心冀冀，说明两点：
第一点，说明像quick这样精妙的算法，确实在理解和记忆上都比较难，而我的水平很一般。
第二点，说明我已经很长时间没有写排序法算法了，虽然我一直在用排序算法，那我的用的代码是从哪里来的？结论是：C，C++库提供的，及CB在其它各种场合提供的现成排序算法很好用，“排序？我们一们在用它，代码现成速度又快，效果还真不错！”
现在的quick排序算法还很多，连Windows的API也为我们提供了一份。不过无论是哪个现成的函数，我们现在都用不了，因为这个函数需要一个函数指针做为参数。而我们还没有学到指针（指针啊指针~!@#%$^）
(哎！最近我的手得了什么炎， 打字相当困难，只能边说边划再让人敲键盘了，原想8号推出这一课程，可一看电脑，得，9号凌晨0点1分。)
关于这一章，怎么说呢？算法是值得大家慢慢推敲的一章，因此，本章是值得花工夫的，但如果你觉得有困难，也是正常的。关于在于一个“慢慢”，我说的“慢慢”就是：“长期地，连续地，一点点来”——“就是: 循！序！渐！进！啦！”台下有个同学暴吼。
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
