交换排序------冒泡法 及其优化

上大学学数据结构的时候就学过  冒泡法，   作为比较经典的排序方式由于其时间复杂较高一直作为入门级的算法，虽然冒泡算法在实际应用中较少但是也是有一定的研究价值的，这里给出三种实现，第一种为原始算法时间复杂度为 O（n）;  第二种为加入标志位, 使算法在待排序数据已成有序情况前提前结束；  第三种，记录每一趟排序后最后交换的两个元素中的较小下标并将其作为下次排序的上限， 使算法可以在待排序数据中直接跨过尾部已经有序的数据元素减少比较次数。

冒泡排序原始算法：

#include <iostream>
using namespace std;

template <class T>
void bubbleSort_0(T A[], int n)
{
    for(int i=1; i<n; i++)
    {
        for(int j=0;j<n-i;j++)
        {
            if(A[j]>A[j+1])
            {
                swap(A[j], A[j+1]);
            }
        }
    }
}

加入标志位后：

template <class T>
void bubbleSort_1(T A[], int n)
{
    int flag=1;
    for(int i=1; i<n && flag; i++)
    {
        flag=0;
        for(int j=0;j<n-i;j++)
        {
            if(A[j]>A[j+1])
            {
                swap(A[j], A[j+1]);
                flag=1;
            }
        }
    }
}

记录每一趟最后交换的一对元素中较小的下标

template <class T>
void bubbleSort_2(T A[], int n)
{
    int i, j;
    int lastExchangeIndex;
    i=n-1;
    while(i>0)
    {
        lastExchangeIndex=0;

        for(j=0;j<i;j++)
        {
            if(A[j]>A[j+1])
            {
                swap(A[j], A[j+1]);
                lastExchangeIndex=j;
            }
        }
        i=lastExchangeIndex;
    }
}

主函数：

int main()
{
    int A[]={8, 6, 9, 7, 5, 0, 4, 1, 3, 2};
    int n=10;
    bubbleSort_2(A, n);
    for(int i=0;i<n;i++)
        cout<<A[i]<<" ";
    cout<<endl;
    return 0;
}