C語言中冒泡排序算法詳解
一、算法描述
比較相鄰兩個元素，如果第一個比第二個大則交換兩個值。遍歷所有的元素，每一次都會將未排序序列中最大的元素放在后面。假設數(shù)組有 n 個元素，那么需要遍歷 n - 1 次，因為剩下的一個元素一定是最小的，無需再遍歷一次。因此需要兩層循環(huán)，第一層是遍歷次數(shù)，第二層是遍歷未排序數(shù)組。
動圖如下：
黃色部分表示已排好序的數(shù)組，藍色部分表示未排序數(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; // 設置標記，用于檢查是否已排好序
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ù)組之前將其設置為 false 表示還未交換。如果遍歷完未排序數(shù)組之后其值還是 false 則表示遍歷過程種沒有發(fā)生交換，也就是說數(shù)組已經(jīng)有序，無需再次遍歷，跳出循環(huán)。
二、算法分析
時間復雜度：O(N2)，兩層循環(huán)
空間復雜度：O(1)，交換元素時只用了一個臨時變量
最好情況：O(N)，有序數(shù)組遍歷一次后 swapped 為 false 退出循環(huán)
最壞情況：O(N2)，數(shù)組倒序
穩(wěn)定性：穩(wěn)定，比較兩個元素大小時不包括元素相等的情況，故相等元素的相對位置不變
三、完整代碼
/**
* @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; // 設置標記，用于檢查是否已排好序
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 測試函數(shù)
*
*/
static void test()
{
const int size = rand() % 500; // 生成隨機數(shù)組大小
int *arr = (int *)calloc(size, sizeof(int));
// 生成范圍 -50 到 49 的隨機數(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;
}
總結(jié)
到此這篇關于C語言中冒泡排序算法詳解的文章就介紹到這了,更多相關C語言冒泡排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
下面小編就為大家?guī)硪黄獪\談在函數(shù)中返回動態(tài)的內(nèi)存。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
C++實現(xiàn)學生信息管理系統(tǒng)(Map實現(xiàn))
這篇文章主要為大家詳細介紹了C++實現(xiàn)學生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
OpenCV reshape函數(shù)實現(xiàn)矩陣元素序列化
reshape函數(shù)是OpenCV中一個很有用的函數(shù)，不僅可以改變矩陣的通道數(shù)，還可以對矩陣元素進行序列化。本文將主要介紹如何通過reshape實現(xiàn)矩陣元素序列化，需要的小伙伴可以參考一下2021-12-12
C?語言提供了豐富的操作符，有：算術操作符，移位操作符，位操作符，賦值操作符，單目操作符，關系操作符，邏輯操作符，條件操作符等。讓我們通讀本篇來詳細了解吧2022-06-06
數(shù)據(jù)結(jié)構之帶頭結(jié)點的單鏈表
單鏈表是一種鏈式存取的數(shù)據(jù)結(jié)構，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點來表示的，每個結(jié)點的構成：數(shù)據(jù)域(數(shù)據(jù)元素的映象)?+?指針域(指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個結(jié)點的地址數(shù)據(jù)2023-07-07
二叉搜索樹（Binary Search Tree）又稱二叉排序樹，也稱作二叉查找樹它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹，若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值，若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值2023-03-03
這篇文章主要介紹了C/C++調(diào)用Fortran的DLL,本文以一個簡單的加法器為例，通過實例代碼給大家介紹的非常詳細，需要的朋友可以參考下2022-03-03
用C語言實現(xiàn)從文本文件中讀取數(shù)據(jù)后進行排序的功能
這是一個十分可靠的程序，這個程序的查錯能力非常強悍。程序包含了文件操作，歸并排序和字符串輸入等多種技術。對大家學習C語言很有幫助，有需要的一起來看看。2016-08-08
i++總是要創(chuàng)建一個臨時對象，在退出函數(shù)時還要銷毀它，而且返回臨時對象的值時還會調(diào)用其拷貝構造函數(shù)2013-10-10
這篇文章主要介紹了C++ QgraphicsScene類案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08