C++冒泡排序算法改進篇

排序是在程序設(shè)計中常碰到的問題，排序算法也有很多種。起泡法是眾所周知的排序算法，其原理是每次將相鄰兩個數(shù)進行比較，較大的下沉。其的主程序段如下（用VC++實現(xiàn)）：
    Void Bubble Sort (int* pData,int Count)
    {
    Int iTemp;
    for(int i=1;i    {
    For (int j=Count-1;j>=i;j--)
    {
    if(pData[j]    {
    　iTemp = pData[j-1];
    　pData[j-1] = pData[j];
    　pData[j] = iTemp;
    }
    }
    }
    }
    我們分析上述程序段可以發(fā)現(xiàn)起泡法是從一端開始比較的，第一次循環(huán)就是把最小數(shù)上升到第一位置，第二次循環(huán)就是把第二最小數(shù)上升到第二位置。如此循環(huán)實現(xiàn)數(shù)據(jù)的排序。那么我們是否可以找到最小數(shù)的同時找到數(shù)呢？當然可以。方法是在一端起泡時同時在另一端也進行起泡。即反向起泡。下面的程序段實現(xiàn)的是雙向起泡：
    void Bubble2Sort(int* pData,int Count)
    {
    int iTemp;
    int left = 1;
    int right =Count -1;
    int t;
    do
    {
    //正向的部分
    for(int i=right;i>=left;i--)
    {
    if(pData[i]    {
    　iTemp = pData[i];
    　pData[i] = pData[i-1];
    　pData[i-1] = iTemp;
    　t = i;
    }
    }
    left = t+1;
    //反向的部分
    for(i=left;i    {
    if(pData[i]    {
    　iTemp = pData[i];
    　pData[i] = pData[i-1];
    　pData[i-1] = iTemp;
    　t = i;
    }
    }
    right = t-1;
    }while(left<=right);
    }
    分析上面的程序段我們可以發(fā)現(xiàn)正向起泡時第一次循環(huán)找出了最小數(shù)，反向起泡第一次循環(huán)找到數(shù)。很顯然在一次循環(huán)中即可以找到一個最小的數(shù)還可以找到一個的數(shù)，所以用雙向冒泡排序的交換的次數(shù)減少了，從而達到了優(yōu)化起泡法的作用。