第十八章 数组(三) ---- 数组的最值与排序

 

18.1 求数组中的最大值

  18.1.1 基本思路与实现

  18.1.2 实例

18.2 将数组元素排序

  18.2.1 现实算法与程序算法的不同

  18.2.2 冒泡排序

  18.2.3 选择排序

  18.2.4 快速排序 (选修)

18.3 小结
 

什么叫程序?随着我们学习的不断进展,这个问题的答案不断有新的表述。

今天,我们学过了“流程”,也学过了“数据类型”。

“流程”表达某种动作或操作的过程;“数据”表达现实生活的事物。因此,程序自然可以表达为“通过流程控制,来对数据进行正确的处理”。其实这一句话,也可以用两个字来代替“算法”。

事实上有一个著名的公式,说:程序 = 数据结构 + 算法。

 

要想真正理解什么叫算法,最好的办法还是从我们的现实生活入手。

 

最常见的例子,就是给整理扑克牌了。给你一付打乱的扑克牌,然后让你把它们整理,就是让你排序。结果是:前四张是:黑桃A,红心A,草花A、方块A,然后是2,3……老K,最后是大小王两张。 

这个过程使用的是“排序”算法。

 

更简单的,给你3张牌,让你找出其中最大的一张,这也需要一种算法。称为“求最值”。

 

你会说,这也算“算法”,3张牌往桌子上一摆,我“一眼”就能找出哪一张最大啊,我的大脑好像没有进行过任何计算。呵呵,这样说可就不对了。你把这三张牌往一头猪前面摆,摆上三年它也找不出哪一张是最大的。这可以证明,我们的大脑的确进行了一定的演算。

 

一套相同的算法,其实是连续的一段“流程控制”。可以用在不同的数据上。比如排序算法,我们可以用于整理扑克,也可以用于排出学员成绩的名次,而不这两样数据的数据结构是什么。但是一套算法在实现时,针对不同数据结构,有不同的实现。

 

这一章主要就是讲两种算法在数组上的实现,这两种算法是:“求最值”、“排序”。

 

18.1 求数组中的最大值

数组含有许多元素,这些元素如果是可以比较大小的,那就常常需要一种计算,求出这些元素中的最大值或最小值。求最值的算法应用在方方面面,比如:如何找出一条街上你喜欢的那某裙子最便宜卖的那家店。比如当早上第四节下课铃敲响后,如何找出从教室到食堂最近的一条路等等。

18.1.1 基本思路与实现

我想大家都知道了,一到要讲实例,我举的例子就是“成绩管理”。“烦不烦呢?”我看到有些同学使劲撇嘴。可不能烦啊,上一章的成绩管理中,“求成绩第一名”和“成绩排序”这样重要的功能还没实现呢。本章的作业就是它们了。

 

比如有这么一个数组,用于存储几个学生成绩。现在老师想找出其中的第一名。

 

int cj[] = {80,67,76,87,78};

 

我们还是一眼“找”出了结果:87。但如果不是5个成绩,而是5万个成绩呢(比如首钢的工人进行考试的结果)?我们就不能一眼看出,而是不断地从一个个成绩里搜寻那个最大值。不管是5万还是5个,其实算法是一样的。

 

冰心老奶奶举了个例子:同样是从动物园回来,有的小学生写出让你如临其境的作文,而有的小学生则像是没有去过动物园一样,写得干巴巴的。

 

在把你的解决问题的思路转化为程序代码的过程中,显然第一步应该做是你能够用自然语言清楚地,准确地表达出你的思路。有些人能做好这一点,而有些人则表达得相当困难,仿佛他不会解决问题。

 

当然这是一个双向锻炼的过程,如果你原来在这方面不擅长,跟着我在这里学习编程,慢慢的你会发现自已不仅学会也写程序,而且学会了如何表达自已的想法、思路、情感……很多人说学习编程是一件快乐的事,很多人沉迷于编程,其中的一点奥妙,他们都不肯“泄密”,我泄密了。

 

言归正传。大家提起精神来!

 

求最大值是一个“比较”的过程。我们就说5个数的情况,看看如何找出5个数中的最大值:

 

2、3、1、4、0

 

为了方便表达,我们用 N 来表示最大值。

 

1、首先假设第一个数就是最大值,则 N = 2;

2、把N和第二个数比较,发现 3N 大,于是让 N = 3;

3、把N和第三个数比较,发现 1 不比 N 大,于是N不变。

4、把N和第四个数比较,发现 4 比 N 大,于是让 N = 4;

5、把N和第五个数比较,发现 0 不比 N 大,于是N不变;

 

求五个数的最大值,我们用了五行话表达,如果求100个数的最值呢?要比较99次,岂不是要写100行?按照它的表达,我们写成的代码是:

 

int n[5] = {2,3,1,4,0};

 

int N = n[0];

 

if(N > n[1])

  N = n[1];

if(N > n[2])

  N = n[2];

if(N > n[3])

  N = n[3];

if(N > n[4])

  N = n[4];

 

这可不叫“算法”。所以前面的表达并没有说出真正的算法。我们要改进它。

 

1、首先假设第一个数就是最大值,则 N = 2;

2、把N和下一个数比较,如果下一个数比N大,则让N等于该数;

3、重复第二步,直到没有下一个数。

 

明白了吗?算法就是这样而来的。第一,这三行话可以适用于无论多少个数求最大值的情况,这是你的算法是否正确的一个必要条件,如果你的算法表达的长短依赖于具体数据的个数,那么你的算法不是通用的算法,不管是否能解决问题。第二,我们在表达中看到了“如果”,看到“重复”,很好,“如果”就是“分支流程”,就是ifswitch;而“重复”就是“循环流程”,是for while do...while

 

int n[5] = {2,3,1,4,0};

 

int N = n[0];

 

for( int i = 1; i < 5; i++)

{

   if(n[i] > N)

     N = n[i];

}

 

循环从数组下标1开始,因为从算法的表述中,我们也看到了,N一开始就等于数组中的第一个数,而后和“下一个数”开始比较。

我们可以把代码改良,以让它方便于应用在任何个数的元素上。

 

int n[] = {2,3,1,4,0};

 

int N = n[0];

 

int count = sizeof(n) / sizeof(n[0]);

 

for( int i = 1; i < count; i++)

{

   if (n[i] > N)

     N = n[i];

}

 

18.1.2 实例

 

要求:

1、不使用数组,实现让用户输入10个数,然后输出其中最大值。

2、同1,但要求使用数组。

 

既然是两个小题,我们就分别写两个函数吧。

 

//不使用数组的例子:

void max1()

{

  cout << "请输入10个数(每个数输入后加回车)" << endl;

 

  int N,n;

 

  cout << "第1个数:" :

  cin >> N;

 

  for(int i = 1; i<10; i++)

  {

      cout << "" << i+1 << "个数:" ;

      cin >> n;

 

      if( n > N)

         N = n;

  }

 

  cout << "最大值为:" << N << endl;

 

  system("PAUSE");  //让控制台系统暂停。相当于我们以前的cin.get() getchar();

}

 

//使用数组的例子:

void max2()

{

   cout << "请输入10个数(每个数输入后加回车)" << endl;

 

   int n[10];

   int N;

 

   for(int i = 0; i<10; i++)

   {

      cout << "" << i+1 << "个数:";

      cin >> n[i];

   }

 

   N = n[0];

   for(int i=1; i<10; i++)

   {

     if(n[i] > N)

       N = n[i];

   }

 

  cout << "最大值为:" << N << endl;

 

  system("PAUSE");  //让控制台系统暂停。

}

 

这样就完成了求最大值实例,如果是要求求最小值呢?改动仅在于那个if判断条件:

 

……

N = n[0]; //一开始假设第一个元素就是最小值

 

for(……)

{

  if (n[i] < N) //如果有元素比我们假设的最小值还小,那就让最小值等于它吧

      N = n[i];

}

……

 

这套题目我没有提供实际代码,大家找开CB自已完成吧。重要的是,在调通程序之后,认真地比较两种处理方法之间的异同。

结论应该是:“算法的抽象逻辑是一样的,只是用在于不同的数据结构上,会有不同的实现”。前者只使用简单的数据类型,所以它不得不在一边输入的情况下,一边求最大值;而后者采用了数组,所以可以从容地先完成输入工作,然后再求最大值。

当算法经较复杂时,采用良好的数据结构的重要性就开始体现,比如下面的排序,我们必须使用数组或其它更复杂的数据。否则就实现不了。

 

18.2 将数组元素排序

 

排序,一个经典教学课程。

排序,一个在超高频的实用算法。

第一点是说,我们必须去学。第二点是说,像这样一个实用算法以,事实上C,C++肯定都为我们写好了,以库函数等形式提供给我们使用,而且,这些写好的代码,肯定是最优秀的实现。

可是我们还是要学,而且是从最笨“冒泡算法”学起。所谓的最笨,是指效率差的。

 

学习的原因:1、前面说了,为了锻炼我们的逻辑思维。2、为了在某些时候,我们可以对排过程做更多的控制。

 

18.2.1 现实算法与程序算法的不同

 

大家都是这么整理扑克牌:把54张摊开放在桌面,然后不断地调整各张牌的位置,并把已经有序的牌放到另外一个位置。

生活中的各种算法一般不用考虑“内存”的问题。比如上面的问题,54牌每一张都要占用一点桌面,这算是固定需要的内存,而在“腾挪”各张牌,使之渐渐变得有序的过程中,还需要开辟新的空间,包括手里抓着的牌,即手心也算是一个内存。

程序排序,要求既要占用内存少,又要速度快。这是衡量一个算法是否优秀的两个基本点。

 

若是应用到人整理牌这一例子,则除了实现将54张牌按次序(牌值和牌花)排好以外,还需另有要求:

1、除了54张牌一开始占用的桌面,及你的一个手心以外,你在整理的过程中,不能让牌再占用新的桌面空间。

2、要求“比较两张牌大小”“交换两张的位置”等过程都尽量地少。

 

你可以拿出家里的扑克牌,现在就开始按上面的要求进行手工排序。也可以下载网站上的“扑克排序”的程序,通过它来模拟手工排序:鼠标点击某一张牌,该牌将移到当前的空位上。(正工学员下载课程包中已含该程序)

 

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……对调,于是:21435 <----- 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 : 该数组的元素个数

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分。)

 

关于这一章,怎么说呢?算法是值得大家慢慢推敲的一章,因此,本章是值得花工夫的,但如果你觉得有困难,也是正常的。关于在于一个“慢慢”,我说的“慢慢”就是:“长期地,连续地,一点点来”——“就是: 循!序!渐!进!啦!”台下有个同学暴吼。