labview数组排序算法.docx
《labview数组排序算法.docx》由会员分享，可在线阅读，更多相关《labview数组排序算法.docx（15页珍藏版）》请在冰点文库上搜索。
labview数组排序算法
18.2.2冒泡排序
“冒泡”是什么意思？
湖底有时会冒出一个气泡，气泡刚在湖底时，是很小的，在向上浮的过程中，才一点地慢慢变大。
学过高中的物理的人，应该不难解释这一现象。
冒泡排序的过程有点类似这个过程，每前进一步，值就大一点。
排序当然有两个方向，一种是从小排到大，一种是从大排到小。
大多数教科书里都讲第一种，我们也如此。
这样一来，冒泡排序法就改为“沉泡法”了，较大值一点点跑到数组中的末尾。
一般教科书里也会说，冒泡排序法是人们最熟悉，及最直观的排序法，我可不这样认为。
或许老外在生活中用的是这种最笨的排序法？
我猜想，大家在生活中99%使用后面要讲的“选择”排序法。
冒泡排序是这么一个过程（从小到大）:
1、比较相邻的两个元素，如果后面的比前面小，就对调二者。
反复比较，到最后两个元素。
结果，最大值就跑到了最末位置。
2、反复第一步，直到所有较大值都跑到靠后的位置。
看一眼例子：
2，5，1，4，3
第一遍：
·比较第一对相邻元素：
2，5，发现后面的5并不比2小，所以不做处理。
序列保持不变：
2，5，1，4，3
·继续比较后两对元素：
5，1，发现后面的1比前面的5小，所以对调二者。
现在，序列变为：
2，1，5，4，3
·继续比较后两对元素：
5，4……对调，于是：
2，1，4，5，3
·继续比较后两对元素：
5，3……对调，于是：
2，1，4，3，5<-----OK,现在最大值5跑到最尾处了。
大泡泡“5”浮出来了，但前面的2,1,4,3,还是没有排好，没事，再来一遍，不过，由于最后一个元素肯定是最大值了，所以我们这回只排到倒数第二个即可。
第二遍：
·比较第一对相邻元素：
2，1，发现1比2小，所以对调：
1,2,4,3,5
·继续比较后两对元素：
2，4，不用处理，因为后面的数比较大。
序列还是：
1,2,4,3,5
·继续4，3，对调：
1,2,3,4,5。
前面说，5不用再参加比较了。
现在的序列是1，2，3，4，5。
接下来，我们再来一遍：
第三遍：
·比较第一对相邻元素：
1，2：
不用对调。
……等等……
有人说，现在已经是1，2，3，4，5了，完全是排好序了啊，何必再来进行呢？
我们确实是看出前面1，2，3也井然有序了，但对于程序来说，它只能明确地知道自己已经排好了两个数：
4，5，并不知道的1，2，3凑巧也排好了。
所以它必须再排两次，直到确认把3和2都已推到合适的位置上。
最后剩一个数是1，因为只有一个数，没得比，所以这才宣告排序结束。
那么到底要排几遍？
看一看前面的“第一遍”、“第二遍”的过程你可发现，每进行一遍，可以明确地将一个当前的最大值推到末尾，所以如果排Count个数，则应排Count遍。
当然，最后一遍是空走，因为仅剩一个元素，没得比较。
下面就动手写冒泡排序法的函数。
写成函数是因为我们希望这个排序法可处理任意个元素的数组。
//冒泡排序（从小到大）：
//num:
要接受排序的数组
//count:
该数组的元素个数
voidbubble（intnum[],intcount）
{
inttmp;
//要排Count个数，则应排Count遍：
for（inti=0;i {
for（intj=0;j {
//比较相邻的两个数：
if（num[j+1] {
//对调两个数，需要有"第三者"参以
tmp=num[j+1];
num[j+1]=num[j];
num[j]=tmp;
}
}
}
}
注意在内层循环中j的结束值是count-i-1。
要理解这段代码，明白为什么结束在count-i-1？
如果你忘了如何在CB进行代码调试，如果设置断点，如何单步运行，如何观察变量的值，那么你需要“严重”复习前面有关“调试”的章节；如果你一直是高度着每一章的程序到现在，那么你可以继续下面的内容。
排序函数写出一个了，如何调试这个函数？
在CB里新建一空白控制台程序，然后在主函数里，让我们写一些代码来调用这个函数，并且观察排序结果。
#include
……
voidbubble（intnum[],intcount）
{
……
}
intmain（）//我实在有些懒得写main里两个参数，反正它们暂时对我们都没有用，
//反正CB会为你自动生成，所以从此刻起，我不写了,除非有必要。
{
intvalues[]={2,5,1,4,3};
intcount=sizeof（values[]）/sizeof（values[0]）;
bubble（value,sizeof）;
}
你要做的工作是单步跟踪上面的代码，看看整个流程是不是像我前面不厌其烦的写的“第一遍第二遍第三遍”所描述的。
完成上面的工作了吗？
全部过程下来，只花20分钟应该算是速度快或者不认真的了（天知道你是哪一种？
天知道你到底是不是没有完成就来骗我？
）。
现在让这个程序有点输出。
我们加一个小小的函数：
//输出数组的元素值
//num:
待输出的数组
//count:
元素个数
voidprintArray（intnum[],intcount）
{
for（inti=0;i {
count< }
cout<}
把这个函数加到main（）函数头之前，然后我们用它来输出：
intmain（）//我实在有些懒得写main里两个参数，反正它们暂时对我们都没有用，
//反正CB会为你自动生成，所以从此刻起，我不写了,除非有必要。
{
intvalues[]={2,5,1,4,3};
intcount=sizeof（values[]）/sizeof（values[0]）;
cout<<"排序之前：
"< printArray（values,count）;
//冒泡排序：
bubble（value,sizeof）;
cout<<"排序之后:
" < printArray（values,count）;
system（"PAUSE"）;
}
后面要讲的其它排序法也将用这个printArray（）来作输出。
冒泡排序是效率最差劲的方法（速度慢），不过若论起不另外占用内存，则它当属第一。
在交换元素中使用了一个临时变量（第三者），还有两个循环因子i和j，这些都属于必须品，其它的它一个变量也没多占。
我们现在讲讲如何避免数据其实已经排好，程序仍然空转的的局面。
首先要肯定一点，至少一遍的空转是不可避免的，这包括让人来排，因为你要发现结果已是1，2，3，4，5了，你也是用眼睛从头到尾抄了一遍（如果你视力不好，说不定还要扫两遍呢）。
接下来一点，我们来看看除了第一遍空转，后面的是否可以避免。
冒泡排序法的空转意味着什么？
因为算法是拿相邻的两个比较，一发现次序不合“从小到大”的目的（小的在大的后头），就进行对调。
所以如果这个对调一次也没有进行，那就说明后面的元素必然是已经完全有序了，可以放心地结束。
让我们来加个变量，用于标志刚刚完成的这一遍是否空转，如果是空转，就让代码跳出循环。
//冒泡排序（从小到大，且加了空转判断）：
voidbubble（intnum[],intcount）
{
inttmp;
boolswapped; //有交换吗？
//要排Count个数，则应排Count遍：
for（inti=0;i {
//第一遍开始之前，我们都假充本遍可能没有交换（空转）：
swapped=false;
for（intj=0;j {
//比较相邻的两个数：
if（num[j+1] {
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，手中的牌不也就已经排好次序了？
每次从中选出最大值或最小值，依此排成序，这就是选择排序法的过程描述。
不过，上述的过程有一点不合要求。
我们说过手中只能过一张牌。
因此，在程序实现时，我们找出一个最大值之后，就要把它放到数组中最末。
那数组中最末位置原来的值？
当然是把它放到最大值原来所在位置了。
为了再稍稍直观点，我们改为：
每次找的是最小值，找出后改为放到数组前头。
//选择排序（从小到大）
voidselect（intnum[],intcount）
{
inttmp;
intminIndex;//用于记住最小值的下标
for（inti=0;i {
minIndex=i;//每次都假设i所在位置的元素是最小的
for（intj=i+1;j {
if（num[minIndex] 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表示后端。
voidquick（intarr,intleft,intright）
{
inttmp;
intL=left,R=right;
intV; //分割值。
V=arr[（L+R）/2]; //分割值取中间那个元素的值。
do
{
//找前端下一个小于分割值的元素：
while（L L++;
//找后端下一个大于分割值的元素：
while（R>left&&arr[R]>V）
R++;
if（L>R）//跑出当前段了，结束本段的“互扔”过程
break;
//开始互换，但L==R的情况说明是同一个元素，不用交换。
if（L {
tmp=arr[L];
arr[L]=arr[R];
arr[R]=tmp;
}
L++；
R--；
}
while（true）;
//前面还可以分段，继续划分
//由于前面是在L>R情况下break出循环，所以R此时已经比L靠前,所以拿它
//来和是前头的left比较，以确定前面的元素是否超过1个。
if（left quick（left,R）; //递归调用quick（）
//后面还可以分段，继续划分
//同理，L此时其实比较靠后。
if（L>right）
quick（L,right）; //递归调用quick（）
}
快速排序的比较和交换的次数分别为：
n*log（n）和n*log（n）/6。
远远少于前面的两种排序方法。
升级会员 