嵌入式算法12---排序算法

關(guān)鍵字：冒泡排序、選擇排序、插入排序、標(biāo)準(zhǔn)庫(kù)函數(shù)qsort

摘要：嵌入式系統(tǒng)中尤其涉及數(shù)據(jù)采集的，需要對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)單處理后再進(jìn)行業(yè)務(wù)層功能，考慮到硬件的資源限制，對(duì)于數(shù)據(jù)排序，一般只是應(yīng)用這四種簡(jiǎn)單的排序算法。本文講解不同算法進(jìn)行從小到大的升序排列的過(guò)程。

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("rn");
}

//從小到大排序
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ù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類(lèi)推，直到所有元素均排序完畢。

算法描述

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)。

獲取更多軟件開(kāi)發(fā)技能，請(qǐng)關(guān)注微信公眾號(hào)?嵌入式系統(tǒng)?。

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

函數(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:rn",?head);

????for(i?=?0;?i?<?size;?i++)
????{
????????printf("%X?%X?%d?[%d]?rn",?wifi[i].bssid_low,?wifi[i].bssid_high,?wifi[i].channel,?wifi[i].rssi);
????}
????printf("rnrn");
}

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ù)量的大小和類(lèi)型，以前原始數(shù)據(jù)是否大概有序，選擇合適的算法滿足需求即可。