【C语言】拿捏冒泡排序（图解）

学习起来吧

发布于 2024-02-29 21:14:23

2660

文章被收录于专栏：学习C/++学习C/++

冒泡排序

冒泡排序:它重复地走访要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。重复地进行直到没有再需要交换，也就是说该数列已经排序完成。下面是冒泡排序的步骤：

从第一个元素开始，依次比较相邻的两个元素，如果顺序不对则交换它们。
继续比较相邻的元素，直到最后一个元素，这样一轮比较下来，最大的元素就会被交换到最后的位置。
接着重复上述步骤，但是不包括已经排序好的最后一个元素，因为它们已经是最大的了。重复以上步骤，直到所有元素都排好序为止。

对数组 arr[] = { 66, 34, 25, 12, 22, 11, 98 }进行冒泡排序

i=0，j=5,第一趟，交换了6次； i=1, j=4,第二趟，交换了5次， i=2, j=3,第三趟，交换了4次； …以此类推结论： 7个元素每走一趟，交换少一次，j少一次,i+1

代码实现：

#include <stdio.h>

void bubbleSort(int arr[], int n) 
{
		//i为趟数
    for (int i = 0; i < n - 1; i++) //arr[]7个元素
    {
        for (int j = 0; j < n - i - 1; j++) 
        {
            if (arr[j] > arr[j + 1]) 
            {
                // 交换arr[j]和arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() 
{
    int arr[] = { 66, 34, 25, 12, 22, 11, 98 };
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("排序后的数组: \n");
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

因为冒泡排序比较次数和交换次数都比较多，当数据量很大时，效率比较低。优化:如果在一次排序中没有发生交换，则表示数组已经排好序了，可以提前结束排序。

使用Flag看他有没有进入交换，交换后就改为

#include <stdio.h>

void bubbleSort(int arr[], int n) 
{
    for (int i = 0; i < n - 1; i++) 
    {
        int flag = 1;//假设这⼀趟已经有序了
        for (int j = 0; j < n - i - 1; j++) 
        {
            if (arr[j] > arr[j + 1]) 
            {
                flag = 0;//发⽣交换就说明，⽆序
                
                // 交换arr[j]和arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (flag == 1)//这⼀趟没交换就说明已经有序，后续⽆序排序了
            break;

    }
}

int main() 
{
    int arr[] = { 66, 34, 25, 12, 22, 11, 98 };
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("排序后的数组: \n");
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-12-16，如有侵权请联系 cloudcommunity@tencent.com 删除

int