關(guān)鍵字:冒泡排序、選擇排序、插入排序、標(biāo)準(zhǔn)庫函數(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)行從小到大的升序排列的過程。
#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é)果
sort:020304051519262736384446474850
{
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;
}
}
}
{
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;
}
}
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)度排序的需求。
#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é)果
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]
1、冒泡排序
冒泡排序(bubble sort)是一種C語言入門級(jí)的簡(jiǎn)單排序算法,重復(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)是一種簡(jiǎn)單直觀的排序算法,首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?,然后,再從剩余未排序元素中繼續(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)存拷貝,這種場(chǎng)景下采用選擇排序略優(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ù)是否大概有序,選擇合適的算法滿足需求即可。
聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請(qǐng)聯(lián)系本站處理。
舉報(bào)投訴
-
嵌入式
+關(guān)注
關(guān)注
5053文章
18915瀏覽量
300869
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
時(shí)間復(fù)雜度為 O(n^2) 的排序算法
作者:京東保險(xiǎn) 王奕龍 對(duì)于小規(guī)模數(shù)據(jù),我們可以選用時(shí)間復(fù)雜度為 O(n2) 的排序算法。因?yàn)闀r(shí)間復(fù)雜度并不代表實(shí)際代碼的執(zhí)行時(shí)間,它省去了低階、系數(shù)和常數(shù),僅代表的增長(zhǎng)趨勢(shì),所以在小規(guī)模數(shù)據(jù)情況下
嵌入式主板是什么意思?嵌入式主板全面解析
嵌入式主板,通常被稱為嵌入式系統(tǒng)的核心組件,是一種用于控制和數(shù)據(jù)處理的計(jì)算機(jī)硬件,其設(shè)計(jì)旨在嵌入特定設(shè)備中執(zhí)行專門任務(wù)。嵌入式主板如同是設(shè)備的“大腦”,主要功能是根據(jù)需要管理和控制設(shè)備
嵌入式軟件開發(fā)與AI整合
嵌入式軟件開發(fā)與AI整合是當(dāng)前技術(shù)發(fā)展的重要趨勢(shì)之一。隨著人工智能技術(shù)的快速發(fā)展,嵌入式系統(tǒng)越來越多地集成了AI算法,以實(shí)現(xiàn)更復(fù)雜的智能功能。以下是關(guān)于嵌入式軟件開發(fā)與AI整合的詳細(xì)分
深度學(xué)習(xí)算法在嵌入式平臺(tái)上的部署
隨著人工智能技術(shù)的飛速發(fā)展,深度學(xué)習(xí)算法在各個(gè)領(lǐng)域的應(yīng)用日益廣泛。然而,將深度學(xué)習(xí)算法部署到資源受限的嵌入式平臺(tái)上,仍然是一個(gè)具有挑戰(zhàn)性的任務(wù)。本文將從嵌入式平臺(tái)的特點(diǎn)、深度學(xué)習(xí)
嵌入式開發(fā)就業(yè)前景怎么樣?
,嵌入式開發(fā)的主要工作是開發(fā)各種工業(yè)控制設(shè)備和系統(tǒng),如數(shù)控機(jī)床、工業(yè)機(jī)器人、智能制造等。嵌入式開發(fā)人員需要掌握相關(guān)的硬件和軟件技術(shù),如處理器、傳感器、通信技術(shù)、工業(yè)控制算法等,同時(shí)也需要具備一定的機(jī)械和電子
發(fā)表于 06-07 14:51
fpga是嵌入式嗎
FPGA(現(xiàn)場(chǎng)可編程門陣列)不是嵌入式系統(tǒng),但FPGA在嵌入式系統(tǒng)中有著重要的應(yīng)用。
FPGA實(shí)現(xiàn)雙調(diào)排序算法的探索與實(shí)踐
雙調(diào)排序(BitonicSort)是數(shù)據(jù)獨(dú)立(Data-independent)的排序算法,即比較順序與數(shù)據(jù)無關(guān),特別適合并行執(zhí)行。在了解雙調(diào)排序算
發(fā)表于 03-14 09:50
?459次閱讀
嵌入式人工智能的就業(yè)方向有哪些?
操作系統(tǒng)使用及C高級(jí)編程 數(shù)據(jù)結(jié)構(gòu)與算法 二:嵌入式Linux應(yīng)用工程師,Linux網(wǎng)絡(luò)開發(fā)工程師 文件IO 并發(fā)程序設(shè)計(jì) 項(xiàng)目實(shí)戰(zhàn):基于Linux的Flappybird游戲開發(fā) 網(wǎng)絡(luò)編程開發(fā)及實(shí)戰(zhàn)上
發(fā)表于 02-26 10:17
C語言實(shí)現(xiàn)經(jīng)典排序算法概覽
冒泡排序(英語:Bubble Sort)是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順序(如從大到小、首字母從A到Z)錯(cuò)誤就把他們交換過來。
嵌入式軟件開發(fā)應(yīng)該掌握哪些知識(shí)?
的控制,如GPIO、串口、SPI、I2C 等。這使得嵌入式軟件開發(fā)人員能夠充分利用硬件資源,滿足特定的需求。 1.2數(shù)據(jù)結(jié)構(gòu)與算法 嵌入式系統(tǒng)通常具有有限的內(nèi)存資源。通過使用合適的數(shù)據(jù)結(jié)構(gòu)和算
發(fā)表于 02-19 11:23
什么是嵌入式系統(tǒng)?嵌入式系統(tǒng)的具體應(yīng)用
嵌入式,一般是指嵌入式系統(tǒng)。用于控制、監(jiān)視或者輔助操作機(jī)器和設(shè)備的裝置。
十大排序算法總結(jié)
排序算法是最經(jīng)典的算法知識(shí)。因?yàn)槠鋵?shí)現(xiàn)代碼短,應(yīng)該廣,在面試中經(jīng)常會(huì)問到排序算法及其相關(guān)的問題。一般在面試中最??嫉氖强焖?/div>
嵌入式課程設(shè)計(jì)報(bào)告-數(shù)據(jù)排序過程演示
電子發(fā)燒友網(wǎng)站提供《嵌入式課程設(shè)計(jì)報(bào)告-數(shù)據(jù)排序過程演示.doc》資料免費(fèi)下載
發(fā)表于 10-26 09:30
?0次下載
評(píng)論