《插入排序交换排序选择排序归并排序基数排序.ppt》由会员分享，可在线阅读，更多相关《插入排序交换排序选择排序归并排序基数排序.ppt（46页珍藏版）》请在三一办公上搜索。
1、插入排序交换排序选择排序归并排序基数排序,第九章 排序,排序问题,定义 给定一组纪录 R1,R2,Rn其关键码分别为k1,k2,kn,将这组纪录重新排成顺序为Rp1,Rp2,Rpn的一个序列，使其关键码具有不减顺序kp1 kp2 kpn.不同的纪录可以具有相同的关键码。稳定的排序：关键码相同的纪录在排序前和排序后的次序保持不变。约定：关键码用整数代替,排序的基本操作,比较 比较关键码的大小。移动 将纪录从一个位置移到另一个位置。,排序方法的分类,内部排序 不用外设 外部排序,插入，交换，选择，归并，计数等排序法,复杂度 O(n2)O(nlogn)等排序法,静态排序，动态排序,原始记录,#def
2、ine MaxDataSize 100templatestruct Data T element;int key;Data,template class Array/array.h 通用数组 抽象数组类型 T*alist;int size;public:Array(int s=50)；/构造函数 Array(const Array；,待排序原始记录数组的输入,templatevoid InputDataList(Array,一、插入排序,逐个将纪录插入到已排好次序的有序表中得到一个新的有序表。,1.直接插入排序,最大时间复杂度O(n2)=O(n2/2)+O(n2/2)n-1 比较 i=n(n-
3、1)/2 次 i=1 n-1 移动(i+2)=(n+4)(n-1)/2 i=1最小时间复杂度 O(n)不移动,49 38 65 97 76 13 27 4949 4938 49 6549 65 9738 49 65 76 9713 38 49 65 76 97 27 38 49 65 76 9713 27 38 49 49 65 76 97,元素个数n越小越好，源序列排序度越高越好,2.折半插入排序,用折半法比较查找到适当的位置再插入减少比较次数 不减少移动次数最坏时间复杂度 O(nlogn)+O(n2/2)=O(n2),3.2路插入排序,49 38 65 97 76 13 27 494949
4、 3849 65 3849 65 97 3849 65 76 97 3849 65 76 97 13 3849 65 76 97 13 27 3849 49 65 76 97 13 27 38,当第一个数据序列中间位置时减少移动次数不减少比较次数,复杂性O(n2),Final First,4.表插入排序 静态链表 不移动,5.链表插入排序 动态链表 不移动,6.希尔排序Shell Sort,缩小增量排序Diminishing Increment Sort基本思想：先将待排纪录分成若干子列分别用直接插入法排序，再对全体纪录用直接插入法排序。理论根据：直接排序序列越短越好，源序列的排序度越好效率越
5、高。,Shell Sort 取 dltak=5，3，2，1,49 38 65 97 76 13 27 49 55 4,一趟排序结果：13 27 49 55 4 49 38 65 97 76,二趟排序结果：13 4 49 38 27 49 55 65 97 76,三趟排序结果：4 13 27 38 49 49 55 65 76 97,/一趟Shell Sort 算法 直接插入,templatevoid ShellInsert(Array,Shell Sort 算法,templatevoid ShellSort(Array 取dltak=2t-k+1-1 dltak=9，5，3，2，1时间复杂度O
6、(n3/2),二.交换排序,起泡排序Bubble Sort 49 38 65 97 76 13 27 49一趟排序结果：38 49 65 76 13 27 49 97二趟排序结果：38 49 65 13 27 49 76 97三趟排序结果：38 49 13 27 49 65 76 97四趟排序结果：38 13 27 49 49 65 76 97五趟排序结果：13 27 38 49 49 65 76 97,最快 正序 比较n-1次 不交换最慢 逆序 n(n-1)/2次比较 同样多次交换,2.快速排序,基本思想：通过一趟排序将待排纪录分成上下两个子列，上子列大于下子列。再对两个子列继续排序。理论依
7、据：排序序列越短越好，源序列的排序度越好效率越高。,快速排序,49 38 65 97 76 13 27 49,pivot,low,high,将pivot和high比较下行找到小于pivot的纪录交换,一次交换后：27 38 65 97 76 13 49,将pivot和low比较上行找到大于pivot的纪录交换,二次交换后：27 38 97 76 13 65 49,high,low,三次交换后：27 38 13 97 76 65 49,四次交换后：27 38 13 49 76 97 65 49,low,high,Low和high相遇结束,快速排序 27 38 13 49 76 97 65 49第
8、一轮后,由pivot49分成两个子列，分别再进行快速排序 27 38 13 49 76 97 65 49一次 13 38 49 49 97 65 二次 13 38 49 49 65 97 三次 13 27 38 49 49 65 76 97,时间复杂性O(knlogn),一趟快速排序算法的实现,templateint Partition(Array,时间复杂度cn,快速排序算法的实现,templatevoid QickSort(Array,快速排序算法复杂性分析,假设T(n)为对n个纪录进行快速排序所需时间，对n个纪录进行一趟快速排序Patition(L,1,n)所需时间为cn,则 T(n)=
9、cn+T(k-1)+T(n-k)=cn+2T(n/2)/理想化每次都分成相等的两部分=2cn+2(cn/2+2T(n/4)=3cn+4T(n/4)=4cn+8T(n/8)=cnlog2n+nT(1)=O(nlog2n)最坏 O(n2)平均O(nlog2n),比较排序算法的下界,n个元素排成一个序列，共有n!种不同的排法。从一个序列出发排序，总共就会有n!种不同的变换次序。每一次比较交换可以得到两种不同的次序，可以将不同的比较排成判定二叉树。,比较排序算法的下界log(n!),log(n/2)n/2)log(n!)log(nn)(n/2)log(n/2)log(n!)nlogn(n/2)log(
10、n/2)=(n/2)(logn-1)=(n/2)logn-n/2=O(nlogn)log(n!)=O(nlogn),三.选择排序,1.简单选择排序基本思想 一趟选择排序 选出最小纪录排在首位L0 第i+1趟选择排序 从纪录Li+1到Ln选出 最小纪录记在Li。一趟比较n-i+1次共比较n(n-1)/2次 最少移动0次，最多移动3(n-1)次 时间复杂度O(n2),2.竞标赛排序,也叫树型排序,13,38,13,38,65,27,49,38,27,13,76,13,49,65,97,两两比较n/2次选出最小值,选次最小值,38,38,65,27,49,38,27,76,49,65,97,先将最小
11、值由顶向下去掉，最底层换上Maxint再比较log2n次。,76,27,27,重复这一过程n-1次得到全排序序列时间复杂性O(nlog2n)空间开销大 可以改进,3.堆排序Heap Sort(改进了的树型排序）,（极小）堆的定义：n个元素的完全二叉树，每个结点都小于其子结点。,13,49,27,97,65,76,38,用一维数组表示极小堆,13,49,27,97,65,76,38,Ai A2i,Ai A2i+1,堆排序,堆排序的过程 1.将一个无序序列建成堆，2.入出顶点元素后，调整并重建堆，3.重复2.直至全部元素都输出完毕。,先作第二步：输出并调整重建堆,13,49,27,97,65,76
12、,38,输出堆顶元素13，用堆末元素取代，将元素76下移与子结点中较小的一个交换，向下过滤，直至叶结点，重复第2步直至全部输出。,76,13,76,76,76,27,27,76,76,76,38,76,38,第一步 建堆,从最末一个非叶结点An/2开始向下过滤直至堆顶,49,38,65,97,76,27,13,49,49,97,13,65,13,49,49,27,向下过滤的实现（极大堆）,templatevoid FilterDown(Array,堆排序的实现(由极大堆实现）,templatevoid HeapSort(Array,四.归并排序 Merge Sort,将两个或两个以上有序表组合
13、成一个新的有序表 叫做归并排序 复杂性O(m+n)2路归并 将一个序列看成是n个由单个元素组成的子序列，每个子序列都是有序的长度为1。再将这些子序列两两合并，得到n/2个长度为2的有序子序列。继续两两合并，直到合并成一个长度为n的有序序列。,2路归并算法,38 65 97 76 13 27 49,38 49 65 97 13 76 27 49,38 49 65 97 13 27 49 76,13 27 38 49 49 65 76 97,时间复杂性O(nlogn),归并算法的实现,templatevoid Merge(Array*L,Array*S,int i,int m,int n)int
14、j,k;for(j=m+1,k=i;im,templatevoid Msort(Array*L,int i,int j)Array*ST；ST=new DataL.ArraySize()；if(i=j)Si=Li else m=(i+j)/2;Msort(L,ST,i,m);Msort(L,ST,m+1,j);Merge(ST,L,i,m,j);,2路归并算法的实现,templatevoid MergeSort(Array*L)Msort(L,L,1,L.ArraySize();,五、基数排序-多关键字排序,例。扑克牌排序 2 3 k A 2 3 K A 2 3 K A 2 3 k A 两种排
15、序法：1。先排花色 2。先排面值,例.多位数排序 278 109 063 930 589 184 505 269 008 083,第一遍：按个位数放入10个箱子（队列）,按0-9的顺序从10个箱子中取出数字,930 063 083 184 505 278 008 109 589 269,例.多位数排序 278 109 063 930 589 184 505 269 008 083,第二遍：再将所得数列按十位依次入箱,930 063 083 184 505 278 008 109 589 269,再按0-9的顺序从10个箱子中取出数字,505 008 109 930 063 269 278 083 184 589,例.多位数排序 278 109 063 930 589 184 505 269 008 083,第三遍：再将所得数列按百位依次入箱,930 063 083 184 505 278 008 109 589 269,505 008 109 930 063 269 278 083 184 589,再按0-9的顺序从10个箱子中取出数字,008 063 083 109 184 269 278 505 589 930,
