排序算法.ppt
排序算法专题排序算法专题 甘肃省白银市平川区第三中学甘肃省白银市平川区第三中学 张民辉张民辉主要内容主要内容:一、选择排序一、选择排序二、插入排序二、插入排序三、冒泡排序三、冒泡排序四、合并排序四、合并排序五、快速排序五、快速排序七、计数排序七、计数排序六、桶排序六、桶排序其它的排序：其它的排序：堆排序，留在后面介绍堆排序，留在后面介绍 排序就是把一组无序的关键字，通过算法变成一组有序的排序就是把一组无序的关键字，通过算法变成一组有序的关键字。关键字。一、选择排序一、选择排序算法思想：对于一组关键字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对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成. 即: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换,然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。举例：对下面一组关键字，要求按照从大到小排序 a1 a2 a3 a4 a5 a6 a7 1 3 2 8 7 4 99 1 2 3 7 4 8从A1到a7找最大的数9 8 1 2 3 4 7从A2到a7找最大的数9 8 7 1 2 3 4从A3到a7找最大的数9 8 7 4 1 2 3从A4到a7找最大的数9 8 7 4 3 1 2从A5到a7找最大的数9 8 7 4 3 2 1从A6到a7找最大的数9 8 7 4 3 2 1排序结束 for(i=1;in;i+) for(j=i+1;jai) a0=ai; ai=aj; aj=a0; 核心代码核心代码该算法缺点就是元素交换的次数太多。改进算法： for(i=1;i=n;i+) k=i; for(j=i+1;j=n;j+) if(akaj) k=j; if(k!=i) a0=ai; ai=ak; ak=a0; 二、插入排序二、插入排序算法思想：设有一组关键字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在已经在已经有序的序列中的位置。有序的序列中的位置。int find(int x,int y)/该函数就是确定第y个元素x，在有序序列中的位置。 int k=y;/函数值通过K来返回，K初始化为y，设插入在y位置。 for(int i=1;i=x) k=i;break;/记下第一个比X小的数的位置，退出循环 return k;/此时的k即为X要插入的位置。 程序核心代码：程序核心代码： for(int i=1;im; k=find(m,i); for (int j=i;j=k;j-) aj+1=aj; ak=m; 程序采用了边读入边插入的方法。兰色部分为后面元素后移。三、冒泡排序三、冒泡排序算法思想：(1)让j取1至n-1,将rj与rj+1比较,如果rjrj+1,则把记录rj与rj+1交换位置,否则不进行交换. 最后是rn-1与rn比较，关键字较小的记录就换到rn的位置上,到此第一趟冒泡结束。最小关键字的记录就象最轻的气泡冒到顶部一样换到了文件的最后.(2) 让j取1至n-2,重复上述的比较对换操作,最终rn-1之中存放的是剩余n-1个记录(rn除外)中关键字最小的记录.(3) 让j取1至2,经过一系列对联对比交换之后,r3之中是剩余若干记录中关键字最小的记录.(4) 让j取1至1,将r1 与r2对比,把关键字较小的记录交换到r2之中。至此，经过n-1次冒泡，r1到rn中的数就成了有序的数。举例：对下面一组关键字，要求按照从大到小排序 a1 a2 a3 a4 a5 a6 a7 1 3 2 8 7 4 93 2 8 7 4 9 13 8 7 4 9 2 1第一趟第二趟第三趟第四趟第五趟第六趟排序结束8 7 4 9 3 2 18 7 9 4 3 2 18 9 7 4 3 2 19 8 7 4 3 2 19 8 7 4 3 2 1for(int i=1;in;i+) for(int j=1;j=n-i;j+) if(ajaj+1) int tmp=aj+1;aj+1=aj;aj=tmp; 核心代码：核心代码：优化：优化：如果待排序是下面这样的数据。很显然除了第一趟排序在最后如果待排序是下面这样的数据。很显然除了第一趟排序在最后一次比较发生了交换外，以后每一趟都不会发生交换。排序在第一趟冒一次比较发生了交换外，以后每一趟都不会发生交换。排序在第一趟冒泡后就已经有序了，可以结束了。泡后就已经有序了，可以结束了。5 4 3 1 2for(int i=1;in;i+) bool flag=true;/引入了一个标记变量引入了一个标记变量flag,循环中交换过就改变值循环中交换过就改变值 for(int j=1;jaj+1) int tmp=aj+1;aj+1=aj;aj=tmp;flag=false;/ if (flag) break;/flag的值没改变过，说明没发生过交换。的值没改变过，说明没发生过交换。四、合并排序四、合并排序算法思想：归并是指将若干个已排序的子文件合并成一个有的文件。归并排序的实现有两种方法：自底向上和自顶向下。采用分治法进行的自顶向下的算法形式更为简洁。具体实现：设归并排序的当前区间是rlowhigh，分治法的三个步骤：（1）分解：将当前区间一分为二，即求分裂点。 mid=(low+high)/2（2）求解：递归地对两个子区间rlowmid和rmid+1high进行归并排序。（3）合并：将已排好的两个区间rlowmid和rmid+1high归并为一个有序的区间rlowhigh递归的终结条件是：low=high,即子区间的长度为1。void merge(int l,int m,int r) int b101; int h,t,k; k=0; h=l;t=m+1; while(h=m)&(t=r) k+; if (ahat)bk=ah;h+; elsebk=at;t+; while(h=m)k+;bk=ah;h+; while(t=r)k+;bk=at;t+; for(int o=1;o=y) return; mid=(x+y)/2; mergesort(x,mid); mergesort(mid+1,y); merge(x,mid,y);#includeusing namespace std;int a101;/定义全局数组定义全局数组void merge(int l,int m,int r);/声明合并函数声明合并函数void mergesort(int x,int y);/声明归并排序函数声明归并排序函数int main()int n;cinn;for(int i=1;iai;mergesort(1,n);for(int i=1;i=n;i+) coutai ;coutendl;system(pause);return 0;五、快速排序五、快速排序在待排序的在待排序的n个记录中任取一个记录个记录中任取一个记录(通常取第一个记录通常取第一个记录)，把该记录放入，把该记录放入最终位置后，整个数据区间被此记录分割成两个子区间。最终位置后，整个数据区间被此记录分割成两个子区间。 所有关键字比所有关键字比该记录关键字小的放置在前子区间中该记录关键字小的放置在前子区间中,所有比他大的放置在后子区间中，所有比他大的放置在后子区间中，并把该记录排在这个两个子区间的中间，这个过程称为一趟快速排序。并把该记录排在这个两个子区间的中间，这个过程称为一趟快速排序。 之后对所有的两个子区间分别重复上述过程之后对所有的两个子区间分别重复上述过程,直至每个子区间内只有一个直至每个子区间内只有一个记录为止。记录为止。一趟快排的做法：一趟快排的做法： 设两个指示器设两个指示器i和和j，他们的初值分别为指向无序区中的，他们的初值分别为指向无序区中的第一个和最后一个记录。第一个和最后一个记录。 假设无序区中记录为假设无序区中记录为Rst，则，则i的初值为的初值为s,j的的初值为初值为t，首先将，首先将Rmid移至临时变量移至临时变量tmp中作为基准，令中作为基准，令j自自t起向左扫描起向左扫描直至直至Rjtmp时，将时，将Ri移至移至j所指的位置上，依次重复直至所指的位置上，依次重复直至i=j，此时所有，此时所有Rk(k=s,s+1,j-1)的关键字都小于的关键字都小于tmp而所有而所有Rk(k=j+1,j+2,t)的关键字的关键字必大于必大于tmp，则可将，则可将tmp中的记录移至中的记录移至i所指位置所指位置Ri，它将无序中记录分割，它将无序中记录分割成成Rsj-1和和Rj+1t，以便分别进行排序。，以便分别进行排序。void qsort(int x,int y) int tmp; int h=x,r=y; tmp=a(h+r)/2); while(hr) while(ahtmp) r-; if(h=r)int tmp2=ah; ah=ar; ar=tmp2; h+;r-; if(xh) qsort(h,y); return; 核心代码：核心代码：六、桶排序六、桶排序基本思想：若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。注：桶排序不是基于关键字值比较的排序。例：对1、3、5、7、2、0、60、100、40、60 排序思路：用上述待排序的数，作为数组下标。对于上面的数，定义一个A101,数组开始每个元素的值为0。在读入数据的过程中，如果读入1令a1加1，读入3，令a3加1，依此处理。得到一个数组A。然后，i从0到100进行如下处理： for(int i=0;i0) couti ;ai-;核心代码：核心代码：#includeusing namespace std;int main() int a1001,i,n,tmp; memset(a,0,sizeof(a);/初始化为初始化为0 cinn; for(i=1;itmp;atmp+; for(i=0;i0)/可能有多个相同的关键字可能有多个相同的关键字 couti ;ai-; coutendl; system(pause); return 0;桶排序的适用范围：关键字的值有固定的范围一般是大于0的。关键字值的范围不太大。七、计数排序七、计数排序基本思想：基本思想：是对于序列中的每一元素是对于序列中的每一元素x,确定序列中小于确定序列中小于x的元素的个数。的元素的个数。 例：例：n个整数序列且每个值在个整数序列且每个值在1,m,排序之。排序之。 #includeusing namespace std;int main() int a500+1,b500+1,c1000+1,i,n; memset(a,0,sizeof(a); memset(b,0,sizeof(b); cinn;/输入n for(i=1;iai; memset(c,0,sizeof(c); for(i=1;i=n;i+)/类似桶排序 cai+; for(i=2;i=n;i+)/统计比i小的数的个数 ci+=ci-1; for(i=1;i=n;i+)/把ai存放在b中，cai是ai在b中的绝对位置 bcai=ai; cai-;/减一 for(i=1;i=n;i+)/输出B数组 coutbi ; coutendl; system(pause); return 0;
