C++ 冒泡排序數(shù)據(jù)結(jié)構(gòu)、算法及改進(jìn)算法

冒泡排序是一種簡(jiǎn)單排序。這種排序是采用“冒泡策略”將最大元素移到最右邊。在冒泡過程中，相鄰兩個(gè)元素比較，如果左邊大于右邊的，則進(jìn)行交換兩個(gè)元素。這樣一次冒泡后，可確保最大的在最右邊。然后執(zhí)行n次冒泡后排序即可完畢。

程序代碼如下：

// BubbleSort.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。

//

#include "stdafx.h"
#include <cmath>
#include <iostream>
using namespace std;
#define  MAXNUM 20

template<typename T>
void Swap(T& a, T& b)
{
    int t = a;
    a = b;
    b = t;
}
template<typename T>
void Bubble(T a[], int n)
{//把數(shù)組a[0:n-1]中最大的元素通過冒泡移到右邊
    for(int i =0 ;i < n-1; i++)
    {
        if(a[i] >a[i+1])
            Swap(a[i],a[i+1]);
    }
}
template<typename T>
void BubbleSort(T a[],int n)
{//對(duì)數(shù)組a[0:n-1]中的n個(gè)元素進(jìn)行冒泡排序
    for(int i = n;i > 1; i--)
        Bubble(a,i);
}
int _tmain(int argc, _TCHAR* argv[])
{
    int a[MAXNUM];
    for(int i = 0 ;i< MAXNUM; i++)
    {
        a[i] = rand()%(MAXNUM*5);
    }
    
    for(int i =0; i< MAXNUM; i++)
        cout << a[i] << "  ";
    cout << endl;
    BubbleSort(a,MAXNUM);
    cout << "After BubbleSort: " << endl;
    for(int i =0; i< MAXNUM; i++)
        cout << a[i] << "  ";
    cin.get();

    return 0;
}

但是常規(guī)的冒泡，不管相鄰的兩個(gè)元素是否已經(jīng)排好序，都要冒泡，這就沒有必要了，所有我們對(duì)這點(diǎn)進(jìn)行改進(jìn)。設(shè)計(jì)一種及時(shí)終止的冒泡排序算法：

如果在一次冒泡過程中沒有發(fā)生元素互換，則說明數(shù)組已經(jīng)按序排列好了，沒有必要再繼續(xù)進(jìn)行冒泡排序了。代碼如下：

// BubbleSort.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。

//

#include "stdafx.h"
#include <cmath>
#include <iostream>
using namespace std;
#define  MAXNUM 20

template<typename T>
void Swap(T& a, T& b)
{
    int t = a;
    a = b;
    b = t;
}
template<typename T>
bool Bubble(T a[], int n)
{//把數(shù)組a[0:n-1]中最大的元素通過冒泡移到右邊
    bool swapped = false;//尚未發(fā)生交換
    for(int i =0 ;i < n-1; i++)
    {
        if(a[i] >a[i+1])
        {
            Swap(a[i],a[i+1]);
            swapped = true;//發(fā)生了交換
        }
    }
    return swapped;
}
template<typename T>
void BubbleSort(T a[],int n)
{//對(duì)數(shù)組a[0:n-1]中的n個(gè)元素進(jìn)行冒泡排序
    for(int i = n;i > 1 && Bubble(a,i); i--);
}
int _tmain(int argc, _TCHAR* argv[])
{
    int a[MAXNUM];
    for(int i = 0 ;i< MAXNUM; i++)
    {
        a[i] = rand()%(MAXNUM*5);
    }

    for(int i =0; i< MAXNUM; i++)
        cout << a[i] << "  ";
    cout << endl;
    BubbleSort(a,MAXNUM);
    cout << "After BubbleSort: " << endl;
    for(int i =0; i< MAXNUM; i++)
        cout << a[i] << "  ";
    cin.get();
    return 0;
}

改進(jìn)后的算法，在最壞的情況下執(zhí)行的比較次數(shù)與常規(guī)冒泡一樣，但是最好情況下次數(shù)減少為n-1。