快捷導(dǎo)航

C語(yǔ)言中冒泡排序算法詳解

更新時(shí)間：2022年01月18日 09:45:09 作者：pineapple_py

大家好，本篇文章主要講的是C語(yǔ)言中冒泡排序算法詳解，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下

一、算法描述

比較相鄰兩個(gè)元素，如果第一個(gè)比第二個(gè)大則交換兩個(gè)值。遍歷所有的元素，每一次都會(huì)將未排序序列中最大的元素放在后面。假設(shè)數(shù)組有 n 個(gè)元素，那么需要遍歷 n - 1 次，因?yàn)槭Ｏ碌囊粋€(gè)元素一定是最小的，無(wú)需再遍歷一次。因此需要兩層循環(huán)，第一層是遍歷次數(shù)，第二層是遍歷未排序數(shù)組。

動(dòng)圖如下：

黃色部分表示已排好序的數(shù)組，藍(lán)色部分表示未排序數(shù)組

核心代碼如下：

/**
 * @brief 冒泡排序
 * 
 * @param arr 待排序的數(shù)組
 * @param size 數(shù)組大小
 */
static void bubble_sort(int *arr, int size)
{
	for (int i = 0; i < size - 1; i++) {
		bool swapped = false; // 設(shè)置標(biāo)記，用于檢查是否已排好序
		for (int j = 0; j < size - i; j++)
			if (arr[j] > arr[j + 1]) {
				swap(arr + j, arr + j + 1);
				swapped = true;
			}
		if (!swapped) // 未交換則排序完畢，跳出循環(huán)
			break;
	}
}

布爾值 swapped 是一種優(yōu)化手段，在每次遍歷未排序數(shù)組之前將其設(shè)置為 false 表示還未交換。如果遍歷完未排序數(shù)組之后其值還是 false 則表示遍歷過(guò)程種沒(méi)有發(fā)生交換，也就是說(shuō)數(shù)組已經(jīng)有序，無(wú)需再次遍歷，跳出循環(huán)。

二、算法分析

時(shí)間復(fù)雜度：O(N2)，兩層循環(huán)

空間復(fù)雜度：O(1)，交換元素時(shí)只用了一個(gè)臨時(shí)變量

最好情況：O(N)，有序數(shù)組遍歷一次后 swapped 為 false 退出循環(huán)

最壞情況：O(N2)，數(shù)組倒序

穩(wěn)定性：穩(wěn)定，比較兩個(gè)元素大小時(shí)不包括元素相等的情況，故相等元素的相對(duì)位置不變

三、完整代碼

/**
 * @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 交換函數(shù)
 * 
 * @param left 左邊的元素
 * @param right 右邊的元素
 */
static inline void swap(int *left, int *right)
{
	int temp = *left;
	*left = *right;
	*right = temp;
}

/**
 * @brief 冒泡排序
 * 
 * @param arr 待排序的數(shù)組
 * @param size 數(shù)組大小
 */
static void bubble_sort(int *arr, int size)
{
	for (int i = 0; i < size - 1; i++) {
		bool swapped = false; // 設(shè)置標(biāo)記，用于檢查是否已排好序
		for (int j = 0; j < size - i; j++)
			if (arr[j] > arr[j + 1]) {
				swap(arr + j, arr + j + 1);
				swapped = true;
			}
		if (!swapped) // 未交換則排序完畢，跳出循環(huán)
			break;
	}
}

/**
 * @brief 測(cè)試函數(shù)
 * 
 */
static void test()
{
	const int size = rand() % 500; // 生成隨機(jī)數(shù)組大小
	int *arr = (int *)calloc(size, sizeof(int));

	// 生成范圍 -50 到 49 的隨機(jī)數(shù)組
	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;
}