排序之冒泡排序

一、数据结构
        约定排序均为升序排序，要排序的记录存储在线性表中，线性表由排序关键字和其它域组成，其定义如下：
        #define MAXITEM 100
        struct rec
        {
            KeyType key;        // 关键字域
            ElemType data;     // 其它数据域
        };
        struct rec sqlist[MAXITEM];
        这里的KeyType和ElemType可以是任何相应的数据类型，比如int，float或char等，在算法中，约定其为int类型。

二、算法思想
        冒泡排序的基本思想是：通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。整个算法是从最下面的记录开始，对每两个相邻的关键进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟起泡排序后，关键字最小的记录到达最上端，接着，再在剩下的记录中找关键字最小的记录，并把它换在第二个位置上。依次类推，一直到所有记录都有序为止。

三、程序实现
        实现冒泡排序的函数如下：
        void bubblesort(sqlist r, int n)        // 排序元素r[1]~r[n]
        {
            int i, j;
            struct rec w;
            for (i=1; i<=n-1; i++)
            {
                for (j=n; j>i+1; j--)
                {
                    if (r[j].key < r[j-1].key)    // 比较
                    {                                  // r[j]与r[j-1]进行交换
                        w = r[j];
                        r[j] = r[j-1];
                        r[j-1] = w;
                    }
                }
            }
        }
        冒泡排序算法的时间复杂度是O(n^₂)，它是一种稳定的排序方法。