排序算法PPT学习教案.pptx

会计学
1
排序算法
主要内容:
一、选择排序
二、插入排序
三、冒泡排序
四、合并排序
五、快速排序
七、计数排序
六、桶排序
其它的排序：
堆排序，留在后面介绍
第1页/共19页
排序就是把一组无序的关键字，通过算法变成一组有序的
关键字。
一、选择排序
算法思想：对于一组关键字{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页/共19页
举例：对下面一组关键字，要求按照从大到小排序

a[1] a[2] a[3] a[4] a[5] a[6] a[7]
1 3 2 8 7 4 9
9 1 2 3 7 4 8
从A[1]到a[7]找最大的数
9 8 1 2 3 4 7
从A[2]到a[7]找最大的数
9 8 7 1 2 3 4
从A[3]到a[7]找最大的数
9 8 7 4 1 2 3
从A[4]到a[7]找最大的数
9 8 7 4 3 1 2
从A[5]到a[7]找最大的数
9 8 7 4 3 2 1
从A[6]到a[7]找最大的数
9 8 7 4 3 2 1
排序结束
第3页/共19页
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
if(a[j]>a[i])
{a[0]=a[i];
a[i]=a[j];
a[j]=a[0];}
}
核心代码
该算法缺点就是元素交换
的次数太多。
改进算法：
for(i=1;i<=n;i++)
{
k=i;
for(j=i+1;j<=n;j++)
if(a[k]<a[j]) k=j;
if(k!=i)
{a[0]=a[i];
a[i]=a[k];
a[k]=a[0];}
}
第4页/共19页
二、插入排序
算法思想：设有一组关键字{K1,K2,…,Kn},排序开始就认为
K1是一个有序序列,让K2 插入上述表长为1的有序序列,使之
成为一个表长为2的有序序列,然后让K3插入上述表长为2的
有序序列,使之成为一个表长为3的有序序列,依次类推,最后
让Kn插入上述表长为 n-1的有序序列,得一个表长为n的有序
序列。
第一趟:  [55]  22  44  11  33
第二趟:  [22 55] 44 11 33
第三趟:  [22 44 55] 11 33
第四趟:  [11 22 44 55] 33
第五趟: [11 22 33 44 55]
解决问题关键是找插入的位置。需要写一个函数find(x,y),来确定第y个插入元素x在已经有序的序列中的位置。
第5页/共19页
int find(int x,int y)//该函数就是确定第y个元素x，在有序序列中的位置。
{int k=y;//函数值通过K来返回，K初始化为y，设插入在y位置。
for(int i=1;i<=y;i++)//从第1个元素开始和X比较找到第一个比X小的数
if(a[i]>=x) {k=i;break;}//记下第一个比X小的数的位置，退出循环
return k;//此时的k即为X要插入的位置。
}
程序核心代码：
for(int i=1;i<=n;i++)
{
int k;
cin>>m;
k=find(m,i);
for (int j=i;j>=k;j--)
a[j+1]=a[j