Blog's Home-数据结构-内排序

根据待排序的记录是否全部被放置在内存中，排序可分为：内排序和外排序。

内排序是指在排序过程中，待排序记录全部被放置在内存中。外排序是由于排序记录数量太多，不能同时放置在内存，排序过程需要在内外存之间多次交换数据才能进行。

这里主要来谈一下内排序中的几种。

首先我们先要有一个用于排序用的顺序表结构体，如下：

#define MAXSIZE 10         //用于要排序数组元素个数的最大值，可根据需要修改    
typedef struct    
{
    int r[MAXSIZE + 1];    //用于存储被排序数据的数组，r[0]用作哨兵或临时变量
    int length;            //用于记录顺序表的长度
}SqList;                   //结构体定义

/*交换元素函数，经常用到*/
void swap(SqList *L, int i, int j)
{
    int temp = L->r[i];        //中间变量
    L->r[i] = L->r[j];
    L->r[j] = temp;
}

1、冒泡排序(Bubble Sort)

基本思想：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

算法代码(C语言版)：

void BubbleSort(SqList *L)
{
    int i, j;
    for(i = 1; i < L->length; i++)                /*第1轮比完后，最小数放在r[1]，r[1]不需要再比，i从2开始，每当比完一轮，就将当前一轮比较数中最小的数放在这一轮比较数的下标最小的地方，然后i加1，再从新的i开始*/ 
    {
        for(j = L->length-1; j >= i; j--)        //先最后两个比，再倒数第2与第3比，再倒数第3与第4比，如此类推
        {
            if(L->r[j] > L->r[j + 1])            //如果反序，则交换
            {
                swap(L, j, j + 1);
            }
        }
    }
}

假设我们排序的关键字序列是{9， 1， 5， 8， 3， 7， 4， 6， 2}，如下图所示，图中较小的数字如同气泡般慢慢浮到上面，因此就将此算法全名为冒泡算法。