冒泡排序

　　冒泡排序并没有时间复杂度比O(n^2)更好的算法，但是在具体实现上还是可以优化的，常见的如下所示代码：

//对单链表可以使用 
void Bubble_Sort(Elemtype A[],int N)
{
    int i,j;
    for(i=N-1;i>=0;--i)
    {
        int flag = 0;
        for(j=0;j<i;++j)
        {
            if(A[j]>A[j+1])//稳定的 
            {
                swap(&A[j],&A[j+1]);
                flag = 1;
            }
        }
        if(flag==0) break;
    }
}

　　这是通过flag标志位优化的代码，当一次遍历时，没有元素交换，那么就表示冒泡排序已完成。

　　下面这段代码是用一个lastSwapPos保存上一次遍历过程中最后交换的两个元素的第一个，因为lastSwapPos后面的元素都已经是有序的了，所以下一次遍历只要到lastSwapPos这个位置就行了。

　　比如数列2,1,3,4,7,6,5,8,9，进行冒泡排序;

　　第一次遍历后：1,2,3,4,6,5,7,8,9;lastSwapPos指向5，下一次遍历只要进行到5就可以结束。

                                     î

　　　　　　　　　　    lastSwapPos

void BubbleSort(Elemtype *A,int n)
{
    int lastSwapPos = n-1;
    while(lastSwapPos>0){
        int tempPos = lastSwapPos;
        lastSwapPos = 0;
        for(int i=0;i<tempPos;++i){
            if(A[i]>A[i+1]){
                int temp = A[i];
                A[i] = A[i+1];
                A[i+1] = temp;
                lastSwapPos = i;
            }
        }
    }
}

　　在对于基本有序的数列进行排序时，第二段代码有一定的优势。