笔记大全

c语言冒泡排序怎样实现从大到小

更新时间：2023-10-09

什么是冒泡排序？

冒泡排序是一种基本的排序算法，它的基本思想是将待排序的数据中相邻的所有元素两两比较，将较小的元素往前移，较大的元素往后移。通俗点说，就像泡泡不断上浮过程中，大小关系也在不断改变，直到最终排序完成。

冒泡排序的实现方法

冒泡排序实现简单，可以使用两层循环来实现，外层循环控制排序的轮次，内层循环控制每一轮排序过程。在每一轮排序中，相邻的两个元素进行比较，如果左边元素大于右边元素，则交换两个元素的位置。经过多轮排序后，我们可以将待排序的序列排成一个有序的序列。

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] < arr[j + 1]) {    // 将<改为>即可实现从大到小排序
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

从大到小的冒泡排序示例

要实现从大到小的冒泡排序，只需要将比较大小的符号从小于号改为大于号即可。

#include 
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] < arr[j + 1]) {   // 将<改为>
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    int i;
    printf("排序前数组序列为：");
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    bubble_sort(arr, len);
    printf("从大到小排序后数组序列为：");
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

冒泡排序的时间复杂度

冒泡排序的时间复杂度是O(n^2)，其中n是数据的数量。这是因为冒泡排序需要进行n-1轮排序，每轮排序需要比较n-i次，每次比较又需要交换位置，所以总的时间复杂度为O(n^2)。

冒泡排序的优化

虽然冒泡排序实现简单，但它的效率较低，对于大规模数据的排序来说，效率会变得非常慢。为了提高冒泡排序的效率，可以在排序的过程中增加一些判断条件，减少不必要的比较。

1. 对已经排好序的元素不再进行比较。在每次比较过程中，可以记录上次排序时的交换位置，下次排序时只需要比较到这个位置即可。

void bubbleSort(int arr[], int n) {
    int m = n; // 上次排序交换的位置
    while (m > 0) {
        int k = m;
        m = 0;
        for (int i = 1; i < k; i++) {
            if (arr[i - 1] < arr[i]) { // 将<改为>即可实现从大到小排序
                int temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;
                m = i;
            }
        }
    }
}

2. 数组后面部分已经排好序，前面的部分无需再比较。在每次内层循环的结束后，记录已经排序好的部分的位置，下次比较时，只需要比较到这个位置即可。

void bubbleSort(int arr[], int n) {
    int m = n; // 上次排序交换的位置
    int k = n;
    while (m > 0) {
        int lastIndex = m;
        m = 0;
        for (int i = 1; i < k; i++) {
            if (arr[i - 1] < arr[i]) { // 将<改为>即可实现从大到小排序
                int temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;
                m = i;
                lastIndex = i;
            }
        }
        k = lastIndex;
    }
}

经过以上两步优化后，冒泡排序的效率得到了一定的提升，但是相比于其他排序算法，还是不够高效。

c语言编程笔录