C语言的冒泡排序方法怎么使用

发布时间：2021-12-18 16:05:02 作者：iii
来源：亿速云阅读：192

# C语言的冒泡排序方法怎么使用

## 1. 冒泡排序算法简介

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端（升序排列时），就像气泡从水底冒到水面一样。

### 1.1 基本思想

冒泡排序的基本思想是通过相邻元素之间的比较和交换，使较大的元素逐渐从前面移到后面（或者较小的元素从后面移到前面），就像气泡一样逐渐向上"漂浮"。

### 1.2 算法特点

- 时间复杂度：O(n²)（最坏和平均情况）
- 空间复杂度：O(1)（原地排序）
- 稳定性：稳定排序算法
- 适应性：适合小规模数据排序

## 2. 冒泡排序的实现步骤

### 2.1 基础实现步骤

1. 比较相邻的元素。如果第一个比第二个大（升序排列），就交换它们
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 重复步骤1~3，直到排序完成

### 2.2 示例代码

```c
#include <stdio.h>

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]) {
                // 交换arr[j]和arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

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

3. 冒泡排序的优化

基础冒泡排序即使在最好的情况下（数组已经有序）时间复杂度仍然是O(n²)。我们可以通过一些优化来提高效率。

3.1 优化一：设置标志位

如果在某一轮排序中没有发生任何交换，说明数组已经有序，可以提前结束排序。

void optimizedBubbleSort(int arr[], int n) {
    int swapped;
    for (int i = 0; i < n-1; i++) {
        swapped = 0;
        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;
                swapped = 1;
            }
        }
        // 如果没有发生交换，提前退出
        if (swapped == 0)
            break;
    }
}

3.2 优化二：记录最后交换位置

记录每轮排序中最后一次交换的位置，下一轮排序只需要比较到这个位置即可。

void furtherOptimizedBubbleSort(int arr[], int n) {
    int lastExchangeIndex = 0;
    int sortBorder = n - 1;
    
    for (int i = 0; i < n-1; i++) {
        int swapped = 0;
        for (int j = 0; j < sortBorder; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1;
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        if (swapped == 0)
            break;
    }
}

4. 冒泡排序的性能分析

4.1 时间复杂度

最坏情况：O(n²)（数组完全逆序）
最好情况：O(n)（数组已经有序，使用优化版本）
平均情况：O(n²)

4.2 空间复杂度

冒泡排序是原地排序算法，只需要常数级别的额外空间，空间复杂度为O(1)。

4.3 稳定性

冒泡排序是稳定的排序算法，因为相等的元素不会交换位置。

5. 冒泡排序的应用场景

虽然冒泡排序在实际应用中较少使用（因为效率较低），但它仍然适用于：

教学目的：理解排序算法的基本原理
小规模数据排序
基本有序的数据排序（使用优化版本）
作为其他排序算法的基础（如鸡尾酒排序）

6. 冒泡排序的变种

6.1 鸡尾酒排序（双向冒泡排序）

鸡尾酒排序是冒泡排序的变种，排序时从左到右再从右到左交替进行。

void cocktailSort(int arr[], int n) {
    int swapped = 1;
    int start = 0;
    int end = n - 1;
    
    while (swapped) {
        swapped = 0;
        
        // 从左到右
        for (int i = start; i < end; i++) {
            if (arr[i] > arr[i+1]) {
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                swapped = 1;
            }
        }
        
        if (!swapped) break;
        
        swapped = 0;
        end--;
        
        // 从右到左
        for (int i = end-1; i >= start; i--) {
            if (arr[i] > arr[i+1]) {
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                swapped = 1;
            }
        }
        
        start++;
    }
}

6.2 梳排序

梳排序是冒泡排序的改进，通过较大的间隔开始比较，逐渐缩小间隔。

7. 总结

冒泡排序虽然简单，但通过不同的优化手段可以显著提高其性能。理解冒泡排序不仅有助于掌握基本的排序算法思想，也为学习更复杂的排序算法奠定了基础。在实际编程中，对于小规模数据或基本有序的数据，优化后的冒泡排序仍然有其用武之地。

”`