排序算法(部编)课件

排序算法专题主要内容:一、选择排序二、插入排序三、冒泡排序四、合并排序五、快速排序七、计数排序六、桶排序其它的排序：堆排序，留在后面介绍排序就是把一组无序的关键字，通过算法变成一组有序的关键字。一、选择排序算法思想：对于一组关键字{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对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成.即:在要排序的一组数中,选出最小的一个数与第一个位置的数交换,然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。举例：对下面一组关键字，要求按照从大到小排序

a[1]a[2]a[3]a[4]a[5]a[6]a[7]13287499123748从A[1]到a[7]找最大的数9812347从A[2]到a[7]找最大的数9

871234从A[3]到a[7]找最大的数9

8

74123从A[4]到a[7]找最大的数9

8

7

4312从A[5]到a[7]找最大的数9

8

7

4

321从A[6]到a[7]找最大的数9

8

7

4

3

21排序结束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];}}二、插入排序算法思想：设有一组关键字{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第五趟:[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小的数的位置，退出循环returnk;//此时的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]<r[j+1],则把记录r[j]与r[j+1]交换位置,否则不进行交换.最后是r[n-1]与r[n]比较，关键字较小的记录就换到r[n]的位置上,到此第一趟冒泡结束。最小关键字的记录就象最轻的气泡冒到顶部一样换到了文件的最后.(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]13287493287491387492

1第一趟第二趟第三趟第四趟第五趟第六趟排序结束87493

2

18794

3

2

1897

4

3

2

198

7

4

3

2

19

8

7

4

3

2

1for(inti=1;i<n;i++)for(intj=1;j<=n-i;j++)if(a[j]<a[j+1]){inttmp=a[j+1];a[j+1]=a[j];a[j]=tmp;}核心代码：优化：如果待排序是下面这样的数据。很显然除了第一趟排序在最后一次比较发生了交换外，以后每一趟都不会发生交换。排序在第一趟冒泡后就已经有序了，可以结束了。54312for(inti=1;i<n;i++){boolflag=true;//引入了一个标记变量flag,循环中交换过就改变值for(intj=1;j<=n-i;j++)if(a[j]>a[j+1]){inttmp=a[j+1];a[j+1]=a[j];a[j]=tmp;flag=false;}//if(flag)break;//flag的值没改变过，说明没发生过交换。}四、合并排序算法思想：归并是指将若干个已排序的子文件合并成一个有的文件。归并排序的实现有两种方法：自底向上和自顶向下。采用分治法进行的自顶向下的算法形式更为简洁。具体实现：设归并排序的当前区间是r[low…high]，分治法的三个步骤：（1）分解：将当前区间一分为二，即求分裂点。mid=(low+high)/2（2）求解：递归地对两个子区间r[low…mid]和r[mid+1…high]进行归并排序。（3）合并：将已排好的两个区间r[low…mid]和r[mid+1…high]归并为一个有序的区间r[low…high]递归的终结条件是：low=high,即子区间的长度为1。voidmerge(intl,intm,intr){intb[101];inth,t,k;k=0;h=l;t=m+1;while((h<=m)&&(t<=r)){k++;if(a[h]<a[t]){b[k]=a[h];h++;}else{b[k]=a[t];t++;}}while(h<=m){k++;b[k]=a[h];h++;}while(t<=r){k++;b[k]=a[t];t++;}for(into=1;o<=k;o++)a[l+o-1]=b[o];}voidmergesort(intx,inty){intmid;if(x>=y)return;mid=(x+y)/2;mergesort(x,mid);mergesort(mid+1,y);merge(x,mid,y);}#include<iostream>usingnamespacestd;inta[101];//定义全局数组voidmerge(intl,intm,intr);//声明合并函数voidmergesort(intx,inty);//声明归并排序函数intmain(){intn;cin>>n;for(inti=1;i<=n;i++)cin>>a[i];mergesort(1,n);for(inti=1;i<=n;i++)cout<<a[i]<<'';cout<<endl;system("pause");return0;}五、快速排序在待排序的n个记录中任取一个记录(通常取第一个记录)，把该记录放入最终位置后，整个数据区间被此记录分割成两个子区间。所有关键字比该记录关键字小的放置在前子区间中,所有比他大的放置在后子区间中，并把该记录排在这个两个子区间的中间，这个过程称为一趟快速排序。之后对所有的两个子区间分别重复上述过程,直至每个子区间内只有一个记录为止。一趟快排的做法：设两个指示器i和j，他们的初值分别为指向无序区中的第一个和最后一个记录。假设无序区中记录为R[s…t]，则i的初值为s,j的初值为t，首先将R[mid]移至临时变量tmp中作为基准，令j自t起向左扫描直至R[j]<tmp时，将R[j]移至i所指的位置上，然后令i自i+1起向右扫描直至R[i]>tmp时，将R[i]移至j所指的位置上，依次重复直至i=j，此时所有R[k](k=s,s+1,…,j-1)的关键字都小于tmp而所有R[k](k=j+1,j+2,…,t)的关键字必大于tmp，则可将tmp中的记录移至i所指位置R[i]，它将无序中记录分割成R[s…j-1]和R[j+1…t]，以便分别进行排序。voidqsort(intx,inty){inttmp;inth=x,r=y;tmp=a[((h+r)/2)];while(h<r){while(a[h]<tmp)h++;while(a[r]>tmp)r--;if(h<=r){inttmp2=a[h];a[h]=a[r];a[r]=tmp2;h++;r--;}}if(x<r)qsort(x,r);if(y>h)qsort(h,y);return;}核心代码：六、桶排序基本思想：若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。注：桶排序不是基于关键字值比较的排序。例：对1、3、5、7、2、0、60、100、40、60排序思路：用上述待排序的数，作为数组下标。对于上面的数，定义一个A[101],数组开始每个元素的值为0。在读入数据的过程中，如果读入1令a[1]加1，读入3，令a[3]加1…，依此处理。得到一个数组A。然后，i从0到100进行如下处理：for(inti=0;i<=100;i++)while(a[i]>0){cout<<i<<‘‘;a[i]--;}核心代码：#include<iostream>usingnamespacestd;intmain(){inta[1001],i,n,tmp;memset(a,0,sizeof(a));//初始化为0cin>>n;for(i=1;i<=n;i++)//边读人，边把数放入桶中{cin>>tmp;a[tmp]++;}for(i=0;i<=1000;i++)//对于有数的桶进入输出while(a[i]>0)//可能有多个相同的关键字{cout<<i<<'';a[i]--;}cout<<endl;system("pause");return