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

關鍵字：冒泡排序、選擇排序、插入排序、標準庫函數(shù)qsort

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

1、冒泡排序

冒泡排序（bubble sort）是一種C語言入門級的簡單排序算法，重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序錯誤進行交換。重復地檢查對比直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。算法的名字由來是因為越小(大)的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同水中的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

算法描述

1、比較相鄰的元素。如果第一個比第二個大，就進行交換

2、對每一對相鄰元素作同樣操作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數(shù)

3、針對所有的元素重復以上的步驟，除了最后一個

4、重復步驟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])????//?相鄰元素兩兩對比
????????????{
????????????????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;
}

運行結果

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)是一種簡單直觀的排序算法，首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

算法描述

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

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

3、再從無序區(qū)的下個元素重復第2步，直至無序區(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即可，運行結果一致

3、插入排序

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

算法描述

1、從第一個元素開始，該元素可認為已排序

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

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

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

5、重復步驟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)??//當前元素與的有序區(qū)逐個比較再插入
????????{
????????????data[pre?+?1]?=?data[pre];
????????????pre--;
????????}
????????data[pre?+?1]?=?current;
????}
}

4、標準庫函數(shù)qsort

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

獲取更多軟件開發(fā)技能，請關注微信公眾號?嵌入式系統(tǒng)?。

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

函數(shù)原型

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

base - ?指針，數(shù)組的第一個元素進行排序

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

size ?- 數(shù)組中的每個元素的大?。ㄒ宰止?jié)為單位）

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

返回：值不返回任何值

缺點：對于有多個重復值的數(shù)組來說，效率較低不穩(wěn)定

范例

//qsort要結合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;
}

其效果和前面三種算法一樣，而且可擴展針對結構體內(nèi)某個元素值對整體排序，滿足前面的wifi信息按信號強度排序的需求。

#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要結合compare使用，按信號強度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;
}

運行結果

source:
5555?55?5?[-55]
1111?11?1?[-51]
3333?33?3?[-53]
4444?44?4?[-54]
2222?22?2?[-52]

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

5、總結

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