[[433624]]

1、冒泡排序

冒泡排序(bubble sort)是一種C語(yǔ)言入門(mén)級(jí)的簡(jiǎn)單排序算法，重復(fù)地走訪過(guò)要排序的元素列，依次比較兩個(gè)相鄰的元素，如果順序錯(cuò)誤進(jìn)行交換。重復(fù)地檢查對(duì)比直到?jīng)]有相鄰元素需要交換，也就是說(shuō)該元素列已經(jīng)排序完成。算法的名字由來(lái)是因?yàn)樵叫?大)的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端(升序或降序排列)，就如同水中的氣泡最終會(huì)上浮到頂端一樣，故名“冒泡排序”。

算法描述

1、比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就進(jìn)行交換

2、對(duì)每一對(duì)相鄰元素作同樣操作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)

3、針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)

4、重復(fù)步驟1~3，直到排序完成

源碼

#include <stdio.h> 
 
#define ARRAY_SIZE 15 
 
void log(char *head, int *data, int len) 
{ 
    unsigned char i; 
 
    printf("%s:", head); 
 
    for(i = 0; i < len; i++) 
    { 
        printf("%02d ", data[i]); 
    } 
    printf("\r\n"); 
} 
 
//從小到大排序 
void bubble_sort(int *data, int size) 
{ 
    int i, j, temp; 
 
    for(i = 0; i < size; i++) 
    { 
        for(j = 0; j < size-i-1; j++) 
        { 
            if(data[j] > data[j + 1])    // 相鄰元素兩兩對(duì)比 
            { 
                temp = data[j + 1];      // 元素交換 
                data[j + 1] = data[j]; 
                data[j] = temp; 
            } 
        } 
    } 
} 
 
int main(void) 
{ 
    int data[ARRAY_SIZE] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; 
 
    log("source", data, ARRAY_SIZE); 
    bubble_sort(data, ARRAY_SIZE); 
    log("sort  ", data, ARRAY_SIZE); 
 
    return 0; 
} 

運(yùn)行結(jié)果

source:03 44 38 05 47 15 36 26 27 02 46 04 19 50 48 
sort  :02 03 04 05 15 19 26 27 36 38 44 46 47 48 50 

2、選擇排序

選擇排序(selection sort)是一種簡(jiǎn)單直觀的排序算法，首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小(大)元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

算法描述

1、初始狀態(tài)，數(shù)據(jù)都屬于無(wú)序區(qū)，有序區(qū)為空

2、從無(wú)序區(qū)中選出最小元素，將它與無(wú)序區(qū)的第1個(gè)元素交換

3、再?gòu)臒o(wú)序區(qū)的下個(gè)元素重復(fù)第2步，直至無(wú)序區(qū)為空

源碼

void selection_sort(int *data, int size) 
{ 
    int i, j, temp; 
    int min; 
 
    for(i = 0; i < size - 1; i++) 
    { 
        min = i; 
        for(j = i + 1; j < size; j++) 
        { 
            if(data[j] < data[min])        // 尋找最小的數(shù) 
            { 
                min = j;                  // 將最小數(shù)的索引保存 
            } 
        } 
 
        if(min != i)    // 需要交互 
        { 
            temp = data[i]; 
            data[i] = data[min]; 
            data[min] = temp; 
        } 
    } 
} 

前面算法的bubble_sort范例替換為selection_sort即可，運(yùn)行結(jié)果一致

3、插入排序

插入排序(insertion sort)的算法，工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

算法描述

1、從第一個(gè)元素開(kāi)始，該元素可認(rèn)為已排序

2、取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

3、如果該元素(已排序)大于新元素，將該元素移到下一位置

4、重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置，將新元素插入到該位置后

5、重復(fù)步驟2~4

源碼

void insertion_sort(int *data, int size) 
{ 
    int i, pre, current; 
 
    for(i = 1; i < size; i++) 
    { 
        pre = i - 1; 
        current = data[i]; 
 
        while(pre >= 0 && data[pre] > current)  //當(dāng)前元素與的有序區(qū)逐個(gè)比較再插入 
        { 
            data[pre + 1] = data[pre]; 
            pre--; 
        } 
        data[pre + 1] = current; 
    } 
} 

4、標(biāo)準(zhǔn)庫(kù)函數(shù)qsort

前面三種排序算法都只是針對(duì)單個(gè)元素進(jìn)行排序，但實(shí)際應(yīng)用中，基于某個(gè)數(shù)值對(duì)一個(gè)大結(jié)構(gòu)體進(jìn)行排序，比如wifi信息結(jié)構(gòu)體數(shù)組，包括其mac、名稱、加密信息、和信號(hào)強(qiáng)度，依據(jù)信息強(qiáng)度對(duì)wifi信息進(jìn)行排序，每次數(shù)據(jù)交換意味著兩次內(nèi)存拷貝，這種場(chǎng)景下采用選擇排序略優(yōu)。

相比于自己造輪子，C語(yǔ)言標(biāo)準(zhǔn)庫(kù)函數(shù)也許更合適;qsort函數(shù)是C語(yǔ)言自帶的排序函數(shù)，包含在中。

函數(shù)原型

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)) 

base - 指針，數(shù)組的第一個(gè)元素進(jìn)行排序

nitems - 數(shù)組中的元素?cái)?shù)目

size - 數(shù)組中的每個(gè)元素的大小(以字節(jié)為單位)

compar - 基于這個(gè)函數(shù)比較兩個(gè)元素

返回：值不返回任何值

缺點(diǎn)：對(duì)于有多個(gè)重復(fù)值的數(shù)組來(lái)說(shuō)，效率較低不穩(wěn)定

范例

//qsort要結(jié)合compare使用 
int compare(const void *value1, const void *value2) 
{ 
    //升序或降序在此調(diào)整 
    return (*(int*)value1 - *(int*)value2); 
} 
 
int main(void) 
{ 
    int data[ARRAY_SIZE] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; 
 
    log("source", data, ARRAY_SIZE); 
    qsort(data, ARRAY_SIZE, sizeof(int), compare); 
    log("sort  ", data, ARRAY_SIZE); 
 
    return 0; 
} 

其效果和前面三種算法一樣，而且可擴(kuò)展針對(duì)結(jié)構(gòu)體內(nèi)某個(gè)元素值對(duì)整體排序，滿足前面的wifi信息按信號(hào)強(qiáng)度排序的需求。

#include <stdio.h> 
#define WIFI_AP_MAX 5 
 
typedef unsigned char       uint8_t; 
typedef signed char         int8_t; 
typedef unsigned short      uint16_t; 
typedef signed short        int16_t; 
typedef unsigned int        uint32_t; 
 
typedef struct 
{ 
    uint32_t bssid_low;  // mac address low 
    uint16_t bssid_high; // mac address high 
    uint8_t channel;     // channel id 
    int8_t rssi;         // signal strength <sort> 
} wifiApInfo_t; 
 
//qsort要結(jié)合compare使用，按信號(hào)強(qiáng)度rssi升序排列 
int compare(const void *value1, const void *value2) 
{ 
    const wifiApInfo_t *ctx1 = (const wifiApInfo_t *)value1; 
    const wifiApInfo_t *ctx2 = (const wifiApInfo_t *)value2; 
    return (ctx1->rssi - ctx2->rssi); 
} 
 
static wifiApInfo_t wifiApInfo[WIFI_AP_MAX] = 
{ 
    {0x5555, 0x55, 5, -55}, 
    {0x1111, 0x11, 1, -51}, 
    {0x3333, 0x33, 3, -53}, 
    {0x4444, 0x44, 4, -54}, 
    {0x2222, 0x22, 2, -52}, 
}; 
 
void wifi_log(char *head, void *data, int size) 
{ 
    unsigned char i; 
    const wifiApInfo_t *wifi = (wifiApInfo_t *)data; 
 
    printf("%s:\r\n", head); 
 
    for(i = 0; i < size; i++) 
    { 
        printf("%X %X %d [%d] \r\n", wifi[i].bssid_low, wifi[i].bssid_high, wifi[i].channel, wifi[i].rssi); 
    } 
    printf("\r\n\r\n"); 
} 
 
int main(void) 
{ 
    wifi_log("source", wifiApInfo, WIFI_AP_MAX); 
    qsort(wifiApInfo, WIFI_AP_MAX, sizeof(wifiApInfo_t), compare); 
    wifi_log("sort", wifiApInfo, WIFI_AP_MAX); 
 
    return 0; 
} 

運(yùn)行結(jié)果

source: 
5555 55 5 [-55] 
1111 11 1 [-51] 
3333 33 3 [-53] 
4444 44 4 [-54] 
2222 22 2 [-52] 
 
//依據(jù)信號(hào)強(qiáng)度關(guān)鍵字，對(duì)wifi信息整體數(shù)據(jù)同步進(jìn)行了排序 
sort: 
5555 55 5 [-55] 
4444 44 4 [-54] 
3333 33 3 [-53] 
2222 22 2 [-52] 
1111 11 1 [-51] 

5、總結(jié)

沒(méi)有最好的排序算法，選擇哪種方式需要結(jié)合待排序數(shù)據(jù)量的大小和類型，以前原始數(shù)據(jù)是否大概有序，選擇合適的算法滿足需求即可。