内容摘要：1、冒泡排序冒泡排序(bubble sort)是一种C语言入门级的简单排序算法，重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误进行交换。重复地检查对比直到没有相邻元素需要交换，也就是

 

1、嵌入冒泡排序

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

算法描述

1、式算算法比较相邻的排序元素。如果第一个比第二个大，嵌入就进行交换

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

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; } 

运行结果

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

算法描述

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

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

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

源码

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])        // 寻找最小的数             {                  min = j;                  // 将最小数的索引保存             }         }         if(min != i)    // 需要交互         {              temp = data[i];             data[i] = data[min];             data[min] = temp;         }     } } 

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

3、插入排序

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

算法描述

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

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

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)  //当前元素与的有序区逐个比较再插入         {              data[pre + 1] = data[pre];             pre--;         }         data[pre + 1] = current;     } } 

4、标准库函数qsort

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

相比于自己造轮子，C语言标准库函数也许更合适;qsort函数是高防服务器C语言自带的排序函数，包含在中。

函数原型

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

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

nitems - 数组中的元素数目

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

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

返回：值不返回任何值

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

范例

//qsort要结合compare使用 int compare(const void *value1, const void *value2) {      //升序或降序在此调整     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; } 

其效果和前面三种算法一样，而且可扩展针对结构体内某个元素值对整体排序，满足前面的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:\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; } 

运行结果

source: 5555 55 5 [-55] 1111 11 1 [-51] 3333 33 3 [-53] 4444 44 4 [-54] 2222 22 2 [-52] //依据信号强度关键字，对wifi信息整体数据同步进行了排序 sort: 5555 55 5 [-55] 4444 44 4 [-54] 3333 33 3 [-53] 2222 22 2 [-52] 1111 11 1 [-51] 

5、总结

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