從趣味遊戲到排序算法(4)

<b>3.3</b><b>選擇排序</b><b></b>

由前文可知，交換排序的特點是每次用目前的對象一一與其後對象比較并交換。選擇排序與交換排序類似，但是它并不是用目前對象與其後對象一一比較，而是直接以目前對象以後的最小對象與目前對象比較并交換，因而可以提高算法的時間性能。

void CSortDlg::OnSelectionSort()

{

      CClientDC dc (this) ;

      dc.SetBkColor(RGB(180,180,180));     

      int objectName[SORT_OBJECT_NUM]; //每個位置對應的成員名

   //初始化每個位置對應的成員

      for(int i=0;i&lt;SORT_OBJECT_NUM;i++)

      {

             objectName[i] = i;

      }

      //選擇排序

      for(i=0;i&lt;SORT_OBJECT_NUM;i++)

             int iPos;

             iPos = i;

             for(int j=i+1;j&lt;SORT_OBJECT_NUM;j++)

             {

                    if(sortObject[objectName[j]].iNumber &lt;

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&lt;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,

                    if(sortObject[objectName[i]].iNumber&lt;1000)

                           strNum.Format("  %d",sortObject[objectName[i]].iNumber);

                           strNum.Format("%d",sortObject[objectName[i]].iNumber);

                    dc.TextOut(objectCoord[sortObject[objectName[i]].iSeq].x-15,

                           objectCoord[sortObject[objectName[i]].iSeq].y-30,

                    //延遲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。

 本文轉自 21cnbao 51CTO部落格，原文連結：http://blog.51cto.com/21cnbao/120742，如需轉載請自行聯系原作者