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 로 줄어든다.