C语言冒泡排序
pineapple_py 人气:0一、算法描述
比较相邻两个元素,如果第一个比第二个大则交换两个值。遍历所有的元素,每一次都会将未排序序列中最大的元素放在后面。假设数组有 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; }
总结
加载全部内容