C:冒泡排序

JonlyMay 2024-08-12 17:35:05 阅读 96

1e0f36d95fb04c78a598e20fa1049156.jpg

1、冒泡排序介绍:

冒泡排序的核心思想就是:两两相邻的元素进行比较。

先用一个例子来帮助大家理解一下冒泡排序的算法是怎们进行的

有一排高矮不同的人站成一列,要按照从矮到高的顺序重新排队。

冒泡排序的方法就是,从第一个人开始,依次两两比较相邻的两个人的身高。如果左边的人比右边的高,就交换他们的位置。

这样一轮下来,最高的人就像气泡一样“浮”到了最右边。

然后再从头开始,重复刚才的比较和交换,让第二高的人“浮”到右边第二个位置。

就这样一轮一轮地比较和交换,直到所有人都排好序。

2、不使用函数的冒泡排序:

代码展示:

<code>#include <stdio.h>

int main(){

int arr[] = { 100,99,3,45,12,55,88,22,13,19 };//随机输入的数字

int i = 0;

int sz = sizeof arr / sizeof(arr[0]);//求数组中的元素个数

for ( i = 0; i < sz - 1; i++){//总趟数

int j = 0;

for (j = 0; j < sz - 1 - i; j++){//一趟冒泡排序

if (arr[j] > arr[j + 1]){

//交换两数

int k = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = k;}}}

for (i = 0; i < sz; i++){

printf("%d ", arr[i]);}//实现排序后的数组打印

return 0;}

 结果展示:

b20175b7e8f14278870c90000fb412be.png

2.1 sz的解释:

int sz = sizeof arr / sizeof(arr[0]);

这行代码用于计算数组 arr 中的元素个数。

 sizeof是 C 语言中的一个操作符,用于获取数据类型或者变量所占用的字节数。

 sizeof arr 会返回整个数组所占用的字节数。

 sizeof(arr[0]) 会返回数组中单个元素所占用的字节数。

然后用整个数组占用的字节数除以单个元素占用的字节数,就得到了数组中元素的个数,并将其存储在变量 sz  中。

例如,如果  arr  是一个 int 类型的数组,每个 int 类型通常占用 4 个字节。假设整个数组占用了 40 个字节,那么sz = 40 / 4 = 10 ,即数组中有 10 个元素。

这样做的好处是,即使数组的大小在不同的情况下可能会发生变化,通过这种方式计算元素个数可以提高代码的可维护性和通用性,避免了重复编码数组的大小。

2.2 i  < sz - 1  和 j < sz-1-i 的解释

这里的 i 是进行冒泡排序的总趟数,sz - 1是因为对于一个含有sz个元素的数组,进行 sz - 1 趟冒泡排序就可以完成排序。

这里的 j 是进行一次冒泡排序所要交换的次数, sz-1-i 用于控制每一趟冒泡排序中比较和交换的次数。

以包含 5 个元素的数组为例:

第一趟需要比较 4 次(即 sz-1),因为要把最大的数“浮”到最后位置。

第二趟只需要比较 3 次(即 sz-1-1),因为最大的数已经在最后,不用再参与比较。

第三趟比较 2 次(即 sz-1-2)。

第四趟比较 1 次(即 sz-1-3)。

这样,每一趟比较的次数逐渐减少,通过这种方式可以在经过一定的趟数后完成整个数组的排序。

3、使用函数的冒泡排序:

<code>#include <stdio.h>

void bublle_sort(int arr[], int sz)//实现冒泡排序

{

for(int i = 0; i < sz - 1; i++)//总趟数

{ //一趟冒泡排序

for (int j = 0; j < sz-1-i; j++)

{

if (arr[j] > arr [j + 1] )//相邻两数比较大小

{

int k = arr[j];

arr[j] = arr[ j + 1];

arr[j + 1] = k;

}

}

}

}

void printf_arr(int arr[], int sz)//打印排序后的值

{

int i = 0;

for (i = 0; i < sz; i++)

{

printf("%d ", arr[i]);

}

printf("\n");

}

int main()

{

int arr[] = { 2,3,4,5,6,7,1,8,9,10 };//这里的整数是可以任意输入的,不限数量

//写一个函数,实现冒泡排序

//假设为升序排列

int sz = sizeof arr / sizeof(arr[0]);//求数组中元素的个数

bublle_sort(arr, sz);//实现冒泡排序

printf_arr(arr, sz);//实现打印排序后的值

return 0;

}

这里就比上面那个多了两个函数,里面注释写的还是比较清楚的,可以看一看

4、关于函数冒泡排序的代码改进

void bublle_sort(int arr[], int sz)//实现冒泡排序

{

for(int i = 0; i < sz - 1; i++)//总趟数

{ //一趟冒泡排序

for (int j = 0; j < sz-1-i; j++)

{

if (arr[j] > arr [j + 1] )//相邻两数比较大小

{

int k = arr[j];

arr[j] = arr[ j + 1];

arr[j + 1] = k;

}

}

}

}

关于冒泡排序的次数,上述这组代码不管所给的数字是什么顺序排列的,想要改为升序都需要进行45组两数相比,如果所要排序的数组是乱序的话45次还能接受,但是如果所给的顺序是

9 0 1 2 3 4 5 6 7 8

像上述这种顺序改为升序仅仅只需要将9移动到最后一位即可,也就是说只需要一趟冒泡排序即可完成。但是,向上面的代码,当第一趟冒泡排序结束后,会紧接着进行下一趟冒泡排序。虽然排序已经完成,但是后面依旧会继续比较,虽然数字不会再交换顺序。因此,向这种情况我们应该怎么改进呢?

#include <stdio.h>

void bublle_sort(int arr[], int sz)

{

    for(int i = 0; i < sz - 1; i++)//总趟数

    {   //一趟冒泡排序

        int flag = 1;//假设已经有序了

        for (int j = 0; j < sz-1-i; j++)

        {

            if (arr[j] > arr [j + 1] )

            {

                int k = arr[j];

                arr[j] = arr[ j + 1];

                arr[j + 1] = k;

                flag = 0;//说明其中发生了交换,假设不成立

            }

        }

        if (flag == 1)//说明假设成立

        {

            break;//跳出循环

        }

    }

}

 看上面被标红的代码,当我们这样优化后,可以减少多余的循环,提高效率。

5、使用指针的冒泡排序:

先补充几个知识点:

数组的数组名arr就是首元素地址,所以我们传参传的其实就是首元素地址bublle_sort(arr, sz);

我们将形参改写为指针,通过指针找回来的还是main函数里的原数组

主函数里的数组传递给冒泡排序函数,冒泡函数里使用的数组依然是主函数里的数组,这是因为数组传参传的是它的地址。

使用指针标识的冒泡函数

#include <stdio.h>                                                               

void bublle_sort(int* arr, int sz)//实现冒泡排序

{

    for (int i = 0; i < sz - 1; i++)//总趟数

    {   //一趟冒泡排序

        int flag = 1;

        for (int j = 0; j < sz - 1 - i; j++)

        {

            if (*(arr + j) > *(arr + j + 1))//相邻两数比较大小

            {

                int k = *(arr+j);

                *(arr + j) = *(arr + j + 1);

                *(arr + j + 1) = k;

                flag = 0;

            }

        }

        if (flag == 1)

        {

            break;

        }

    }

}

void printf_arr(int* arr, int sz)//打印排序后的值

{

    int i = 0;

    for (i = 0; i < sz; i++)

    {

        printf("%d ", *(arr + i));

    }

    printf("\n");

}

int main()

{

int arr[] = { 2,3,4,5,6,7,1,8,9,10 };

//写一个函数,实现冒泡排序

//假设为升序排列

int sz = sizeof arr / sizeof(arr[0]);

bublle_sort(arr, sz);//实现冒泡排序

printf_arr(arr, sz);//实现打印排序后的值

return 0;

}


结语:

本篇文章到这里就先结束了,期待大家的的阅读!!!

 

 

 



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。