【C语言】深入理解冒泡排序算法(优化+详解)

文章目录

什么叫冒泡排序

冒泡排序是比较基础的排序算法之一,其思想是相邻的元素两两比较,较大的数下沉,较小的数冒起来,这样一趟比较下来,最大(小)值就会排列在一端。

整个过程如同气泡冒起,因此被称作冒泡排序

通俗来说,也就是:

从第一个元素开始比较相邻的两个元素,如果第一个比第一个大或小,就互换它们的位置,这样先比较完一次,然后抛弃最大或最小的继续比较,直到排序完成。

冒泡排序的步骤:

  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  • 每趟从第一对相邻元素开始,对每一对相邻元素作同样的工作,直到最后一对。
  • 针对所有的元素重复以上的步骤,除了已排序过的元素(每趟排序后的最后一个元素),直到没有任何一对数字需要比较。

动画演示:

此处引用网上一张比较经典的gif来展示冒泡排序的整个过程:


【C语言】深入理解冒泡排序算法(优化+详解)

图解冒泡排序

有8个数组组成一个无序数列:5,8,6,3,9,2,1,7,希望从小到大排序。


【C语言】深入理解冒泡排序算法(优化+详解)

按照冒泡排序的思想:把相邻的两个数字两两比较,当一个数字大于右侧相邻的数字时,交换他们的位置,当一个数字和他右侧的数字小于或等于的时候,不交换。

第一轮排序

  1. 首先让5和8进行交换,发现5比8小,因此元素位置不变;
  2. 接下来让8和6比较,发现8比6大,所以要交换8和6的位置;

【C语言】深入理解冒泡排序算法(优化+详解)

  1. 继续让8和3比较,发现8比3要大,所以8和3 交换位置;

【C语言】深入理解冒泡排序算法(优化+详解)

  1. 继续让8和9进行比较,发现8比9小,不用交换;
  2. 9和2进行比较,发现9比2大,进行交换;

【C语言】深入理解冒泡排序算法(优化+详解)

  1. 继续让9和1进行比较,发现9比1大,所以交换9和1的位置;

【C语言】深入理解冒泡排序算法(优化+详解)

  1. 最后,让9和7交换位置;

【C语言】深入理解冒泡排序算法(优化+详解)

这样一来,元素9作为数列的最大元素,就已经排序好了

【C语言】深入理解冒泡排序算法(优化+详解)

第二轮排序

  1. 首先让5和6比较,发现5比6小,位置不变;
  2. 接下来让6和3比较,发现6比3大,交换位置;

【C语言】深入理解冒泡排序算法(优化+详解)

  1. 接下来让6和8比较,6比8小,位置不变;
  2. 8和2比较。8比2大,交换位置;

【C语言】深入理解冒泡排序算法(优化+详解)

  1. 接下来让8和1比较,8比1大,因此交换位置;【C语言】深入理解冒泡排序算法(优化+详解)
  2. 继续让8和7比较,发现8比7大,交换位置;

【C语言】深入理解冒泡排序算法(优化+详解)

这样一来,第二轮排序已经好了

【C语言】深入理解冒泡排序算法(优化+详解)

第三轮排序

按照以上步骤,可得第三轮排序:

【C语言】深入理解冒泡排序算法(优化+详解)

第四轮排序

按照以上步骤,可得第四轮排序:

【C语言】深入理解冒泡排序算法(优化+详解)

第五轮排序

按照以上步骤,可得第五轮排序:

【C语言】深入理解冒泡排序算法(优化+详解)

第六轮排序

按照以上步骤,可得第六轮排序:

【C语言】深入理解冒泡排序算法(优化+详解)

第七轮排序

按照以上步骤,可得第七轮排序,此时已经有序了:

【C语言】深入理解冒泡排序算法(优化+详解)

第八轮排序

此时已经排序完成啦!

【C语言】深入理解冒泡排序算法(优化+详解)

到此为止,所有的数字都是有序的了,冒泡排序是一种稳定排序,由于该排序算法的每一轮都要遍历所有的数字,一共要遍历n-1,所以时间复杂度为O(n^2)

那么我们如何区分排序算法是否稳定呢?

如果我们交换的时候,遇到两个相同的数字;

如果两个相同的数字在排序之后相对位置没有交换,那么就是稳定的排序,反之则是不稳定的排序。

代码实现

代码过程如下:

void bubble_sort(int* arr, int sz)
{
    int i = 0;
    int j = 0;
    for (i = 0; i < sz - 1; i++)
    {
        for (j = 0; j < sz - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

int main()
{
    int arr[10] = { 5, 8, 6, 3, 9, 2, 1, 7 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, sz);

    int i = 0;
    for (i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
 }

运行结果:

【C语言】深入理解冒泡排序算法(优化+详解)

这个代码很简单,使用双循环的方式进行排序。

外部的循环控制所有回合,内部循环代表每一轮的冒泡处理,先进行元素比较,再进行元素交换。

代码优化

从上面的例子不难看出,我们可以对原来的冒泡排序进行优化。

我们仍然用上面呢个数列{ 5, 8, 6, 3, 9, 2, 1, 7 }为例子,从上面的图解可以看出在第六、第七、第八轮排序后,整个数列已经是有序的了,但是排序算法还是执行到了第八轮排序。

【C语言】深入理解冒泡排序算法(优化+详解)

优化的思路是:如果能判断出数列已经是有序的了,并且做出标记,那么就不会执行多余的排序。

因此,我们可以进行一个优化,就是设置一个flags;

  • 如果在本轮排序中有元素进行交换,则说明数列无序,如果已经排序了那么设置为0;
  • 如果在本轮排序中,没有元素进行交换,则说明数列有序,那么设置为1。

现在我们来看看优化后的代码:

void bubble_sort(int* arr, int sz)
{
    int i = 0;
    int j = 0;
    int flags = 0;
    for (i = 0; i < sz - 1; i++)
    {
        for (j = 0; j < sz - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                flags = 1;//不是有序的,flags设置为1
            }
        }

        if (flags == 0)
            return;
    }
}

int main()
{
    int arr[8] = { 5, 8, 6, 3, 9, 2, 1, 7 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i = 0;

    printf("排序前: ");
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    bubble_sort(arr, sz);

    printf("排序后: ");
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
 }

运行结果:

【C语言】深入理解冒泡排序算法(优化+详解)

以上就是冒泡排序啦!

如有错误,欢迎指正话????!

上一篇:C#9.0新特性详解系列之六:增强的模式匹配


下一篇:Linux和Windows系统之间文件互传