欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言中冒泡排序算法詳解

 更新時間:2022年01月18日 09:45:09   作者:pineapple_py  
大家好,本篇文章主要講的是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ù)詳解

    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ān)C++中隨機函數(shù)rand() 和srand() 的用法詳解

    下面小編就為大家?guī)硪黄嘘P(guān)C++中隨機函數(shù)rand() 和srand() 的用法詳解。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-01-01
  • 深入解析C++ STL中的常用容器

    深入解析C++ STL中的常用容器

    這里我們不涉及容器的基本操作之類,只是要討論一下各個容器其各自的特點。STL中的常用容器包括:順序性容器(vector、deque、list)、關(guān)聯(lián)容器(map、set)、容器適配器(queue、stac)
    2013-09-09
  • C語言編寫漢諾塔游戲

    C語言編寫漢諾塔游戲

    這篇文章主要介紹了C語言編寫漢諾塔游戲,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2021-11-11
  • C++實現(xiàn)趣味掃雷游戲

    C++實現(xiàn)趣味掃雷游戲

    這篇文章主要為大家詳細介紹了C++實現(xiàn)趣味掃雷游戲,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-06-06
  • 用c語言實現(xiàn)和平精英的完整代碼

    用c語言實現(xiàn)和平精英的完整代碼

    這篇文章主要介紹了用c語言實現(xiàn)和平精英的完整代碼,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-04-04
  • Qt實現(xiàn)圖形裁減

    Qt實現(xiàn)圖形裁減

    這篇文章主要為大家詳細介紹了Qt實現(xiàn)圖形裁減,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-06-06
  • c++如何在主函數(shù)文件中調(diào)用其他函數(shù)文件

    c++如何在主函數(shù)文件中調(diào)用其他函數(shù)文件

    這篇文章主要介紹了c++如何在主函數(shù)文件中調(diào)用其他函數(shù)文件問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-08-08
  • C/C++?Qt數(shù)據(jù)庫SqlRelationalTable關(guān)聯(lián)表詳解

    C/C++?Qt數(shù)據(jù)庫SqlRelationalTable關(guān)聯(lián)表詳解

    這篇文章主要介紹了QT中SqlRelationalTable關(guān)聯(lián)表組件的使用,文中代碼對我們的學習和工作具有一定價值,感興趣的朋友可以了解一下
    2021-12-12
  • C語言實現(xiàn)超市信息管理系統(tǒng)

    C語言實現(xiàn)超市信息管理系統(tǒng)

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)超市信息管理系統(tǒng),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03

最新評論