下载掌阅APP，畅读海量书库
立即打开
排序算法是要整理文件、数据库、表中的记录，使其按照一定的顺序（常用的是递增或递减两种）排列起来；查找算法是在一系列数据中根据输入条件找出要获得的数据。这两类算法在众多的嵌入式软件程序中得到较多的应用。
1.3.4.1 算法的概念
算法是指在确定输入后，要通过一系列计算步骤或方法得到输出结果的过程，其中每个步骤或方法要在有限时间内完成。算法不是一个简单函数，它还有时间复杂度和空间复杂度的计算。所以算法必须能正确地解决一类问题，而不是一个问题，具有通用性。设计一个好的算法要注意以下方面。
（1）即使输入不同，算法也不应无限计算，若没有终止条件，就会陷入僵死状态。
（2）在终止时，算法不能输出错误的或不一致的结果。
（3）一定要评估复杂度，否则可能会影响其他任务的调度。
嵌入式程序中对算法的时间复杂度要求比较高，因为有较高的实时性要求，尤其是内核里的算法实现。如移动电话代码中，要查找某人移动电话中存储的号码，就需要选择一个好的算法，以快速响应。
1.3.4.2 排序算法
排序算法有很多种，如插入排序、选择排序、冒泡排序、快速排序、堆排序和归并排序等。本节给出目前常用的5种排序算法的代码，可直接移植运行，供读者参考。
1.常用排序算法
（1）插入排序算法
算法描述：将一个待排序的数据元素，插入已经有序（通常是从小到大或从大到小的顺序）的数列中的适当位置，要求插入后数列依然按照原先的顺序，循环直到待排序数据元素全部处理完。
假设按从小到大的顺序排序，这里用数组存储待排序元素，用一个临时变量temp 存储无序区的第一个元素；temp和有序区元素逐一比较，找到比temp小的元素p,p右边的有序元素逐一后移一位；然后在p后插入temp。
void InsertSort (int a[], int n)
{
/*将输入数组a[1..n]按递增顺序进行插入排序，a[0]是监视哨*/
int i,j;
int temp;
/*依次插入a[2],...,a[n]*/
for (i =0; i <n;i++)
{
temp = a[i];
j = i - 1;
while (temp < a[j])//逐个比较
{
a[j+1] = a[j];
j = j- 1;
}
a[j + 1] = temp;
}
return;
}
（2）选择排序算法
算法思想：根据预定目标，在一组数据中每次选出最小（或最大）的一个元素，放在已排好序的数列最后（或最前），再反复此过程，直到全部数据处理结束。
voidSelectSort (int a[], int n)
{
int i,j, k;
int temp;
/*做n-1趟选择排序*/
for (i = 0;i < n-1;i++)
{
k = i;
/*在当前a[i..n]中选最小的元素a[k]*/
for (j = i+1;j < n;j++)
{
if (a[j] < a[k])
k=j;
}
if (k != i)
{
temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
return;
}
（3）冒泡排序算法
算法思想：按预定目标每次比较一组数据中的两个元素，若发现它们的大小顺序相反，则直接交换，直到所有数据有序为止。
voidBubbleSort (int a[], int n)
{
int i,j;
int temp, flag;
/*从下向上扫描的起泡排序*/
for (i = 1;i <= n-1;i++)
{
/*置未排序的标志为真*/
flag = true;
for (j = n-1;j >= 0;j--)
{
if (a[j+1] < a[j])
{
/*交换元素*/
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
flag = false;
}
}
if (flag)
return;
}
return;
}
这种算法可形象理解为：一组数据中的元素对应一个重量的气泡，所有气泡有轻重之分。若要求轻气泡在重气泡上面，从下往上扫描这个数组。当轻气泡元素在重气泡下时就使其上浮，重气泡下沉，如此反复进行，直至所有元素对应的气泡重量完全有序为止。
（4）快速排序算法
算法思想：在当前无序数组a[1..n]中先任取一个数据元素作为基准数X=a[i]，用基准数将当前无序数组划分为左右两个较小的无序数组：a[1..i−1]和a[i+1..n]，基准数位于最终排序的位置上，左边和右边两组数满足a[1..i−1]≤X≤ a[i+1..n] (1≤i≤n)，然后再对左边、右边的数组元素重复上述的划分过程，直至所有元素均有序为止。
int Parttion (int a[], int low, int high )
{
int i,j;
int temp = a[low];
i = low;
j = high;
/*从右向左扫描，查找第一个小于temp的元素*/
while (i < j)
{
while ((i < j)&& (temp < a[j]))
j− −;
if (i <j)
{
a[i] = a[j];
i++;
}
while ((i < j)&& (temp >= a[i]))
i++;
if (i <j)
{
a[j] = a[i];
j− −;
}
}
a[i] = temp;
return i;
}
void QuickSort (int a[], int low, int high)
{
int pos = 0;
if (low < high)
{
pos = Parttion (a,low,high);
QuickSort (a,low, pos −1);
QuickSort (a, pos +1,high);
}
return;
}
（5）堆排序算法
算法思想：将key[1..n]视为完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点的内在关系来确定最小元素。即先建立树形结构的堆，将当前无序数组调整为一个大根堆/小根堆，再选择关键值最大或最小的堆顶元素与堆的最后一个元素进行交换。
void HeapAdjust (int sortdata[],int index, int length)
{
int childIndex, tmpData;
while (2* index +1 <length)
{
childIndex = 2* index +1 ;
if (2* index +2 <length)
{
/*比较左子树和右子树，记录最大值的index*/
if (sortdata[2* index +1]< sortdata[2* index +2])
childIndex = 2* index +2;
}
If (sortdata[index] <sortdata[childIndex])
{
tmpData = sortdata[index];
sortdata[index] = sortdata[childIndex];
sortdata[childIndex] =tmpData;
/*重新调整堆*/
index = childIndex;
}
else
break;/*比较左右孩子均大则堆未被破坏，不再需要调整*/
}
return;
}
void HeapSortData (int sortdata[], int length)
{
int i, tmpData;
/*建成大根堆*/
for (i = length/2−1; i>=0; i− −)
{
HeapAdjust (sortdata, i, length);
}
for (i = length−1; i>0; i− −)
{
tmpData = sortdata[0];
sortdata[0] = sortdata[i];
sortdata[i] =tmpData;
/*重新调整为大根堆*/
HeapAdjust (sortdata, 0, i);
}
return;
}
2.排序算法的比较和选择
选取排序算法必须要考虑复杂度，还有待排序的元素个数、元素信息大小、所选择的关键字和算法的应用场景等。例如，元素个数较少和较多时采用的排序算法不应相同。当元素的信息量较大时，可用链表作为存储结构。链表节点用指针做链接，可避免耗费大量移动时间。目前很多移动电话存储号码的排序使用快速排序算法，因为它的时间复杂度不大，在内部排序中使用较广。读者可先根据需求模拟具体的应用写出算法，再计算出运行时间和响应时间，优选后确定具体的算法类型。
1.3.4.3 查找算法
查找算法有很多种，主要有二分查找、顺序查找、哈希查找和二叉树查找等，目的是从一组数据中找到符合条件的数据。本节列出常用的4种算法的代码，可直接在嵌入式Linux软件环境下运行，供读者参考。
1.二分查找算法
二分查找算法有个前提要求是：待查找的数组采用顺序存储结构，且已是有序排列。因为该算法的思想是：先将所有 num 个元素（假设数组是升序排列）分成两组，每组元素数量大致相同，将输入的待查找数与第num/2个数比较，若两者相等则查找成功，算法结束；若小于则在前一组中继续查找；若大于则在后一组中继续查找，以此类推，这种查找算法的效率较高。若数据是无序性的，则无法确定待查找范围。
Int BinarySearch (int a[], int size, int key)
{
int low = 0, high = size – 1, mid;
while (low <= high)
{
/*获取中间的位置*/
mid = (low + high) / 2;
if (a[mid] = = key)
return mid;
if (a[mid] > key)
high=mid–1; /*向低的位置查找*/
else
low=mid+1; /*向高的位置查找*/
}
return −1;
}
2.顺序查找算法
顺序查找算法流程最为简单，具体思想是：用待查找数据和各个元素逐个比较，若找到与其相等的元素，则表示查找成功，算法结束；否则一直查找到数组最后一个元素，若还未找到与其相等的元素，则查找失败。
int SeqSearch (int a[],int key, int n)
{
int i =0;
a[n−1]=key;
while (a[i]!=key)
i++;
if (i < n−1)
return i;
else
return −1;
}
3.哈希查找算法
算法思想：先构建哈希表，根据待查找数据的特征来设计哈希函数，利用该函数计算出各元素在哈希表中的存储位置。查找时对待查键值计算出哈希地址，并将此键值映射到表中一个对应位置来确定查找是否成功。好的哈希函数可大大加快查找的速度，减少冲突。
#define m 13
#define n 10
#define p 11
#define MV 0
int hash (int k)
{
return (k%p);
}
int linerdetect (int *hl,int k)
{
int x=hash (k), i =1;
while (hl[x] != MV)
{
x = (x+i)%m;
i++;
}
return x;
}
void createhash (int *hl,int *x)
{
int i;
for (i =0;i <n;i++)
{
if (hl[hash (x[i])] = = MV)
hl[hash (x[i])] = x[i];
else
hl[linerdetect (hl,x[i])] = x[i];
}
}
int hashsearch (int *hl, int k)
{
int d,temp;
/*计算k的哈希地址*/
d =hash (k);
temp=d;
while (hl[d]!=MV)
{
if (hl[d]= =k)
return d;
else
d = (d+1)%n;
if (d= =temp)
return −1;
}
return −1;
}
/*检测哈希算法的运行效果*/
main ()
{
int hl[m],x[9]={57,7,69,11,16,82,22,8,3};
int i, key;
for (i =0;i <m;i++)
hl[i]=MV;
createhash(hl,x); /*创建哈希表*/
for (i =0;i <9;i++)
{
key = x[i];
printf (＂search : %d\n＂, hashsearch (hl,key));
}
return;
}
4.二叉树查找算法
二叉树查找算法采用数据结构中二叉树的思想：先建立一个二叉树，将所有元素分成两组，每组元素数量大致相同，通常右边的数比左边大，即根节点的右子树>根>左子树。查找时遍历二叉树，先将待查找数与根比较，若两者相等则直接返回；若大于则在右子树中查找；若小于则在左子树中查找，逐层深入，一直到确定最终位置。
typedef struct node
{
int data;
struct node * lchild;
struct node * rchild;
} node,*Tree;
/*树的根*/
Tree root = NULL;
void insert (Tree s)
{
Tree p,f;
if (root= =NULL)
root=s;
else
{
p = root;
while (p)
{
if (s->data<p->data)
{
f =p;
p =p->lchild;
}
else
{
f =p;
p =p->rchild;
}
}
if (s->data<f->data)
f->lchild=s;
else
f->rchild=s;
}
}
void createTree ()
{
Trees;
int x;
printf (＂输入0 end \n＂);
scanf (＂%d＂,&x);
while (x!= 0)
{
s = (Tree)malloc (sizeof (node));
s->data=x;
s->lchild=s->rchild=NULL;
insert (s);
scanf (＂%d＂,&x);
}
}
Tree findnode (int key)
{
Tree p= root;
while (p)
{
if (p->data= =key)
return p;
else if (p->data>key)
p=p->lchild;
else
p=p->rchild;
}
return NULL;
}
main() /*检验算法*/
{
Tree p;
int key, m;
while (1)
{
printf(＂1——建树；2——查找； 0——退出\n＂);
scanf (＂%d＂,&m);
switch (m)
{
case 1:
createTree ();
break;
case 2:
printf (＂输入要查的数字：＂);
scanf (＂%d＂,&key);
p=findnode (key);
if (p!=NULL)
printf (＂存在该数：%d\n＂, p->data);
break;
}
if (m= =0)
break;
}
}