搜尋

冒泡 排序

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

一. 演算法描述

    冒泡 排序:依序比較鄰近的數據,將小數據放在前,大數據放在後;即第一趟先比較第1個和第2個數,大數在後,小數在前,再比較第2個數與第3個數,大數在後,小數在前,以此類推則將最大的數"滾動"到最後一個位置;第二趟則將次大的數字滾動到倒數第二個位置......第n-1(n為無序資料的個數)趟即能完成排序。

以下面5個無序的數據為例:

40 8 15 18 12 (文中僅細化了第一趟的比較過程)

第1趟: 8 15 18 12 40

第1趟: 8 15 18 12 40冒泡 排序

第1趟2趟: 8 15 12 18 40

第3趟: 8 12 15 18 40

第4趟: 8 12 15 18 40

二. 行程分析

複雜度:O(1)  (用於交換)

穩定性:穩定

三.演算法實作

//交换data1和data2所指向的整形  
void DataSwap(int* data1, int* data2)  
{  
    int temp = *data1;  
    *data1 = *data2;  
    *data2 = temp;  
}  
  
/******************************************************** 
*函数名称:BubbleSort 
*参数说明:pDataArray 无序数组; 
*          iDataNum为无序数据个数 
*说明:    冒泡 排序 
*********************************************************/  
void BubbleSort(int* pDataArray, int iDataNum)  
{  
    for (int i = 0; i < iDataNum - 1; i++)   //走iDataNum-1趟  
        for (int j = 0; j < iDataNum - i - 1; j++)      
            if (pDataArray[j] > pDataArray[j + 1])  
                DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
}

四. 演算法最佳化

還可以對冒泡 排序演算法進行簡單的最佳化,用一個標記來記錄演算法最佳化

還可以對冒泡 排序演算法進行簡單的最佳化,用一個標記來記錄在一趟的比較過程中是否存在交換,如果不存在交換則整個數組已經有序退出排序過程,反之則繼續進行下一趟的比較。

/******************************************************** 
*函数名称:BubbleSort 
*参数说明:pDataArray 无序数组; 
*          iDataNum为无序数据个数 
*说明:    冒泡 排序 
*********************************************************/  
void BubbleSort(int* pDataArray, int iDataNum)  
{  
    BOOL flag = FALSE;    //记录是否存在交换  
    for (int i = 0; i < iDataNum - 1; i++)    //走iDataNum-1趟  
    {  
        flag = FALSE;  
        for (int j = 0; j < iDataNum - i - 1; j++)      
            if (pDataArray[j] > pDataArray[j + 1])  
            {  
                flag = TRUE;  
                DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
            }  
          
        if (!flag)    //上一趟比较中不存在交换,则退出排序  
            break;  
    }  
}



更多冒泡 排序相關文章請關注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

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

熱工具

WebStorm Mac版

WebStorm Mac版

好用的JavaScript開發工具

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器