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é)
到此這篇關(guān)于C語言中冒泡排序算法詳解的文章就介紹到這了,更多相關(guān)C語言冒泡排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++類與對象深入之構(gòu)造函數(shù)與析構(gòu)函數(shù)詳解
朋友們好,這篇播客我們繼續(xù)C++的初階學習,現(xiàn)在對我們對C++非常重要的一個知識點做出總結(jié),整理出來一篇博客供我們一起復習和學習,如果文章中有理解不當?shù)牡胤?還希望朋友們在評論區(qū)指出,我們相互學習,共同進步2022-06-06有關(guān)C++中隨機函數(shù)rand() 和srand() 的用法詳解
下面小編就為大家?guī)硪黄嘘P(guān)C++中隨機函數(shù)rand() 和srand() 的用法詳解。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-01-01c++如何在主函數(shù)文件中調(diào)用其他函數(shù)文件
這篇文章主要介紹了c++如何在主函數(shù)文件中調(diào)用其他函數(shù)文件問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08C/C++?Qt數(shù)據(jù)庫SqlRelationalTable關(guān)聯(lián)表詳解
這篇文章主要介紹了QT中SqlRelationalTable關(guān)聯(lián)表組件的使用,文中代碼對我們的學習和工作具有一定價值,感興趣的朋友可以了解一下2021-12-12