關(guān)鍵字：冒泡排序、選擇排序、插入排序、標(biāo)準(zhǔn)庫函數(shù)qsort摘要：嵌入式系統(tǒng)中尤其涉及數(shù)據(jù)采集的，需要對(duì)數(shù)據(jù)進(jìn)行簡單處理后再進(jìn)行業(yè)務(wù)層功能，考慮到硬件的資源限制，對(duì)于數(shù)據(jù)排序，一般只是應(yīng)用這四種簡單的排序算法。本文講解不同算法進(jìn)行從小到大的升序排列的過程。

1、冒泡排序

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

1、比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就進(jìn)行交換2、對(duì)每一對(duì)相鄰元素作同樣操作，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)3、針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)4、重復(fù)步驟1~3，直到排序完成

源碼

#include

#defineARRAY_SIZE15

voidlog(char*head,int*data,intlen)
{
unsignedchari;

printf("%s:",head);

for(i=0;i {
printf("%02d",data[i]);
}
printf("\r\n");
}

//從小到大排序
voidbubble_sort(int*data,intsize)
{
inti,j,temp;

for(i=0;i {
for(j=0;j-1;j++)
{
if(data[j]>data[j+1])//相鄰元素兩兩對(duì)比
{
temp=data[j+1];//元素交換
data[j+1]=data[j];
data[j]=temp;
}
}
}
}

intmain(void)
{
intdata[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);

return0;
}
運(yùn)行結(jié)果

source:034438054715362627024604195048
sort:020304051519262736384446474850

2、選擇排序

選擇排序(selection sort)是一種簡單直觀的排序算法，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。算法描述

1、初始狀態(tài)，數(shù)據(jù)都屬于無序區(qū)，有序區(qū)為空2、從無序區(qū)中選出最小元素，將它與無序區(qū)的第1個(gè)元素交換3、再從無序區(qū)的下個(gè)元素重復(fù)第2步，直至無序區(qū)為空

源碼

voidselection_sort(int*data,intsize)
{
inti,j,temp;
intmin;

for(i=0;i1;i++)
{
min=i;
for(j=i+1;j {
if(data[j]//尋找最小的數(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）的算法，工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。算法描述

1、從第一個(gè)元素開始，該元素可認(rèn)為已排序2、取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描3、如果該元素（已排序）大于新元素，將該元素移到下一位置4、重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置，將新元素插入到該位置后5、重復(fù)步驟2~4

源碼

voidinsertion_sort(int*data,intsize)
{
inti,pre,current;

for(i=1;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)庫函數(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)存拷貝，這種場景下采用選擇排序略優(yōu)。相比于自己造輪子，C語言標(biāo)準(zhǔn)庫函數(shù)也許更合適；qsort函數(shù)是C語言自帶的排序函數(shù)，包含在中。函數(shù)原型

voidqsort(void*base,size_tnitems,size_tsize,int(*compar)(constvoid*,constvoid*))

base - 指針，數(shù)組的第一個(gè)元素進(jìn)行排序nitems-數(shù)組中的元素?cái)?shù)目size - 數(shù)組中的每個(gè)元素的大小（以字節(jié)為單位）compar - 基于這個(gè)函數(shù)比較兩個(gè)元素返回值：不返回任何值缺點(diǎn)：對(duì)于有多個(gè)重復(fù)值的數(shù)組來說，效率較低不穩(wěn)定

范例

//qsort要結(jié)合compare使用
intcompare(constvoid*value1,constvoid*value2)
{
//升序或降序在此調(diào)整
return(*(int*)value1-*(int*)value2);
}

intmain(void)
{
intdata[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);

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

#include
#defineWIFI_AP_MAX5

typedefunsignedcharuint8_t;
typedefsignedcharint8_t;
typedefunsignedshortuint16_t;
typedefsignedshortint16_t;
typedefunsignedintuint32_t;

typedefstruct
{
uint32_tbssid_low;//macaddresslow
uint16_tbssid_high;//macaddresshigh
uint8_tchannel;//channelid
int8_trssi;//signalstrength <sort>
}wifiApInfo_t;

//qsort要結(jié)合compare使用，按信號(hào)強(qiáng)度rssi升序排列
intcompare(constvoid*value1,constvoid*value2)
{
constwifiApInfo_t*ctx1=(constwifiApInfo_t*)value1;
constwifiApInfo_t*ctx2=(constwifiApInfo_t*)value2;
return(ctx1->rssi-ctx2->rssi);
}

staticwifiApInfo_twifiApInfo[WIFI_AP_MAX]=
{
{0x5555,0x55,5,-55},
{0x1111,0x11,1,-51},
{0x3333,0x33,3,-53},
{0x4444,0x44,4,-54},
{0x2222,0x22,2,-52},
};

voidwifi_log(char*head,void*data,intsize)
{
unsignedchari;
constwifiApInfo_t*wifi=(wifiApInfo_t*)data;

printf("%s:\r\n",head);

for(i=0;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");
}

intmain(void)
{
wifi_log("source",wifiApInfo,WIFI_AP_MAX);
qsort(wifiApInfo,WIFI_AP_MAX,sizeof(wifiApInfo_t),compare);
wifi_log("sort",wifiApInfo,WIFI_AP_MAX);

return0;
}運(yùn)行結(jié)果

source:
5555555[-55]
1111111[-51]
3333333[-53]
4444444[-54]
2222222[-52]

//依據(jù)信號(hào)強(qiáng)度關(guān)鍵字，對(duì)wifi信息整體數(shù)據(jù)同步進(jìn)行了排序
sort:
5555555[-55]
4444444[-54]
3333333[-53]
2222222[-52]
1111111[-51]

5、總結(jié)

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