C语言中冒泡排序算法详解
时间：2022-02-19 09:39:12|栏目：C代码|点击： 次
一、算法描述
比较相邻两个元素，如果第一个比第二个大则交换两个值。遍历所有的元素，每一次都会将未排序序列中最大的元素放在后面。假设数组有 n 个元素，那么需要遍历 n - 1 次，因为剩下的一个元素一定是最小的，无需再遍历一次。因此需要两层循环，第一层是遍历次数，第二层是遍历未排序数组。
动图如下：
黄色部分表示已排好序的数组，蓝色部分表示未排序数组
核心代码如下：
/**
* @brief 冒泡排序
*
* @param arr 待排序的数组
* @param size 数组大小
*/
static void bubble_sort(int *arr, int size)
{
for (int i = 0; i < size - 1; i++) {
bool swapped = false; // 设置标记，用于检查是否已排好序
for (int j = 0; j < size - i; j++)
if (arr[j] > arr[j + 1]) {
swap(arr + j, arr + j + 1);
swapped = true;
}
if (!swapped) // 未交换则排序完毕，跳出循环
break;
}
}
布尔值 swapped 是一种优化手段，在每次遍历未排序数组之前将其设置为 false 表示还未交换。如果遍历完未排序数组之后其值还是 false 则表示遍历过程种没有发生交换，也就是说数组已经有序，无需再次遍历，跳出循环。
二、算法分析
时间复杂度：O(N2)，两层循环
空间复杂度：O(1)，交换元素时只用了一个临时变量
最好情况：O(N)，有序数组遍历一次后 swapped 为 false 退出循环
最坏情况：O(N2)，数组倒序
稳定性：稳定，比较两个元素大小时不包括元素相等的情况，故相等元素的相对位置不变
三、完整代码
/**
* @file bubble_sort.c
* @date 2022-01-16
* @author Pineapple (pineapple_cpp@163.com)
*
* @brief 冒泡排序
*/
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/**
* @brief 交换函数
*
* @param left 左边的元素
* @param right 右边的元素
*/
static inline void swap(int *left, int *right)
{
int temp = *left;
*left = *right;
*right = temp;
}
/**
* @brief 冒泡排序
*
* @param arr 待排序的数组
* @param size 数组大小
*/
static void bubble_sort(int *arr, int size)
{
for (int i = 0; i < size - 1; i++) {
bool swapped = false; // 设置标记，用于检查是否已排好序
for (int j = 0; j < size - i; j++)
if (arr[j] > arr[j + 1]) {
swap(arr + j, arr + j + 1);
swapped = true;
}
if (!swapped) // 未交换则排序完毕，跳出循环
break;
}
}
/**
* @brief 测试函数
*
*/
static void test()
{
const int size = rand() % 500; // 生成随机数组大小
int *arr = (int *)calloc(size, sizeof(int));
// 生成范围 -50 到 49 的随机数组
for (int i = 0; i < size; i++)
arr[i] = rand() % 100 - 50;
bubble_sort(arr, size);
for (int i = 0; i < size - 1; i++)
assert(arr[i] <= arr[i + 1]);
free(arr);
}
int main(void)
{
srand(time(NULL));
test();
return 0;
}
总结
上一篇：C语言实现三子棋游戏
栏 目：C代码
下一篇：C++继承介绍
本文标题：C语言中冒泡排序算法详解
本文地址：http://www.codeinn.net/misctech/193865.html
