数据结构之冒泡排序

冒泡排序算法的原理如下： 相邻比较的元素。n个元素比较n-1次。

可以分为两种比较方式。

第一种：重者沉，从第一个元素开始比较 ，如果第一个比第二个大，就交换他们两个，否则，就不交换位置，然后再第二个比第三个比较大小···，依次向后比较，直到没有任何一对数字需要比较。

第二种：轻者浮，从最后一个元素开始比较 ，如果第n个比第n-1个小，就交换他们两个，否则，就不交换位置，然后再第n-1个比第n-2个比较大小···，依次向后比较，直到没有任何一对数字需要比较。

具体代码实现的方式有很多种

博主这里以顺序表冒泡排序为例

//基于顺序表的冒泡排序
#include <stdio.h>
#define LISTSIZE 100    // LISTSIZE 表示顺序表可能的最大数据元素数目

/****** 顺序表存储结构 ******/
typedef struct
{
    int list[LISTSIZE];
    int length;
}SqList;

//初始化顺序表
int InitList(SqList* L)   
{
    L->length = 0;
    return 1;
}

//求顺序表表长
int ListLenth(SqList L)                
{
    return L.length;
}

//判断顺序表是否为空
int ListEmpty(SqList L)   
{
    if (L.length <= 0)
    {
        return 1;
    }
     return 0;
}

//向顺序表插入元素 
int ListInsert(SqList* L, int pos, int item)
{         
    int i;

    if (L->length >= LISTSIZE) 
    {
        printf("顺序表已满，无法插入\n");
        return 0;
    }

    if (pos <= 0 || pos > L->length + 1)
    {                                // 检查元素插入位置是否在顺序表里
        printf("插入位置不合法\n");
        return 0;
    }

    for (i = L->length - 1; i >= pos - 1; i--)
    {                                // 移动数据元素
        L->list[i + 1] = L->list[i];
    }

    L->list[pos - 1] = item;        // 插入元素
    L->length++;                    // 表长加一

    return 1;
}

// 遍历顺序表
int TraverList(SqList L)
{
    int i;
    for (i = 0; i < L.length; i++)
    {
        printf("%d ", L.list[i]);
    }
    printf("\n");
    return 1;
}
// 交换位置函数 ，可以不单独写出来，在用的时候再写
void swap(SqList* L, int i, int j)
{
    int temp = L->list[i];
    L->list[i] = L->list[j];
    L->list[j] = temp;
}
// 冒泡排序之重者沉
//void BubbleSort(SqList* L)
//{
//    int i, j, over;
//    for (i = 0; i < L->length - 1; i++)
//    {
//        over = 1;
//        for (j = 0; j < L->length - i - 1; j++)
//        {
//            if (L->list[j] > L->list[j + 1])
//            {
//                swap(L, j, j + 1);
//                over = 0;
//            }
//        }
//        if (over)
//        {
//            break;
//        }
//        TraverList(*L);
//    }
//}
//冒泡排序之轻者浮
void BubbleSort(SqList* L)
{
    int i, j, over;
    for (i = 0; i < L->length - 1; i++)
    {
        over = 1;
        for (j = L->length - 1; j > 0; j--) // 这里需要注意j
        {
            if (L->list[j - 1] > L->list[j])
            {
                swap(L, j - 1, j);
                over = 0;
            }
        }
        if (over)
        {
            break;
        }
        TraverList(*L);
    }
}
int main()
{
    SqList L;
    int x;
    char ch;
    int pos = 1;
    InitList(&L);
    do
    {
        scanf_s("%d", &x);
        ListInsert(&L, pos++, x);
    } while ((ch = getchar()) != '\n');
    BubbleSort(&L);
    printf("The sorted List is\n");
    TraverList(L);
    return 0;
}

执行代码如图

重者沉

轻者浮