【数据结构与算法】【排序】冒泡排序的代码实现

女爷i 2022-08-13 14:40 200阅读 0赞

冒泡排序是一种交换排序。

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

冒泡排序的要点：

1、两两注意是相邻的两个元素的意思；

2、如果有n个元素，则需要比较n-1次，每一轮减少1次比较；

3、既然叫冒泡排序，那就是从下往上两两比较，所以看上去就跟泡泡往上冒一样。

代码实现：

// Filename: bubble_sort.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    // 交换两个整数的值
    void swap(int *pa, int *pb)
    {
        // 入参有效性由调用函数保证
        int temp = *pa;
        *pa = *pb;
        *pb = temp;
        return;
    }
    
    // 伪冒泡排序
    // n个元素序列的各元素下标：[0, 1, 2, ..., n-2, n-1]
    // 处理方式：
    // 1、首先处理第0个，用第0个和后面的依次比较，反序则交换；
    // 2、然后处理第1个，用第1个和后面的依次比较，反序则交换；
    // 3、依此类推；
    // 4、最后处理第n-2个，用第n-2个和后面的第n-1个比较，反序则交换；
    // 5、处理结束。
    void BubbleSort1(int a[], int n)
    {
        int i, j;
    
        for (i = 0; i < n - 1; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                if (a[i] > a[j]) swap(&a[i], &a[j]);
            }
        }
    
        return;
    }
    
    // 冒泡排序
    // n个元素序列的各元素下标：[0, 1, 2, ..., n-2, n-1]
    // 处理方式：
    // 1、首先处理第0个，从最后两个（第n-2个和第n-1个）开始依次向前进行两两比较，直到第1个和第2个进行比较，反序则交换；
    // 2、然后处理第1个，从最后两个（第n-2个和第n-1个）开始依次向前进行两两比较，直到第2个和第3个进行比较，反序则交换；
    // 3、依此类推；
    // 4、最后处理第n-2个，用第n-2个和第n-1个比较，反序则交换；
    // 5、处理结束。
    void BubbleSort2(int a[], int n)
    {
        int i, j;
    
        for (i = 0; i < n - 1; i++)
        {
            for (j = n - 2; j >= i; j--)
            {
                if (a[j] > a[j + 1]) swap(&a[j], &a[j + 1]);
            }
        }
    
        return;
    }
    
    // 冒泡排序优化版本
    // n个元素序列的各元素下标：[0, 1, 2, ..., n-2, n-1]
    // 处理方式：
    // 1、首先处理第0个，从最后两个（第n-2个和第n-1个）开始依次向前进行两两比较，直到第1个和第2个进行比较，反序则交换；
    // 2、然后处理第1个，从最后两个（第n-2个和第n-1个）开始依次向前进行两两比较，直到第2个和第3个进行比较，反序则交换；
    // 3、依此类推；
    // 4、最后处理第n-2个，用第n-2个和第n-1个比较，反序则交换；
    // 5、处理结束。
    void BubbleSort3(int a[], int n)
    {
        int i, j;
        bool swapflag = true;   // 如果内循环遍历一次发生了交换，则标记为true；如果没有发生交换，则为false，表示后面的数已经有序不需要再比较了
    
        for (i = 0; i < n - 1 && swapflag; i++)
        {
            swapflag = false;
            for (j = n - 2; j >= i; j--)
            {
                if (a[j] > a[j + 1]) swap(&a[j], &a[j + 1]);
                swapflag = true;
            }
        }
    
        return;
    }
    
    // 打印数组
    void PrintArray(int a[], int n)
    {
        int i;
        for (i = 0; i < n; i++)
        {
            printf("%d ", a[i]);
        }
    
        return;
    }
    
    // 冒泡排序主函数
    int BubbleSortMain()
    {
        int a1[10] = {3, 4, 5, 8, 9, 7, 6, 1, 0, 2};
        int a2[10] = {3, 4, 5, 8, 9, 7, 6, 1, 0, 2};
        int a3[10] = {3, 4, 5, 8, 9, 7, 6, 1, 0, 2};
    
        printf("排序前：\n");
        printf("a1: ");
        PrintArray(a1, 10);
        printf("\n");
        printf("a2: ");
        PrintArray(a2, 10);
        printf("\n");
        printf("a3: ");
        PrintArray(a3, 10);
        printf("\n");
    
        BubbleSort1(a1, 10);
        BubbleSort2(a2, 10);
        BubbleSort3(a3, 10);
    
        printf("排序后：\n");
        printf("a1: ");
        PrintArray(a1, 10);
        printf("\n");
        printf("a2: ");
        PrintArray(a2, 10);
        printf("\n");
        printf("a3: ");
        PrintArray(a3, 10);
        printf("\n");
    
        return 0;
    }