第9章排序及查找算法及其实现本章主要内容在工程领域的计算机程序设计中，使用最广泛的，也是研究最充分的课题就是排序和查找算法了。有关排序和查找的算法遍布在千千万万的程序中，无论是数据库程序，还是各种编译程序、各种游戏，无一不用到排序和查找算法的所谓排序，就是将一个数据元素（或记录）的任意序列，按照指定的关键字，重新排成一个有序的序列假设含n个记录的序列为：其相应的关键字序列为排序的目的是为了确定一个新的序列对应的关键字满足如下的非递减(或非递增)关系交换法9.1.4排序效率9.2冒泡排序法的设计及其实现冒泡排序（BubbleSort）算法是最简单、最常见的也是效率最差的算法，适用于小数据量的排序。【例】有一组序列，顺序为5、4、3、2、1，用冒泡算法，对此序列按从小到大顺序排列#include<stdio.h>#include<stdlib.h>voidPrintArray(int*a,intn)//输出排序每一步结果的函数{inti;for(i=0;i<n;i++)//输出元素printf("%4d",a[i]);printf("\n");}voidBubbleSort(inta[],intn)//排序函数{inti,j,tmp;//tmp存储交换数据intflag;//标志变量，如果为0，//说明不再交换顺序，排序结束intcount=0;//计录交换次数printf("initialsorting:");PrintArray(a,n);//输出排序前的序列for(i=0;i<n-1;i++)//开始排序{flag=0;//标志初值为0for(j=0;j<n-i-1;j++){if(a[j]>a[j+1]){tmp=a[j];a[j]=a[j+1];a[j+1]=tmp;flag=1;//若发生交换，flag变为1}}count++;//记录已经发生的排序次数printf("after%dsorting:",count);PrintArray(a,n);//第count次的排序结果if(flag==0)//每排序一次，flag都清0//若交换不再发生，则排序完成return;}}voidmain()//主函数{int*a,n=5,i;a=(int*)malloc(n*sizeof(int));//为5个待排序整型数开辟存储空间for(i=0;i<n;i++)scanf("%d",&a[i]);//输入待排序数据BubbleSort(a,n);//调用排序函数free(a);//排序结束，释放存储空间}9.3选择排序法的设计及其实现选择排序法的过程很简单。首次扫描的时候选择出最小的一个元素，将它和第一个位置(也称为当前的基准元素位置)的元素交换。然后从剩下的n-1个元素中选择次小的元素，再和第二个位置(变成当前新的基准元素位置了)的元素交换。不断重复这一过程，直到最后一次从最后两个元素里面选择比较小的一个，然后交换。【例】选择排序法voidSelectSort(inta[],intn)//选择排序法的函数实现{inti,j,tmp;//tmp为中间变量intmin;//保存序列中的最小值intcount=0;//记录交换次数printf("initialsorting:");PrintArray(a,n);//输出当前结果for(i=0;i<n-1;i++)//开始排序{min=i;//基准元素的下标//其他元素与该下标下的元素比较for(j=i;j<n;j++){if(a[j]<a[min])//若小于基准元素，则交换min=j;//把要交换的位置告诉min}if(min!=i)//若min的值非原来的i，则要交换{tmp=a[i];//与基准元素进行位置交换a[i]=a[min];a[min]=tmp;}count++;printf("after%dsorting:",count);PrintArray(a,n);}}9.4插入排序法的设计及其实现插入排序法的思想是：当插入第i个元素的时候，前面i-1个元素已经排好了，这时只需要用第i个的关键码从最后开始与其他的进行比较，找到合适的位置，将后面的对象依次后移，然后将新的对象插入。【例】用插入排序法实现排序voidInsertSort(inta[],intn){inti,j,tmp;for(i=1;i<n;i++){tmp=a[i];for(j=i-1;(j>=0)&&(tmp<a[j]);j--)a[j+1]=a[j];//其余元素后移