四种排序算法

  嵌入式系统中尤其涉及数据采集的，需要对数据进行简单处理后再进行业务层功能，考虑到硬件的资源限制，对于数据排序，一般只是应用这四种简单的排序算法。

一、冒泡排序

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

1.1、算法描述

  1、比较相邻的元素。如果第一个比第二个大，就进行交换
  2、对每一对相邻元素作同样操作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
  3、针对所有的元素重复以上的步骤，除了最后一个
  4、重复步骤1~3，直到排序完成

1.2、源码

#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("rn");
}
//从小到大排序
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;
}

1.3、运行结果

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

二、选择排序

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

2.1、算法描述

  1、初始状态，数据都属于无序区，有序区为空
  2、从无序区中选出最小元素，将它与无序区的第1个元素交换
  3、再从无序区的下个元素重复第2步，直至无序区为空

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

三、插入排序

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

3.1、算法描述

  1、从第一个元素开始，该元素可认为已排序
  2、取出下一个元素，在已经排序的元素序列中从后向前扫描
  3、如果该元素（已排序）大于新元素，将该元素移到下一位置
  4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置后
  5、重复步骤2~4

3.2、源码

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

四、标准库函数qsort

  前面三种排序算法都只是针对单个元素进行排序，但实际应用中，基于某个数值对一个大结构体进行排序，比如wifi信息结构体数组，包括其mac、名称、加密信息、和信号强度，依据信息强度对wifi信息进行排序，每次数据交换意味着两次内存拷贝，这种场景下采用选择排序略优。
相比于自己造轮子，C语言标准库函数也许更合适；qsort函数是C语言自带的排序函数，包含在<stdlib.h>中。

4.1、函数原型

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

  base - 指针，数组的第一个元素进行排序
  nitems - 数组中的元素数目
  size - 数组中的每个元素的大小（以字节为单位）
  compar - 基于这个函数比较两个元素
  返回值：不返回任何值
  缺点：对于有多个重复值的数组来说，效率较低不稳定

4.2、范例

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

最后

以上就是和谐玉米为你收集整理的四种排序算法的全部内容，希望文章能够帮你解决四种排序算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。