算法（三）-冒泡排序算法

短命女 2022-08-09 05:28 122阅读 0赞

## 冒泡算法原理： ##

将临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束。

## 冒泡排序过程 ##

设想被排序的数组R\[1..N\]垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上”漂浮”（交换位置），如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。

#include <stdio.h>
    void swap(int *a, int *b);
    int main()
    {
        int    array[10] = {
       15, 225, 34, 42, 52, 6, 7856, 865, 954, 10};
        int    i, j;
        for (i = 0; i < 10; i++)
        {
            //每一次由底至上地上升
            for (j = 9; j > i; j--)
            {
                if (array[j] < array[j-1])
                {
                        swap(&array[j], &array[j-1]);
                }
            }
        }
        for (i = 0; i < 10; i++)
        {
            printf("%d\n", array[i]);
        }
        return    0;
    }
    void swap(int *a, int *b)
    {
        int    temp;
        temp = *a;
          *a = *b;
          *b = temp;
    }

上面代码中，如果里面一层循环在某次扫描中没有执行交换，则说明此时数组已经全部有序列，无需再扫描了。因此，增加一个标记flag，每次发生交换，就标记flag=1，如果某次循环完没有标记，则说明已经完成排序。

#include <stdio.h>
    void swap(int *a, int *b);
    int main()
    {
        int    array[10] = {
       2, 1, 3, 4, 5, 6, 7, 8, 9, 10};
        int    i, j;
        int    flag = 1;   //设置标记变量
        for (i = 0; i < 10 && flag; i++)
        {
            flag = 0;      //只要flag在下一次外循环条件检测的时候值为0，就说明已经排好序，不用继续循环
            for (j = 9; j > i; j--)
            {
                if (array[j] < array[j-1])
                {
                    swap(&array[j], &array[j-1]);
                    flag = 1;   //如果有交换，就将标记变量赋1
                }
            }
        }
    
        for (i = 0; i < 10; i++)
        {
            printf("%d\n", array[i]);
        }
        return    0;
    }
    void swap(int *a, int *b)
    {
        int    temp;
        temp = *a;
          *a = *b;
          *b = temp;
    }

在第一步优化的基础上发进一步思考：如果R\[0..i\]已是有序区间，上次的扫描区间是R\[i..n\]，记上次扫描时最后 一次执行交换的位置为lastSwapPos，则lastSwapPos在i与n之间，不难发现R\[i..lastSwapPos\]区间也是有序的，否则这个区间也会发生交换；所以下次扫描区间就可以由R\[i..n\] 缩减到\[lastSwapPos..n\]。

void BubbleSort_3(int a[], int size)
    {
        int i, j, temp, lastSwapPos, lastSwapPos_temp = 0;
    
        for (i = 0; i < size - 1; i++)
        {
            lastSwapPos = lastSwapPos_temp;
            for (j = size - 1; j > lastSwapPos; j--)
            {
                if (a[j - 1] > a[j])
                {
                    temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;
    
                    lastSwapPos_temp = j - 1;
                }
            }
        }
    }