程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> C++ 冒泡排序數據結構、算法及改進算法

C++ 冒泡排序數據結構、算法及改進算法

編輯:C語言基礎知識

程序代碼如下:
代碼如下:

// BubbleSort.cpp : 定義控制台應用程序的入口點。
//
#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)
{//把數組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)
{//對數組a[0:n-1]中的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;
}

但是常規的冒泡,不管相鄰的兩個元素是否已經排好序,都要冒泡,這就沒有必要了,所有我們對這點進行改進。設計一種及時終止的冒泡排序算法:

如果在一次冒泡過程中沒有發生元素互換,則說明數組已經按序排列好了,沒有必要再繼續進行冒泡排序了。代碼如下:

代碼如下:

// BubbleSort.cpp : 定義控制台應用程序的入口點。

//
#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)
{//把數組a[0:n-1]中最大的元素通過冒泡移到右邊
    bool swapped = false;//尚未發生交換
    for(int i =0 ;i < n-1; i++)
    {
        if(a[i] >a[i+1])
        {
            Swap(a[i],a[i+1]);
            swapped = true;//發生了交換
        }
    }
    return swapped;
}
template<typename T>
void BubbleSort(T a[],int n)
{//對數組a[0:n-1]中的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;
}

改進後的算法,在最壞的情況下執行的比較次數與常規冒泡一樣,但是最好情況下次數減少為n-1。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved