自学内容网 自学内容网

C语言程序设计十大排序—冒泡排序

1.概念✅

  排序是数据处理的基本操作之一,每次算法竞赛都很多题目用到排序。排序算法是计算机科学中基础且常用的算法,排序后的数据更易于处理和查找。在计算机发展的历程中,在排序算法的研究一直深受人们重视,出现了很多算法,在思路、效率、应用等方面各有特色。通过学习排序算法,读者可以理解不同算法的优势和局限性,并根据具体情况选择最合适的算法,以提高程序的性能和效率。学习排序算法还有助于培养逻辑思维和问题解决能力,在解决其他类型的问题时也能够应用到类似的思维方法。

2.冒泡排序🎈

 冒泡排序(Bubble Sort)也是一种简单、直观的排序算法,它的算法思想和选择排序差不多,略有区别。
 第一轮,找到最大的数,放到第n个位置:
 第二轮,找到第2大的数,放到第n-1个位置;
 ......
 第n轮,找到最小的数,放到第1个位置。
 与选择排序的原理过于简单相比,冒泡排序用到了“冒泡”这个小技巧。以“第一轮,找最大的数,放到第n个位置”为例,对a[0]~a[n-1]做冒泡排序,操作如下:
 (1)从第1个数a[0]开始,比较a[0]和a[1],如果a[0]>a[1],交换。进一步把前面两个数的最大数放到了第2个位置,如下图所示。

排序前
 (2)比较a[1]和a[2],如果a[1]>a[2],交换,这一步把前面3个数的最大数放到了第3个位置,如下图所示:
排序后
 (3)比较a[2]和a[3]…
  依次比较相邻的两个数,直到最后两个数a[n-2]和a[n-1],就把最大的数放到了第a[n-1]个位置。一共比较了n-1次。
  将这个过程形象地比喻为“冒泡”,最大的元素像气泡一样慢慢“浮”到了顶端。
  以上是“第一轮,最大元素的冒泡”,其他的数也同样的方法处理,一共做n-1轮冒泡。第i轮找到第i大的数,冒泡到a[i-1],就把第i大的数放到了第i个位置。

3.代码实现✅

3.1 直接写✨

#include <stdio.h>

int main() {
    int arr[] = {13, 14, 52, 12, 22, 11, 90}; // 原始数组
    int n = sizeof(arr) / sizeof(arr[0]); // 数组大小
    int temp,i,j;
    printf("排序前:");
    for ( i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

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

3.2 函数✨

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int temp,i,j;
    for (i = 0; i < n - 1; i++) {
        // 设置一个标志位,用于优化
        int swapped = 0;
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                // 标记有元素交换
                swapped = 1;
            }
        }
        // 如果没有发生交换,数组已经排好序
        if (swapped == 0) {
            break;
        }
    }
}

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

int main() {
    int arr[] = {13, 14, 52, 12, 22, 11, 90}; // 原始数组
    int n = sizeof(arr) / sizeof(arr[0]); // 数组大小
    bubbleSort( arr, n);
    printArray( arr, n);
}

4.总结✅

  冒泡排序的计算复杂度:第5行和第8行有两重for循环计算复杂度为O(n^2),和选择排序的计算复杂度一样。
  冒泡排序可以做一点优化:若两个相邻的数已经有序,那么不用冒泡;在第i轮求第i大的数时,若一次冒泡都没有发生,说明整个数列已经有序,算法结束。

Perspective-takling


原文地址:https://blog.csdn.net/weixin_49853850/article/details/145279990

免责声明:本站文章内容转载自网络资源,如侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!