排序算法讲解学习.ppt

《排序算法讲解学习.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序算法排序就是把一组无序的关键字，通过算法变成一组有序的关键字。一、选择排序算法思想：对于一组关键字{K1,K2,…,Kn},首先从K1,K2,…,Kn中选择最小值,假如它是Ki,则将Ki与K1对换,然后从K2,K3,…,Kn中选择最小值Ki,再将Ki与K2对换.如此进行选择和调换n-2趟,第(n-1)趟,从Kn-1、Kn中选择最小值Ki将Ki与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成.即:在要排序的一组数中,选出最小的一个数与第一个位置的数交换,然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。举例

2、：对下面一组关键字，要求按照从大到小排序a[1]a[2]a[3]a[4]a[5]a[6]a[7]13287499123748从A[1]到a[7]找最大的数9812347从A[2]到a[7]找最大的数9871234从A[3]到a[7]找最大的数9874123从A[4]到a[7]找最大的数9874312从A[5]到a[7]找最大的数9874321从A[6]到a[7]找最大的数9874321排序结束for(i=1;ia[i]){a[0]=a[i];a[i]=a[j];a[j]=a[0];}}核心代码该算法缺点就是元素交换

3、的次数太多。改进算法：for(i=1;i<=n;i++){k=i;for(j=i+1;j<=n;j++)if(a[k]

4、55] 44 11 33第三趟: [22 44 55] 11 33第四趟: [11 22 44 55] 33第五趟:[1122 33 44 55]解决问题关键是找插入的位置。需要写一个函数find(x,y),来确定第y个插入元素x在已经有序的序列中的位置。intfind(intx,inty)//该函数就是确定第y个元素x，在有序序列中的位置。{intk=y;//函数值通过K来返回，K初始化为y，设插入在y位置。for(inti=1;i<=y;i++)//从第1个元素开始和X比较找到第一个比X小的数if(a[i]>=x){k=i;break;}//记下第一个比X小的数的位置，退出循环r

5、eturnk;//此时的k即为X要插入的位置。}程序核心代码：for(inti=1;i<=n;i++){intk;cin>>m;k=find(m,i);for(intj=i;j>=k;j--)a[j+1]=a[j];a[k]=m;}程序采用了边读入边插入的方法。兰色部分为后面元素后移。三、冒泡排序算法思想：让j取1至n-1,将r[j]与r[j+1]比较,如果r[j]

6、后.(2)让j取1至n-2,重复上述的比较对换操作,最终r[n-1]之中存放的是剩余n-1个记录(r[n]除外)中关键字最小的记录.(3)让j取1至2,经过一系列对联对比交换之后,r[3]之中是剩余若干记录中关键字最小的记录.(4)让j取1至1,将r[1]与r[2]对比,把关键字较小的记录交换到r[2]之中。至此，经过n-1次冒泡，r[1]到r[n]中的数就成了有序的数。举例：对下面一组关键字，要求按照从大到小排序a[1]a[2]a[3]a[4]a[5]a[6]a[7]132874932874913874921第一趟第二趟第三趟第四趟第五趟第六趟排序结束874932187943218

7、97432198743219874321for(inti=1;i