正文

转用Visual C++实现排序算法大全2007-12-19 15:58:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/sword2008/31495.html

分享到:

 1.引言

  2005年10月25~26日,包括笔者在内的十多位成员组队参加了武汉原动力的野外拓展(Outward Bound)。在攀岩悬崖之前,教官组织了这样的一个游戏项目:

  教官将团队里的所有成员分开,然后用布条蒙上大家的眼睛,接着给每人一个3位或4位的数字。他要求成员们蒙着眼睛集合,在不说话也看不到彼此的情况下,在限定的时间内,按所分得数字的大小顺序排成一条线。

  要成功地完成这个游戏的确有相当的难度,成员们唯一可以借助的分辨彼此大小的手段可能是摸手指、拍肩膀或跺脚等,而要在限定的时间内分别出所有的大小并排成一条线却依赖一个好的排序算法。 最后我们团队失败了,我们这群都有一定数据结构和算法学习背景的所谓IT人败在了这个游戏的面前。最后,教官对我们进行了一番“团队合作精神如此重要”之类的教育云云。

  本文对排序算法的全面论述将从这个游戏说开去,并用Visual C++ 6.0编写一个示例工程以动画演示这个游戏中的成员以各种算法实现成功排序的过程。排序算法是数据结构学科的经典内容,也是计算机科学中最重要的研究问题之一。由于它的应用广泛和固有的理论上的重要性,2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一。对于排序的研究既有理论上的重要意义,又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。 常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。在演示完各种排序算法的动态过程后,本文将给出面对特定问题时选用合适排序算法的原则。

 
 2.演示工程

  单击此处下载演示工程。

  以Visual C++编写一个基于对话框的程序,我们假设待排序的队员的总数为10,排序的整个过程为(每个步骤对应一个菜单):

  (1)队员分散:模拟教官将队员分散开来的过程

   对应的菜单为:IDM_Disperse_Member

   菜单标题为:队员分散 (2)分配数字:模拟教官给每个队员一个3位或4位的数字的过程

   对应的菜单为:IDM_CREAT_NUMBER

   菜单标题为:产生数字

  (3)集合:所有成员在获得数字后,为进行排序,他们需要先集合

   对应的菜单为:IDM_Muster_Member

   菜单标题为:队员集合

  (4)排序:成员们依据摸手指、拍肩膀或跺脚等手段进行由小到大的排序,又依据排序算法分为:

   a.冒泡法

    对应的菜单为:IDM_Bubble_Sort

   b.交换排序

    对应的菜单为:IDM_Exchange_Sort

   c.选择排序

    对应的菜单为:IDM_Selection_Sort

   d.插入排序

    对应的菜单为:IDM_INSERT_SORT

   e.快速排序

   对应的菜单为:IDM_QUICK_SORT

   整个对话框的消息映射关系为:

BEGIN_MESSAGE_MAP ( CSortDlg, Cdialog )

//{{AFX_MSG_MAP ( CSortDlg )
  ON_WM_SYSCOMMAND()
  ON_WM_PAINT()
  ON_WM_QUERYDRAGICON()
  ON_COMMAND ( IDM_Disperse_Member, OnDisperseMember )
  ON_COMMAND ( IDM_CREAT_NUMBER, OnCreatNumber )
  ON_COMMAND ( IDM_Muster_Member, OnMusterMember )
  ON_COMMAND ( IDM_Bubble_Sort, OnBubbleSort )
  ON_COMMAND ( IDM_Exchange_Sort, OnExchangeSort )
  ON_COMMAND ( IDM_Selection_Sort, OnSelectionSort )
  ON_COMMAND ( IDM_INSERT_SORT, OnInsertSort )
  ON_COMMAND ( IDM_QUICK_SORT, OnQuickSort )
//}}AFX_MSG_MAP

END_MESSAGE_MAP()
  “队员分散”实现的功能是将10个成员均匀分散在一个大圆周上(以一个小正方形模拟一个成员,这些成员的名字为0~9),其源代码为:
void CSortDlg::OnDisperseMember()
{
  CRect rect;
  GetClientRect(&rect);
  CClientDC dc(this);
  dc.SetBkColor(RGB(180, 180, 180));
  dc.FillRect(&rect, &CBrush(RGB(180, 180, 180)));

  //将待排序的对象分散在一个圆上
 
  for (int i = 0; i < SORT_OBJECT_NUM; i++)
  {
   //绘制边框
   dc.DrawEdge(&CRect(rect.right / 2+150 * cos(2 *PI * i / 10.0) - 10,
   rect.bottom / 2+150 * sin(2 *PI * i / 10.0) - 10, rect.right / 2+150 *
   cos(2 *PI * i / 10.0) + 10, rect.bottom / 2+150 * sin(2 *PI * i / 10.0) +10), BDR_RAISEDINNER, BF_RECT);
   //显示名称

   CString strName;
   strName.Format("%d", i);
   dc.TextOut(rect.right / 2+150 * cos(2 *PI * i / 10.0) - 5, rect.bottom / 2+150 * sin(2 *PI * i / 10.0) - 8, strName);
  }
}
   图1给出了队员分散后的显示结果。


图1 队员分散

   “分配数字”实现的是给每个成员随机的分配一个3位或4位的数字,其源代码为:
void CSortDlg::OnCreatNumber()
{
  CRect rect;
  GetClientRect(&rect);
  CClientDC dc(this);
  dc.SetBkColor(RGB(180, 180, 180));
  // Seed the random-number generator with current time

  srand((unsigned)time(NULL));

  //产生SORT_OBJECT_NUM个3/4位的数

  for (int i = 0; i < SORT_OBJECT_NUM; i++)
  {
   int temp;
   temp = rand();
   if (temp % 2 == 0)
   //产生3位数
   {
    while (temp % 1000 < 100)
    {
     temp = rand();
    }
    sortObject[i].iNumber = temp % 1000;
   }
   else
   //产生4位数
   {
    while (temp % 10000 < 1000)
    {
     temp = rand();
    }
    sortObject[i].iNumber = temp % 10000;
   }

   //初始化序号和名称

   sortObject[i].iName = i;
   sortObject[i].iSeq = i;

   //显示获得的数字

   CString strNum;
   strNum.Format("%4d", sortObject[i].iNumber);
   dc.TextOut(rect.right / 2+150 * cos(2 *PI * i / 10.0) - 15, rect.bottom / 2+150 * sin(2 *PI * i / 10.0) - 30, strNum);
  }
}
  图2给出了分配数字后的显示结果。


图2 分配数字

  “队员集合”实现的功能是将所有成员一字排开,其源代码为:
void CSortDlg::OnMusterMember()
{
  CClientDC dc (this) ;
  CRect rect;
  GetClientRect(&rect) ;
  InitObjectCoord(rect);//初始化一字排开的坐标

  dc.SetBkColor(RGB(180,180,180));
  dc.FillRect(&rect,&CBrush(RGB(180,180,180)));

  for(int i=0;i<SORT_OBJECT_NUM;i++)
  {
   //绘制外框
   dc.DrawEdge(&CRect(
    objectCoord[i].x-10,objectCoord[i].y-10,objectCoord[i].x+10,objectCoord[i].y+10),BDR_RAISEDINNER,
BF_RECT);

   //显示名称

   CString strName;
   strName.Format("%d",i);
   dc.TextOut(objectCoord[i].x-5,
   objectCoord[i].y-8,strName);

   //显示获得的数字

   CString strNum;
   strNum.Format("%4d",sortObject[i].iNumber);
   dc.TextOut(objectCoord[i].x-15,objectCoord[i].y-30,strNum);
  }
}
  其中所调用的InitObjectCoord函数获取一字排开时所均匀分配的坐标,其原型为:
void InitObjectCoord(CRect &clientRect)
{
  for (int i = 0; i < SORT_OBJECT_NUM; i++)
  {
   objectCoord[i].x = 30 +i * (clientRect.right - 60) / (SORT_OBJECT_NUM - 1);
   objectCoord[i].y = clientRect.bottom / 2;
  }
}
  其中的objectCoord定义为:
POINT objectCoord[SORT_OBJECT_NUM];
  图3给出了队员集合后的显示结果。


图3 队员集合


  上述CSortDlg::OnCreatNumber()及CSortDlg::OnMusterMember()函数中用到的sortObject定义为:

SortObject sortObject[SORT_OBJECT_NUM];

  即SortObject数组,而SortObject的含义则为待排序的成员,其定义为:

typedef struct tagSortObject
{
  int iName; //待排序对象名:即0~9
  int iSeq; //排序的序号
  int iNumber; //教官给出的数字
}SortObject;

    3.排序

  3.1冒泡排序

  冒泡排序的名字来源于其工作方式,在这种排序算法中,较小的数一个一个往水面上“冒”,最终所有数均变成了由小到大排列。在冒泡排序算法中我们要对待排序的对象序列进行若干遍处理,处理的过程是:自底向上检查序列,并比较相邻对象的大小。如果发现两个相邻对象的顺序不对(较小对象在后面),就交换它们的位置。经过一遍处理之后,最小的对象就“冒”到了最前面的位置;经过第二遍处理,次小的对象又“冒”到了次前位置,依此类推。

void CSortDlg::OnBubbleSort()
{
  CClientDC dc(this);
  dc.SetBkColor(RGB(180, 180, 180));

  int objectName[SORT_OBJECT_NUM]; //每个位置对应的成员名

  //初始化每个位置对应的成员

  for (int i = 0; i < SORT_OBJECT_NUM; i++)
  {
   objectName[i] = i;
  }

  //冒泡排序

  for (i = 1; i < SORT_OBJECT_NUM; i++)
  {
   for (int j = SORT_OBJECT_NUM - 1; j >= i; j--)
   {
    if (sortObject[objectName[j]].iNumber < sortObject[objectName[j -1]].iNumber)
    {
     //交换成员序号
     int iTemp;
     iTemp = sortObject[objectName[j - 1]].iSeq;
     sortObject[objectName[j - 1]].iSeq = sortObject[objectName[j]].iSeq;
     sortObject[objectName[j]].iSeq = iTemp;

     //交换成员位置

     iTemp = objectName[j];
     objectName[j] = objectName[j - 1];
     objectName[j - 1] = iTemp;

     //显示新位置

     CString strName;
     CString strNum;

     //显示j-1位置的成员

     strName.Format("%d", objectName[j - 1]);
     dc.TextOut(objectCoord[sortObject[objectName[j - 1]].iSeq].x - 5,
     objectCoord[sortObject[objectName[j - 1]].iSeq].y - 8, strName);

     if (sortObject[objectName[j - 1]].iNumber < 1000)
      {
      strNum.Format(" %d", sortObject[objectName[j - 1]].iNumber);
     }
     else
     {
      strNum.Format("%d", sortObject[objectName[j - 1]].iNumber);
     }
     dc.TextOut(objectCoord[sortObject[objectName[j - 1]].iSeq].x - 15,
       objectCoord[sortObject[objectName[j - 1]].iSeq].y - 30, strNum);
     //显示j位置的成员

     strName.Format("%d", objectName[j]);
     dc.TextOut(objectCoord[sortObject[objectName[j]].iSeq].x - 5,objectCoord[sortObject[objectName[j]].iSeq].y - 8, strName);

     if (sortObject[objectName[j]].iNumber < 1000)
     {
      strNum.Format(" %d", sortObject[objectName[j]].iNumber);
     }
     else
     {
      strNum.Format("%d", sortObject[objectName[j]].iNumber);
     }
     dc.TextOut(objectCoord[sortObject[objectName[j]].iSeq].x - 15,
objectCoord[sortObject[objectName[j]].iSeq].y - 30, strNum);

     //延迟1秒进行下一次排序以便将排序过程显示为动画
     Sleep(1000);
    }
   }
  }
}
  通过运行上述程序,我们非常清晰地看到了较小的数冒泡的全过程,这是缘于我们在每次排序之间利用Sleep(1000)插入了1秒钟的延迟。下面是我们追踪所得的一次冒泡排序的轨迹:
196 3993 2037 2953 318 2815 5770 960 7325 486
196 3993 2037 2953 318 2815 5770 960 486 7325
196 3993 2037 2953 318 2815 5770 486 960 7325
196 3993 2037 2953 318 2815 486 5770 960 7325
196 3993 2037 2953 318 486 2815 5770 960 7325
196 3993 2037 318 2953 486 2815 5770 960 7325
196 3993 318 2037 2953 486 2815 5770 960 7325
196 318 3993 2037 2953 486 2815 5770 960 7325
196 318 3993 2037 2953 486 2815 960 5770 7325
196 318 3993 2037 2953 486 960 2815 5770 7325
196 318 3993 2037 486 2953 960 2815 5770 7325
196 318 3993 486 2037 2953 960 2815 5770 7325
196 318 486 3993 2037 2953 960 2815 5770 7325
196 318 486 3993 2037 960 2953 2815 5770 7325
196 318 486 3993 960 2037 2953 2815 5770 7325
196 318 486 960 3993 2037 2953 2815 5770 7325
196 318 486 960 3993 2037 2815 2953 5770 7325
196 318 486 960 2037 3993 2815 2953 5770 7325
196 318 486 960 2037 2815 3993 2953 5770 7325
196 318 486 960 2037 2815 2953 3993 5770 7325
  仔细的观察上述过程可以帮助我们更好地理解冒泡排序的内涵。下面的动画(GIF格式)演示了冒泡排序的过程:


(编者注:本图为动画,请设置IE浏览器:工具->internet->高级->多媒体,选择播放网页中的动画,即可观看,后同)


  对于n个待排序成员,冒泡排序需要进行n(n-1)/2次比较,平均情况下需进行3n(n-1)/4次交换;因为每交换一对不合顺序的元素,需进行三次操作,所以最坏情况下,交换次数是比较次数的三倍,即3n(n-1)/2 。因此,冒泡法是效率最差的排序方法,一般只适合于数组较小的情况。

  因此,有学者提出了“拉锯法”、“双边冒泡法”等改进措施。“拉锯法”不再是总按同一方向读数组元素,而是这一遍从下到上把最小的送到最前面,下一遍从上到下把最大的元素送到最后面;“双边冒泡法”则每次除了冒出最小元素外,还“下沉”最大元素。

   3.2交换排序

  交换排序的基本思想是对待排序的对象序列进行n-1遍处理,第i遍处理的过程为:将对象i~对象n-1与对象i-1进行比较,若其较小,则与i-1对象交换位置;经过i遍处理之后,前i个对象就是顺序排列的了。

void CSortDlg::OnSelectionSort()
{
  CClientDC dc (this) ;
  dc.SetBkColor(RGB(180,180,180));
  int objectName[SORT_OBJECT_NUM]; //每个位置对应的成员名

  //初始化每个位置对应的成员

  for (int i = 0; i < SORT_OBJECT_NUM; i++)
  {
   objectName[i] = i;
  }

  //交换排序

  for(i=0;i<SORT_OBJECT_NUM;i++)
  {
   for(int j=i+1;j<SORT_OBJECT_NUM;j++)
   {
    if(sortObject[objectName[j]].iNumber <sortObject[objectName[i]].iNumber)
    {
     //交换成员序号
     int iTemp;
     iTemp = sortObject[objectName[j]].iSeq;
     sortObject[objectName[j]].iSeq =sortObject[objectName[i]].iSeq;
     sortObject[objectName[i]].iSeq = iTemp;

     //交换成员位置
     iTemp = objectName[j];
     objectName[j] = objectName[i];
     objectName[i] = iTemp;

     //显示新位置

     CString strName;
     CString strNum;
     //显示j位置的成员

     strName.Format("%d",sortObject[objectName[j]].iName);
     dc.TextOut(objectCoord[sortObject[objectName[j]].iSeq].x-5,
     objectCoord[sortObject[objectName[j]].iSeq].y-8,strName);

     if(sortObject[objectName[j]].iNumber<1000)
     {
      strNum.Format(" %d",sortObject[objectName[j]].iNumber);
     }
     else
     {
      strNum.Format("%d",sortObject[objectName[j]].iNumber);
     }
     dc.TextOut(objectCoord[sortObject[objectName[j]].iSeq].x-15,
       objectCoord[sortObject[objectName[j]].iSeq].y-30,strNum);
     //显示i位置的成员

     strName.Format("%d",sortObject[objectName[i]].iName);
     dc.TextOut(objectCoord[sortObject[objectName[i]].iSeq].x-5,objectCoord[sortObject[objectName[i]].iSeq].y-8,strName);

     if(sortObject[objectName[i]].iNumber<1000)
     {
      strNum.Format(" %d",sortObject[objectName[i]].iNumber);
     }
     else
     {
      strNum.Format("%d",sortObject[objectName[i]].iNumber);
     }
     dc.TextOut(objectCoord[sortObject[objectName[i]].iSeq].x-15,
      objectCoord[sortObject[objectName[i]].iSeq].y-30,strNum);

     //延迟1秒进行下一次排序以便将排序过程显示为动画 Sleep(1000);
    }
   }
  }
}

  下面是我们追踪所得的一次交换排序的轨迹:
7449 318 964 396 4973 1431 6541 2331 1489 3743
318 7449 964 396 4973 1431 6541 2331 1489 3743
318 964 7449 396 4973 1431 6541 2331 1489 3743
318 396 7449 964 4973 1431 6541 2331 1489 3743
318 396 964 7449 4973 1431 6541 2331 1489 3743
318 396 964 4973 7449 1431 6541 2331 1489 3743
318 396 964 1431 7449 4973 6541 2331 1489 3743
318 396 964 1431 4973 7449 6541 2331 1489 3743
318 396 964 1431 2331 7449 6541 4973 1489 3743
318 396 964 1431 1489 7449 6541 4973 2331 3743
318 396 964 1431 1489 6541 7449 4973 2331 3743
318 396 964 1431 1489 4973 7449 6541 2331 3743
318 396 964 1431 1489 2331 7449 6541 4973 3743
318 396 964 1431 1489 2331 6541 7449 4973 3743
318 396 964 1431 1489 2331 4973 7449 6541 3743
318 396 964 1431 1489 2331 3743 7449 6541 4973
318 396 964 1431 1489 2331 3743 6541 7449 4973
318 396 964 1431 1489 2331 3743 4973 7449 6541
318 396 964 1431 1489 2331 3743 4973 6541 7449
  下面的动画(GIF格式)演示了交换排序的过程:


  交换排序的时间复杂度为O(n2),其比较次数与下文要介绍的选择排序相同,但是其交换次数比选择排序大,因此不推荐使用这种排序算法。

    3.3选择排序

  由前文可知,交换排序的特点是每次用当前的对象一一与其后对象比较并交换。选择排序与交换排序类似,但是它并不是用当前对象与其后对象一一比较,而是直接以当前对象以后的最小对象与当前对象比较并交换,因而可以提高算法的时间性能。

void CSortDlg::OnSelectionSort()
{
  CClientDC dc (this) ;
  dc.SetBkColor(RGB(180,180,180));
  int objectName[SORT_OBJECT_NUM]; //每个位置对应的成员名

  //初始化每个位置对应的成员

  for(int i=0;i<SORT_OBJECT_NUM;i++)
  {
   objectName[i] = i;
  }

  //选择排序

  for(i=0;i<SORT_OBJECT_NUM;i++)
  {
   int iPos;
   iPos = i;
   for(int j=i+1;j<SORT_OBJECT_NUM;j++)
   {
    if(sortObject[objectName[j]].iNumber <sortObject[objectName[iPos]].iNumber)
    {
     iPos = j;
    }
   }
   if(iPos!=i)
   {
    //交换序号
    int iTemp;
    iTemp = sortObject[objectName[iPos]].iSeq;
    sortObject[objectName[iPos]].iSeq = sortObject[objectName[i]].iSeq;
    sortObject[objectName[i]].iSeq = iTemp;

    //交换成员名

    iTemp = objectName[iPos];
    objectName[iPos] = objectName[i];
    objectName[i] = iTemp;

    //显示变化

    CString strName;
    CString strNum;

    //对象iPos
    strName.Format("%d",sortObject[objectName[iPos]].iName);
    dc.TextOut(objectCoord[sortObject[objectName[iPos]].iSeq].x-5,
      objectCoord[sortObject[objectName[iPos]].iSeq].y-8,strName);
    if(sortObject[objectName[iPos]].iNumber<1000)
    {
     strNum.Format(" %d",sortObject[objectName[iPos]].iNumber);
    }
    else
    {
     strNum.Format("%d",sortObject[objectName[iPos]].iNumber);
    }
    dc.TextOut(objectCoord[sortObject[objectName[iPos]].iSeq].x-15,
      objectCoord[sortObject[objectName[iPos]].iSeq].y-30,strNum);

    //对象i

    strName.Format("%d",sortObject[objectName[i]].iName);
    dc.TextOut(objectCoord[sortObject[objectName[i]].iSeq].x-5,
    objectCoord[sortObject[objectName[i]].iSeq].y-8,strName);
    if(sortObject[objectName[i]].iNumber<1000)
    {
     strNum.Format(" %d",sortObject[objectName[i]].iNumber);
    }
    else
    {
     strNum.Format("%d",sortObject[objectName[i]].iNumber);
    }
    dc.TextOut(objectCoord[sortObject[objectName[i]].iSeq].x-15,
      objectCoord[sortObject[objectName[i]].iSeq].y-30,strNum);

    //延迟1秒进行下一次排序以便将排序过程显示为动画

    Sleep(1000);
   }
  }
}
  下面是我们追踪所得的一次选择排序的轨迹:
5919 280 1617 4375 332 1467 158 9599 342 496
158 280 1617 4375 332 1467 5919 9599 342 496
158 280 332 4375 1617 1467 5919 9599 342 496
158 280 332 342 1617 1467 5919 9599 4375 496
158 280 332 342 496 1467 5919 9599 4375 1617
158 280 332 342 496 1467 1617 9599 4375 5919
158 280 332 342 496 1467 1617 4375 9599 5919
158 280 332 342 496 1467 1617 4375 5919 9599
  下面的动画(GIF格式)演示了选择排序的过程:


  选择排序法总的比较次数是n(n-1)/2次,但其交换次数有所减少。最坏情况下的交换次数接近于比较次数,为〔n2/ 4+3(n-1)〕;平均情况下交换次数为〔n*ln(n+u)〕,其中u 是尤拉常数,约为0. 577216。

   3.4插入排序

  插入排序的基本思想是,经过i-1遍处理后,对象0~i-1己排好序,第i遍处理的过程是将对象i插入对象0~i-1之间的适当位置,使得对象0~i又是排好序的序列。

void CSortDlg::OnInsertSort()
{
  CClientDC dc(this);
  dc.SetBkColor(RGB(180, 180, 180));
  int objectName[SORT_OBJECT_NUM]; //每个位置对应的成员名

  //初始化每个位置对应的成员

  for (int i = 0; i < SORT_OBJECT_NUM; i++)
  {
   objectName[i] = i;
  }

  //插入排序

  for (i = 1; i < SORT_OBJECT_NUM; i++)
  {
   int iPos = i - 1;
   int iName = objectName[i];
   CString strName, strNum;
   while (iPos >= 0 && sortObject[iName].iNumber < sortObject[objectName[iPos]].iNumber)
   {
    objectName[iPos + 1] = objectName[iPos];
    sortObject[objectName[iPos]].iSeq += 1;
    //显示iPos+1位置的对象
    strName.Format("%d", objectName[iPos + 1]);
    dc.TextOut(objectCoord[iPos + 1].x - 5, objectCoord[iPos + 1].y - 8,strName);
    if (sortObject[objectName[iPos + 1]].iNumber < 1000)
    {
     strNum.Format(" %d", sortObject[objectName[iPos + 1]].iNumber);
    }
    else
    {
     strNum.Format("%d", sortObject[objectName[iPos + 1]].iNumber);
    }
    dc.TextOut(objectCoord[iPos + 1].x - 15, objectCoord[iPos + 1].y - 30,strNum);

    iPos--;
    Sleep(1000);
   }
   objectName[iPos + 1] = iName;
   sortObject[objectName[iPos + 1]].iSeq = iPos + 1;
   //显示iPos+1位置的对象
   strName.Format("%d", objectName[iPos + 1]);
   dc.TextOut(objectCoord[iPos + 1].x - 5, objectCoord[iPos + 1].y - 8,strName);
   if (sortObject[objectName[iPos + 1]].iNumber < 1000)
   {
    strNum.Format(" %d", sortObject[objectName[iPos + 1]].iNumber);
   }
   else
   {
    strNum.Format("%d", sortObject[objectName[iPos + 1]].iNumber);
   }
   dc.TextOut(objectCoord[iPos + 1].x - 15, objectCoord[iPos + 1].y - 30,strNum);
   Sleep(1000);
  }
}
  下面是我们追踪所得的一次插入排序的轨迹:
262 738 1699 4875 270 228 706 102 1787 1565
262 738 1699 4875 270 228 706 102 1787 1565
262 738 1699 4875 270 228 706 102 1787 1565
262 738 1699 4875 270 228 706 102 1787 1565
262 270 738 1699 4875 228 706 102 1787 1565
228 262 270 738 1699 4875 706 102 1787 1565
228 262 270 706 738 1699 4875 102 1787 1565
102 228 262 270 706 738 1699 4875 1787 1565
102 228 262 270 706 738 1699 1787 4875 1565
102 228 262 270 706 738 1565 1699 1787 4875
  下面的动画(GIF格式)演示了插入排序的过程:


  插入排序法的比较次数和交换次数与被排序数组的初始顺序情况有关:在最好、最坏、平均三种情况下,总的比较次数分别是(n-1)、(n2+n-2)/4、(n2+n)/2-1,总的交换次数是总比较次数减去n-1,它在最佳情况下为0,在最差及平均情况下为O(n2)。由此看出,在最坏情况下,插入排序法的交换次数与冒泡法、选择法一样糟糕,其执行时间和n2成正比。

  D. L. Shell 发明了希尔(Shell)排序算法,该算法的基本思路是插入排序。希尔排序又称为缩小增量法,它的做法是先取定一个正整数d1 < n,把全部记录分成d1 个组,所有距离为d1倍数的记录放在一个组中,在个组内进行插入排序;然后取d2 < d1 ,重复上述分组和排序工作,直至取di = 1,即所有记录放在一个组中排序为止。大量的实验证明:当n在某个特定范围内时,希尔排序的比较次数和交换次数均为约n1.3。

    3.5快速排序

  Tony Hoare在1962年首次提出了快速排序算法。对快速排序方法的研究表明,至今快速排序算法仍然是流传久远的最实用的排序算法。只在输入数据项有更详细的信息时,其它排序算法才可能胜过快速排序算法快速排序算法是利用分治技术的典型例子,随机分治策略是设计组合优化与计算几何一类问题有效算法的基础。分治策略分为三步:

  (1)将问题分成若干大小基本相等的子问题;

  (2)独立地解决这些子问题;

  (3)将子问题归并成原问题的解。

  快速排序的基本思路是:首先我们选择一个中间值middle(程序中我们可使用数组中间值),把比中间值小的放在其左边,比中间值大的放在其右边。由于这个排序算法较复杂,我们先给出其进行一次排序的程序框架(从各类数据结构教材中可得):

void QuickSort(int *pData, int left, int right)
{
  int i, j;
  int middle, iTemp;
  i = left;
  j = right;

  middle = pData[(left + right) / 2]; //求中间值
  do
  {
   while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数
    i++;
   while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数
    j--;
   if (i <= j) //找到了一对值
   {
    //交换
    iTemp = pData[i];
    pData[i] = pData[j];
    pData[j] = iTemp;
    i++;
    j--;
   }
  } while (i <= j) ; //如果两边扫描的下标交错,就停止(完成一次)

  //当左边部分有值(left<j),递归左半边

  if(left<j)
   QuickSort (pData,left,j);
   //当右边部分有值(right>i),递归右半边
  if(right>i)
   QuickSort (pData,i,right);
}
  由此可见,上述排序算法中采用了递归策略。我们根据上述函数,重新书写一个与我们应用程序框架相符的函数,可动态在对话框客户区显示变化过程:
void QuickSort(int objectName[], CDC &dc, int left, int right)
{
  int i, j;
  int middle, iTemp;
  i = left;
  j = right;

  middle = sortObject[objectName[(left+right)/2]].iNumber; //求中间值
  do
  {
   while ((sortObject[objectName[i]].iNumber < middle) && ( i < right))
    //从左扫描大于中值的数
    i++;
   while ((sortObject[objectName[j]].iNumber > middle)&&(j > left))
    //从右扫描小于中值的数
    j--;
    if (i < j) //找到了一对值
    {
     //交换成员名
     iTemp = objectName[i];
     objectName[i] = objectName[j];
     objectName[j] = iTemp;
     //交换序号
     iTemp = sortObject[objectName[i]].iSeq;
     sortObject[objectName[i]].iSeq = sortObject[objectName[j]].iSeq;
     sortObject[objectName[j]].iSeq = iTemp;
     //显示变化
     CString strName;
     CString strNum;
     //显示位置j的对象
     strName.Format("%d",objectName[j]);
     dc.TextOut(objectCoord[j].x-5,objectCoord[j].y-8,strName);
     if(sortObject[objectName[j]].iNumber<1000)
     {
      strNum.Format(" %d",sortObject[objectName[j]].iNumber);
     }
     else
     {
      strNum.Format("%d",sortObject[objectName[j]].iNumber);
     }
     dc.TextOut(objectCoord[j].x-15,objectCoord[j].y-30,strNum);
     //显示位置i的对象
     strName.Format("%d",objectName[i]);
     dc.TextOut(objectCoord[i].x-5,objectCoord[i].y-8,strName);
     if(sortObject[objectName[i]].iNumber<1000)
     {
      strNum.Format(" %d",sortObject[objectName[i]].iNumber);
     }
     else
     {
      strNum.Format("%d",sortObject[objectName[i]].iNumber);
     }
     dc.TextOut(objectCoord[i].x-15,objectCoord[i].y-30,strNum);
     Sleep(1000);
     i++;
     j--;
    }
    else if (i==j)
    {
     i++;
     j--;
    }
   } while (i <= j) ; //如果两边扫描的下标交错,就停止(完成一次)
   //当左边部分有值(left<j),递归左半边
   if(left<j)
    QuickSort (objectName,dc,left,j);
    //当右边部分有值(right>i),递归右半边 if(right>i)
    QuickSort (objectName,dc,i,right);
  }
  上述函数相对于原始的快速排序函数增加了两个参数:int objectName[], CDC &dc,前者用于记录某位置对应的对象名,后者用于记录设备上下文,以便显示排序的动态过程。下面给出了这个函数的调用:
void CSortDlg::OnQuickSort()
{
  CClientDC dc(this) ;
  dc.SetBkColor(RGB(180,180,180));
  int objectName[SORT_OBJECT_NUM]; //每个位置对应的成员名

  //初始化每个位置对应的成员

  for(int i=0;i<SORT_OBJECT_NUM;i++)
  {
   objectName[i] = i;
  }
  QuickSort(objectName,dc,0,SORT_OBJECT_NUM-1);
}
  下面是我们追踪所得的一次快速排序的轨迹:
154 1089 9859 564 554 4419 692 456 9359 9703
154 1089 456 564 554 4419 692 9859 9359 9703
154 1089 456 564 554 692 4419 9859 9359 9703
154 554 456 564 1089 692 4419 9859 9359 9703
154 456 554 564 1089 692 4419 9859 9359 9703
154 456 554 564 692 1089 4419 9859 9359 9703
154 456 554 564 692 1089 4419 9703 9359 9859
154 456 554 564 692 1089 4419 9359 9703 9859
  下面的动画(GIF格式)演示了快速排序的过程:


  对于n个成员,快速排序法的比较次数大约为n*logn 次,交换次数大约为(n*logn)/6次。如果n为100,冒泡法需要进行4950 次比较,而快速排序法仅需要200 次,快速排序法的效率的确很高。快速排序法的性能与中间值的选定关系密切,如果每一次选择的中间值都是最大值(或最小值),该算法的速度就会大大下降。快速排序算法最坏情况下的时间复杂度为O(n2),而平均时间复杂度为O(n*logn)。

  4.总结

  冒泡排序、选择排序和插入排序等的时间复杂性是O(n2),快速排序、堆排序和归并排序等高级排序算法的时间复杂度为O(n*logn),因此后者的排序效率较高。但这并不意味着总是要使用高级排序算法,下面给出各种排序算法选用的一般原则:

  (1)当数据量不大时选插入或选择排序,不要用冒泡排序;

  事实上,冒泡排序虽然简单,但的确是最不宜采用的排序算法,因为其性能表现是最差的。

  (2)当数据量大而又注重时间复杂度时选快速或堆排序等;

  堆排序的设计思路是:定义堆为一个键值序列{k1 ,k2 ,…,kn},它具有如下特性:ki < = k2i,ki < = k2i + 1 (i = 1 ,2 ,…, [ n/ 2 ]) 。对一组待排序的键值,首先把它们按堆的定义排列成一个序列(称为初建堆),这就找到了最小键值。然后将最小的键值取出,用剩下的键值再重新建堆,便得到次小键值。如此反复进行,直到把全部键值排好序为止。

  由于快速排序和堆排序算法较复杂,因此在待排序的数据量较小时反而比插入和选择排序慢;

  (3)当要在已排序数据上增加新数据时选插入排序。

  当原有数据本身就有序时,插入排序的性能非常好。在已排序数据上增加新数据时,时间复杂性仅为O(n)。

阅读(3891) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册