21ic电子技术开发论坛 › 单片机与嵌入式系统 › GigaDevice GD32 MCU › 【转】嵌入式算法12---排序算法
返回列表 发新帖我要提问

【转】嵌入式算法12---排序算法

[复制链接]
785|10
 楼主| 电竞孔乙己 发表于 2022-5-5 16:22 | 显示全部楼层 |阅读模式
https://mp.weixin.qq.com/s/SlEpZDhT1BRl05RPfVjc5w

关键字：冒泡排序、选择排序、插入排序、标准库函数qsort

摘要：嵌入式系统中尤其涉及数据采集的，需要对数据进行简单处理后再进行业务层功能，考虑到硬件的资源限制，对于数据排序，一般只是应用这四种简单的排序算法。本文讲解不同算法进行从小到大的升序排列的过程。

1、冒泡排序

冒泡排序（bubble sort）是一种C语言入门级的简单排序算法，重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误进行交换。重复地检查对比直到没有相邻元素需要交换，也就是说该元素列已经排序完成。算法的名字由来是因为越小(大)的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同水中的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法描述

1、比较相邻的元素。如果第一个比第二个大，就进行交换

2、对每一对相邻元素作同样操作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数

3、针对所有的元素重复以上的步骤，除了最后一个

4、重复步骤1~3，直到排序完成

74945627389172d14a.png

源码

复制
  1. #include <stdio.h>
    


  2. 

  3. #define ARRAY_SIZE 15
    


  4. 

  5. void log(char *head, int *data, int len)
    

  6. {
    

  7.     unsigned char i;
    


  8. 

  9.     printf("%s:", head);
    


  10. 

  11.     for(i = 0; i < len; i++)
    

  12.     {
    

  13.         printf("%02d ", data[i]);
    

  14.     }
    

  15.     printf("\r\n");
    

  16. }
    


  17. 

  18. //从小到大排序
    

  19. void bubble_sort(int *data, int size)
    

  20. {
    

  21.     int i, j, temp;
    


  22. 

  23.     for(i = 0; i < size; i++)
    

  24.     {
    

  25.         for(j = 0; j < size-i-1; j++)
    

  26.         {
    

  27.             if(data[j] > data[j + 1])    // 相邻元素两两对比
    

  28.             {
    

  29.                 temp = data[j + 1];      // 元素交换
    

  30.                 data[j + 1] = data[j];
    

  31.                 data[j] = temp;
    

  32.             }
    

  33.         }
    

  34.     }
    

  35. }
    


  36. 

  37. int main(void)
    

  38. {
    

  39.     int data[ARRAY_SIZE] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    


  40. 

  41.     log("source", data, ARRAY_SIZE);
    

  42.     bubble_sort(data, ARRAY_SIZE);
    

  43.     log("sort  ", data, ARRAY_SIZE);
    


  44. 

  45.     return 0;
    

  46. }

运行结果

复制
  1. source:03 44 38 05 47 15 36 26 27 02 46 04 19 50 48
    

  2. sort  :02 03 04 05 15 19 26 27 36 38 44 46 47 48 50


73005627388f2c03ac.png
96293627388fe70cf9.png
回复

收藏 举报

 楼主| 电竞孔乙己 发表于 2022-5-5 16:23 | 显示全部楼层
2、选择排序

选择排序(selection sort)是一种简单直观的排序算法，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述

1、初始状态，数据都属于无序区，有序区为空

2、从无序区中选出最小元素，将它与无序区的第1个元素交换

3、再从无序区的下个元素重复第2步，直至无序区为空

36914627389626a9fc.png

源码

复制
  1. void selection_sort(int *data, int size)
    

  2. {
    

  3.     int i, j, temp;
    

  4.     int min;
    


  5. 

  6.     for(i = 0; i < size - 1; i++)
    

  7.     {
    

  8.         min = i;
    

  9.         for(j = i + 1; j < size; j++)
    

  10.         {
    

  11.             if(data[j] < data[min])        // 寻找最小的数
    

  12.             {
    

  13.                 min = j;                  // 将最小数的索引保存
    

  14.             }
    

  15.         }
    


  16. 

  17.         if(min != i)    // 需要交互
    

  18.         {
    

  19.             temp = data[i];
    

  20.             data[i] = data[min];
    

  21.             data[min] = temp;
    

  22.         }
    

  23.     }
    

  24. }

前面算法的bubble_sort范例替换为selection_sort即可，运行结果一致


回复

收藏 举报

 楼主| 电竞孔乙己 发表于 2022-5-5 16:24 | 显示全部楼层
3、插入排序

插入排序（insertion sort）的算法，工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述

1、从第一个元素开始，该元素可认为已排序

2、取出下一个元素，在已经排序的元素序列中从后向前扫描

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

4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置后

5、重复步骤2~4

355626273899042ea3.png

源码

复制
  1. void insertion_sort(int *data, int size)
    

  2. {
    

  3.     int i, pre, current;
    


  4. 

  5.     for(i = 1; i < size; i++)
    

  6.     {
    

  7.         pre = i - 1;
    

  8.         current = data[i];
    


  9. 

  10.         while(pre >= 0 && data[pre] > current)  //当前元素与的有序区逐个比较再插入
    

  11.         {
    

  12.             data[pre + 1] = data[pre];
    

  13.             pre--;
    

  14.         }
    

  15.         data[pre + 1] = current;
    

  16.     }
    

  17. }


回复

收藏 举报

 楼主| 电竞孔乙己 发表于 2022-5-5 16:25 | 显示全部楼层
4、标准库函数qsort

前面三种排序算法都只是针对单个元素进行排序，但实际应用中，基于某个数值对一个大结构体进行排序，比如wifi信息结构体数组，包括其mac、名称、加密信息、和信号强度，依据信息强度对wifi信息进行排序，每次数据交换意味着两次内存拷贝，这种场景下采用选择排序略优。

相比于自己造轮子，C语言标准库函数也许更合适；qsort函数是C语言自带的排序函数，包含在<stdlib.h>中。

函数原型

复制
  1. void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

base -  指针，数组的第一个元素进行排序

nitems - 数组中的元素数目

size  - 数组中的每个元素的大小（以字节为单位）

compar - 基于这个函数比较两个元素

返回值：不返回任何值

缺点：对于有多个重复值的数组来说，效率较低不稳定

范例

复制
  1. //qsort要结合compare使用
    

  2. int compare(const void *value1, const void *value2)
    

  3. {
    

  4.     //升序或降序在此调整
    

  5.     return (*(int*)value1 - *(int*)value2);
    

  6. }
    


  7. 

  8. int main(void)
    

  9. {
    

  10.     int data[ARRAY_SIZE] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    


  11. 

  12.     log("source", data, ARRAY_SIZE);
    

  13.     qsort(data, ARRAY_SIZE, sizeof(int), compare);
    

  14.     log("sort  ", data, ARRAY_SIZE);
    


  15. 

  16.     return 0;
    

  17. }

其效果和前面三种算法一样，而且可扩展针对结构体内某个元素值对整体排序，满足前面的wifi信息按信号强度排序的需求。

复制
  1. #include <stdio.h>
    

  2. #define WIFI_AP_MAX 5
    


  3. 

  4. typedef unsigned char       uint8_t;
    

  5. typedef signed char         int8_t;
    

  6. typedef unsigned short      uint16_t;
    

  7. typedef signed short        int16_t;
    

  8. typedef unsigned int        uint32_t;
    


  9. 

  10. typedef struct
    

  11. {
    

  12.     uint32_t bssid_low;  // mac address low
    

  13.     uint16_t bssid_high; // mac address high
    

  14.     uint8_t channel;     // channel id
    

  15.     int8_t rssi;         // signal strength <sort>
    

  16. } wifiApInfo_t;
    


  17. 

  18. //qsort要结合compare使用，按信号强度rssi升序排列
    

  19. int compare(const void *value1, const void *value2)
    

  20. {
    

  21.     const wifiApInfo_t *ctx1 = (const wifiApInfo_t *)value1;
    

  22.     const wifiApInfo_t *ctx2 = (const wifiApInfo_t *)value2;
    

  23.     return (ctx1->rssi - ctx2->rssi);
    

  24. }
    


  25. 

  26. static wifiApInfo_t wifiApInfo[WIFI_AP_MAX] =
    

  27. {
    

  28.     {0x5555, 0x55, 5, -55},
    

  29.     {0x1111, 0x11, 1, -51},
    

  30.     {0x3333, 0x33, 3, -53},
    

  31.     {0x4444, 0x44, 4, -54},
    

  32.     {0x2222, 0x22, 2, -52},
    

  33. };
    


  34. 

  35. void wifi_log(char *head, void *data, int size)
    

  36. {
    

  37.     unsigned char i;
    

  38.     const wifiApInfo_t *wifi = (wifiApInfo_t *)data;
    


  39. 

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


  41. 

  42.     for(i = 0; i < size; i++)
    

  43.     {
    

  44.         printf("%X %X %d [%d] \r\n", wifi[i].bssid_low, wifi[i].bssid_high, wifi[i].channel, wifi[i].rssi);
    

  45.     }
    

  46.     printf("\r\n\r\n");
    

  47. }
    


  48. 

  49. int main(void)
    

  50. {
    

  51.     wifi_log("source", wifiApInfo, WIFI_AP_MAX);
    

  52.     qsort(wifiApInfo, WIFI_AP_MAX, sizeof(wifiApInfo_t), compare);
    

  53.     wifi_log("sort", wifiApInfo, WIFI_AP_MAX);
    


  54. 

  55.     return 0;
    

  56. }
    

  57. 运行结果
    


  58. 

  59. source:
    

  60. 5555 55 5 [-55]
    

  61. 1111 11 1 [-51]
    

  62. 3333 33 3 [-53]
    

  63. 4444 44 4 [-54]
    

  64. 2222 22 2 [-52]
    


  65. 

  66. //依据信号强度关键字，对wifi信息整体数据同步进行了排序
    

  67. sort:
    

  68. 5555 55 5 [-55]
    

  69. 4444 44 4 [-54]
    

  70. 3333 33 3 [-53]
    

  71. 2222 22 2 [-52]
    

  72. 1111 11 1 [-51]


回复

收藏 举报

 楼主| 电竞孔乙己 发表于 2022-5-5 16:26 | 显示全部楼层
5、总结

没有最好的排序算法，选择哪种方式需要结合待排序数据量的大小和类型，以前原始数据是否大概有序，选择合适的算法满足需求即可。


回复

收藏 举报

tpgf 发表于 2022-6-2 20:16 | 显示全部楼层
非常经典的算法
回复

收藏 举报

drer 发表于 2022-6-2 20:25 | 显示全部楼层
就看写的巧妙不巧妙了
回复

收藏 举报

qcliu 发表于 2022-6-2 20:35 | 显示全部楼层
都是非常常用的排序算法
回复

收藏 举报

coshi 发表于 2022-6-2 20:43 | 显示全部楼层
标准库函数用的是什么算法啊
回复

收藏 举报

kxsi 发表于 2022-6-2 20:51 | 显示全部楼层
哪一种是最简单的呢
回复

收藏 举报

wiba 发表于 2022-6-2 21:00 | 显示全部楼层
让我想起了数学建模
回复

收藏 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

电竞孔乙己

9

主题

91

帖子

0

粉丝
快速回复 在线客服 返回列表 返回顶部