嵌入式算法之排序算法
1、冒泡排序
冒泡排序(bubble sort)是一種C語言入門級的簡單排序算法，重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序錯誤進行交換。重復地檢查對比直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。算法的名字由來是因為越小(大)的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端(升序或降序排列)，就如同水中的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。
算法描述
1、比較相鄰的元素。如果第一個比第二個大，就進行交換
2、對每一對相鄰元素作同樣操作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應該會是最大的數(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("\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]) // 相鄰元素兩兩對比
- {
- 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;
- }
運行結(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)是一種簡單直觀的排序算法，首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(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即可，運行結(jié)果一致
3、插入排序
插入排序(insertion sort)的算法，工作原理是通過構(gòu)建有序序列，對于未排序數(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ù)值對一個大結(jié)構(gòu)體進行排序，比如wifi信息結(jié)構(gòu)體數(shù)組，包括其mac、名稱、加密信息、和信號強度，依據(jù)信息強度對wifi信息進行排序，每次數(shù)據(jù)交換意味著兩次內(nèi)存拷貝，這種場景下采用選擇排序略優(yōu)。
相比于自己造輪子，C語言標準庫函數(shù)也許更合適;qsort函數(shù)是C語言自帶的排序函數(shù)，包含在
函數(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要結(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;
- }
其效果和前面三種算法一樣，而且可擴展針對結(jié)構(gòu)體內(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要結(jié)合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:\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;
- }
運行結(jié)果
- 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、總結(jié)
沒有最好的排序算法，選擇哪種方式需要結(jié)合待排序數(shù)據(jù)量的大小和類型，以前原始數(shù)據(jù)是否大概有序，選擇合適的算法滿足需求即可。
