搜尋
首頁php教程PHP开发排序演算法入門冒泡排序

排序演算法入門冒泡排序

Dec 19, 2016 pm 01:13 PM
冒泡排序

在開發中,對一組資料進行有序地排列是經常需要做的事情,所以掌握幾種甚至更多的排序演算法是絕對有必要的

本文章介紹的是排序演算法中較簡單的一種演算法:冒泡排序

先嘗試用最簡單的想法去實現排序,以此來比較學習冒泡排序

問題:設有一數組,其大小為10個元素(int   str[10])數組內的數據是無序。現在要求我們透過程式將這個無序的陣列變成一個從小到大排序的陣列(從下標為0開始)

思路:按照題目的要求,毫無疑問,正確的結果應該就像這樣: 1 2 3 4 5 6 7 8 9 10   要做到這樣,最簡單且最直接想到的方法就是進行對比交換。


首先,將10個數裡最小的個數放到下標為0的位置上(str[0])

通過將下標為0的數(str[0])與剩下其餘9個數字進行對比交換(將較少者放置在下標為0的位置上),就可以得到這10個數最小的那個

10個數最小的那位確定後,接下來就要找剩下9個數最小的那個。

因為已經確定出一個最小的數,所以就不要動str[0],直接從str[1]開始,與剩下的8個數對比交換,找出9個數中最小的那位放到下標為1(str[1])的位置上

繼續按照這個思路就可以將這十個數變成有序的(從小到大)的數組

代碼:

#include <stdio.h>  
  
void swap(int *a, int *b); //交换两个数  
  
int main()  
{  
    int     str[10];  
    int     i, j;  
    //初始化数组为10 9 8 7 6 5 4 3 2 1  
    for (i = 0; i < 10; i++)  
    {  
        str[i] = 10 - i;  
    }  
    //排序,从a[0]开始排,从小到大  
    for (i = 0; i < 10; i++)  
    {  
        for (j = i + 1; j < 10; j++)  
        {  
            if (str[i] > str[j])  
            {  
                swap(&str[i], &str[j]);  
            }  
        }  
    }  
        //将十个数输出  
    for (i = 0; i < 10; i++)  
        printf("%d\n", str[i]);  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int     c;  
     c = *a;  
    *a = *b;  
    *b =  c;  
}

這個方法是比較容易想到的實作方法。但存在不足:就是原本位於前面的較小數字被交換到後面


演示:

開始:9 4 5 6 8 3 2 7 10 1  (下標從左到右分別是0~9)依照上面的程序進行比較交換

第一次:4 9 5 6 8 3 2 7 10 1 

第二次:4 9 5 6 8 3 2 7 10 1 

。 。 。 :(無交換)

第五次:3 9 5 6 8 4 2 7 10 1 

第六次:2 9 5 6 8 3 4 7 10 1 

。 。 。 :(沒有交換)

第十次:1 9 5 6 8 3 4 7 10 2 

可以看出,原來較小的數是在前面的,經過一輪的交換後放到後面了

那麼怎樣解決這個不足呢?可以使用冒泡排序

什麼是冒泡排序呢?

你可以這樣理解:(從小到大排序)存在10個不同大小的氣泡,由底至上地把較少的氣泡逐步地向上升,這樣經過遍歷一次後,最小的氣泡就會被上升到頂(下標為0),然後再從底至上地這樣升,循環直到十個氣泡大小有序。

在冒泡排序中,最重要的思想是兩兩比較,將兩者較少的升上去

冒泡排序最壞情況的時間複雜度是O(n²)

代碼:

#include <stdio.h>  
void swap(int *a, int *b);  
int main()  
{  
    int    array[10] = {15, 225, 34, 42, 52, 6, 7856, 865, 954, 10};  
    int    i, j;  
    for (i = 0; i < 10; i++)  
    {  
        //每一次由底至上地上升  
        for (j = 9; j > i; j--)  
        {  
            if (array[j] < array[j-1])  
            {  
                    swap(&array[j], &array[j-1]);  
            }  
        }  
    }  
    for (i = 0; i < 10; i++)  
    {  
        printf("%d\n", array[i]);  
    }  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int    temp;  
    temp = *a;  
      *a = *b;  
      *b = temp;  
}

冒泡排序演算法只會將較少的逐步向上推,不會造成文章前面所說的不足,這裡就不給予示範。



更多排序演算法入門之冒泡排序相關文章請關注PHP中文網!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

SublimeText3 英文版

SublimeText3 英文版

推薦:為Win版本,支援程式碼提示!

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

WebStorm Mac版

WebStorm Mac版

好用的JavaScript開發工具

mPDF

mPDF

mPDF是一個PHP庫,可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件,並處理不同的語言。與原始腳本如HTML2FPDF相比,它的速度較慢,並且在使用Unicode字體時產生的檔案較大,但支援CSS樣式等,並進行了大量增強。支援幾乎所有語言,包括RTL(阿拉伯語和希伯來語)和CJK(中日韓)。支援嵌套的區塊級元素(如P、DIV),