目錄

1、緣起

2、BubbleSort 算法描述

3、用圖示描述 BubbleSort 算法

4、C?語言描述

5、Python?語言描述?

6、Java?語言描述?

7、總結

1、緣起

? ? ? ? 冒泡排序算法 是一個非常經典的算法，它是各大網絡編程平臺上的座上賓，面試官口中的最愛。這個算法就是因其中數字從列表的開始向頂部移動的方式 就像水泡從水中冒出的樣子 而得名，將較大的元素逐步"冒泡"到數組的頂部，從而實現排序。

????????雖然效率不如其他高級排序算法，但冒泡排序算法的思想易于理解和實現，是學習排序算法的入門良品。通過這篇博客讓我們來翔實的了解一下冒泡排序算法吧 ！本篇博客所講解的冒泡排序算法的排序為?升序。

2、BubbleSort 算法描述

? ? ? ? 假設將需要排序的數字列表分成兩個子列表: 已排序的 和 未排序的。在未排序子列表中，最小的元素通過冒泡的方法選出來并移到已排序子列表中。

? ? ? ? 未排序子列表?中的元素從前往后兩兩比較大小，如果一個元素比另外一個元素小，那么將這兩個元素交換位置；否則，不進行任何處理，則進行下一次的元素兩兩比較；直到最大的元素排到合適的位置。最大元素排到合適的位置稱之為一輪排序，一個含有N個元素的數字列表則需要 N-1輪來完成數據排序。

? ? ? ? 為什么是 N-1 輪排序？當未排序子列表剩下兩個元素時，只需要交換一次數據，就完成了整個原始列表的數據排序。所以排序輪數比元素的個數少1。

3、用圖示描述 BubbleSort 算法

注：紅色方塊左邊為未排序元素，右邊為已排序元素?

????????第一輪，從 9 開始并把它與 5 比較，9 大于 5 則這兩個元素進行位置交換。9 大于 7 則這兩個元素進行位置交換。9 大于 1 則這兩個元素進行位置交換。9 大于 3 則這兩個元素進行位置交換，9 到達合適的位置。圖中只給出了每一輪排序后的數字列表，每一輪排序的數據交換細節(jié)并沒給出，我將其留給各位小伙伴作為練習。這里只詳細的寫了第一輪冒泡排序算法的具體過程，剩余輪數也留給各位小伙伴作為練習。

? ? ? ? 上圖中，在第 3 輪后數字列表已經排好順序了，在 4 輪不會有數據交換。如果在元素更多的情況下，在排序輪數還沒達到 N-1 輪，可能整個數字列表就已經排好順序了。如果在排序過程中，數字列表已經提前排好順序，但是算法中沒有提前結束排序的功能，那么這個算法就會跑完 N-1 輪排序才會停止。這時，冒泡排序算法的性能并不是很好。

????????這時，我們可以在算法中包含一個 指示器（標志位），如果在一輪排序中沒有數據交換，說明整個數字列表已經排好順序了，那就停止排序，這樣可以減少冒泡排序算法的排序輪數，改善冒泡排序算法的性能。

4、C?語言描述

#include<stdio.h>

//函數聲明
void BubbleSort(int* arr, int sz);

//冒泡排序法(BubbleSort)
int main()
{
	//將需要排序的數字存入數組
	int arr[] = { 5,4,3,2,1};

	//求數組中元素的個數
	int sz = (sizeof(arr) / sizeof(arr[0]));

	//將數組傳入函數
	BubbleSort(arr, sz);

	//打印已排序的數組
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	
	return 0;
}	

void BubbleSort(int* arr, int sz)
{
	//確定冒泡排序的輪數
	for (int i = 0; i < sz - 1; i++)
	{
		//標志位,假設在排序過程中剩余的元素已經排好順序了
		int flag = 1;

		//每一次冒泡排序
		for (int j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag = 0;
			}
		}

		//在排序過程中已排好序了,就不會有數據交換
		//即標志位就不會重新被賦值
		if (flag == 1)
		{
			break;  //跳出排序輪數循環(huán)
		}
	}
}

?

關鍵代碼解釋：

第二層循環(huán)判斷條件：j < sz - 1 - i?

? ? ? ? 表達式分兩步解釋

? ? ? ? ①? sz - 1:?在一輪排序中，元素兩兩比較的次數比元素個數少1。

? ? ? ? ②? -i? :?減去的是已排序的元素個數，即已排序的元素不參與排序，只排未排序的元素。每一輪排序就會排好一個元素，即排序輪數和已排序元素的個數相同，所以是 -i。

5、Python?語言描述?

def BubbleSort(arr):
    '''冒泡排序算法'''

    # 求數字列表中元素的個數
    sz = len(arr)

    for i in range(sz - 1):

        # 標志位，假設在排序過程中剩余的元素已經排好順序了
        flag = 1

        for j in range(sz - i -1):
            if arr[j] > arr[j + 1]:
                arr[j],arr[j + 1] = arr[j + 1],arr[j]
                flag = 0
    
    # 在排序過程中已經排好順序了，就不會有數據交換
    # 即標志位就不會重新被賦值
        if flag == 1:
            break


if __name__ == '__main__':
    arr = [5,4,3,2,1]
    BubbleSort(arr)
    print("排序后的數字列表")
    for i in range(len(arr)):
        print(arr[i],end = " ")

6、Java?語言描述?

public class BubbleSort 
{
    public static void bubbleSort(int[] arr) 
    {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) 
        {
            # 標志位，假設在排序過程中剩余的元素已經排好順序了
            flag = 1

            for (int j = 0; j < n - i - 1; j++) 
            {
                if (arr[j] > arr[j + 1]) 
                {
                    // 數據交換
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }

        //在排序過程中已排好序了,就不會有數據交換
		//即標志位就不會重新被賦值
		if (flag == 1)
		{
			break;  //跳出排序輪數循環(huán)
		}

        }
     }

    public static void main(String[] args) 
    {
        int[] arr = {5,4,3,2,1};
        bubbleSort(arr);
        System.out.println("排序后的數組：");
        for (int i = 0; i < arr.length; i++) 
        {
            System.out.print(arr[i] + " ");
        }
    }
}

?

7、總結

????????這篇文章寫了 BubbleSort 算法的文字描述、圖示描述和代碼描述。在這里為了方便實現此算法只輸入了 5 個正整數。算法一般情況下具有通用性，所以這個 BubbleSort 算法可以對 n 個整數進行排序。

????????各位小伙伴，也可以拷貝代碼清單試試輸入更多的整數（正整數，0和負整數），看看這個算法能不能對數字列表正確排序。本期的分享總結就到這里了，如果有疑問的小伙伴，我們在評論區(qū)交流嗷，筆者必回，我們下期再見啦 ！

????????文章來源地址http://www.zghlxwxcb.cn/news/detail-775055.html

到了這里，關于【數據結構與算法】冒泡排序算法（BubbleSort）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！