排序算法及MATLAB实现.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,排序,算法,排序,例：对,1,、,9,、,6,、,11,、,3,这,5,个数字进行从小到大排序？,结果：,1,、,3,、,6,、,9,、,11,思考：如何编程让计算机完成排序？,排序算法的种类：,1,、冒泡排序（,Bubble Sort,）,2,、选择排序（,Selection Sort,）,3,、插入排序（,Insertion Sort,）,4,、希尔排序（,Shell Sort,）,5,、归并排序（,Merge Sort,）,6,、快速排序（,Quick Sort,）,7,、堆排序（,Heap Sort,）,8,、计数排序（,Counting Sort,）,9,、桶排序（,Bucket Sort,）,10,、基数排序（,Radix Sort,）,1,、冒泡排序,原理：,重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。,1,、冒泡排序,例：对,1,、,9,、,6,、,11,、,3,这,5,个数字进行从小到大排序？,冒泡排序：,（,1,）,1,、,6,、,9,、,11,、,3,（,2,）,1,、,6,、,9,、,3,、,11,（,3,）,1,、,6,、,3,、,9,、,11,（,4,）,1,、,3,、,6,、,9,、,11,1,、冒泡排序,MATLAB,程序实现：,X=1,9,6,11,3;,a=size(X,2);,for,i=1:a,for,j=1:a-1,y=X(j);,z=X(j+1);,if,X(j)X(j+1),X(j)=z;,X(j+1)=y;,end,end,X,end,2,、选择排序,原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。,2,、选择排序,例：对,1,、,9,、,6,、,11,、,3,这,5,个数字进行从小到大排序？,选择排序：,（,1,）,1,、,9,、,6,、,11,、,3,（,2,）,1,、,3,、,6,、,11,、,9,（,3,）,1,、,3,、,6,、,11,、,9,（,4,）,1,、,3,、,6,、,9,、,11,2,、选择排序,MATLAB,程序实现：,X=1,9,6,11,3,12,18;,a=size(X,2);,for,i=1:a,x=X(i:a);,y=min(x);,b=find(X=y);,X(b)=X(i);,X(i)=y;,X,end,3,、插入排序,原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。,3,、插入排序,例：对,1,、,9,、6,、,11,、,3,这,5,个数字进行从小到大排序？,选择排序：,（,1,）,1,、,9,、,6,、,11,、,3,（,2,）,1,、,6,、,9,、,11,、,3,（,3,）,1,、,6,、,9,、,11,、,3,（,4,）,1,、,3,、,6,、,9,、,11,3,、插入排序,MATLAB,程序实现：,X=1,9,6,11,3,12,18;,a=size(X,2);,for,j=2:a,key=X(j);,i=j-1;,while,i0&X(i)key,X(i+1)=X(i);,i=i-1;,end,X(i+1)=key;,X,end,4,、希尔排序,插入排序当原始数据比较有序时，效率非常高。但当原始数据无序时，效率比较低。,希尔排序是对插入排序的改进,。,希尔排序目标：在进行排序之前让数据变得更为有序，提高排序效率。,4,、希尔排序,步骤：将待排序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。,4,、希尔排序,例：利用希尔方法对,592,、,401,、,874,、,141,、,348,、,72,、,911,、,887,、,820,、,283,进行排序。,5,、归并排序,基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列。,在内部排序中，通常采用的是,2-,路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列。5,、归并排序,如何进行两路归并？,将两个有序表的元素进行比较，小者复制到目标表中。,5,、归并排序,5,24,35,74,222,(,),19,23,30,(,),i,j,(,),k,5,19,23,24,30,35,74,222,两路归并动画演示,i,k,j,k,j,k,i,k,j,k,s,m,t,m+1,5,、归并排序,具体实现步骤,假设,初始序列含有,n,个记录，则可看成,n,个有序的子序列，每个子序列长度为1,。,然后两两归并，得到,n/2,个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为,n,的有序序列为止,。,5,、归并排序,初始时：,49 38 65 97 76 13 27,初始关键字：,49 38 65 97 76 13 27,一趟归并后：,38 49 65 97 13 76 27,二趟归并后：,38 49 65 97 13 27 76,三趟归并后：,13 27 38 49 65 76 97,6,、快速排序,思考：利用冒泡排序将,38,、,49,、,65,、,13,、,27,完成排序需要几步？,解：（,1,）,38 49 65 13 27,（,2,）,38 49 65 13,27,（,3,）,38 49,13 65 27,（,4,）,38 49 13,27 65,（,5,）,38 49 13 27 65,（,6,）,38,13 49,27,65,6,、快速排序,（,7,）,38 13,27 49 65,（,8,）,38 13 27 49,65,（,9,）,13 38 27,49,65,（,10,）,13,27 38,49,65,冒泡算法最少需要,10,步。,能否用更少的步数完成排序？,6,、快速排序,基本思想：,（,1,）从数列中挑出一个元素，称为,“基准”,（,2,）所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的,后面,（,3,）对上步分成的两端无序数组重复（,1,）和（,2,）步操作，直到完成排序。,6,、快速排序,例：利用快速排序,将,38,、,49,、,65,、,13,、,27,完成,排序？,（,1,）选取,38,为基准，将大于,38,的值放右边，小的放左边：,（,2,）在左边数组选取,13,为基准，重复上步,（,3,）,在右边,数组,选取,49,为,基准，重复上步,13,27,38,49,65,6,、快速排序,MATLAB,实现,X=1,9,6,11,3;,Sta=X(3);,%,基准,X1=X(XSta);,Sta1=X1(1);,X11=X1(X1Sta1);,Sta2=X2(1);,X21=X2(X2Sta2);,X=X11 Sta1 X12 Sta X21 Sta2 X22,7,、堆排序,堆的定义：,若,n,个元素的序列,a,1,a,2,a,n,满足,则分别称该序列,a,1,a,2a,n,为,小根堆,和,大根堆。,7,、堆排序,例,:,下面序列为堆，对应的完全二叉树分别为,:,77 35 62 55 14 35 48,14 48 35 62 55 98 35 77,小根堆,大根,堆,7,、堆排序,建堆,在实际应用中，大多数数据构建的二叉树并不是堆，比如：,解决方案：调整次序，构建大根堆或小根堆。,7,、堆排序,建堆,例：,7,、堆排序,建堆,例：将序列,28,25,16,36,18,32,构建成大根堆,7,、堆排序,堆排序原理,若,在输出堆顶的最小值（最大值）后，使得剩余,n-1,个元素的序列重又建成一个堆，则得到,n,个元素的次小值（次大值）,如此反复，便能得到一个有序序列，这个过程称之为,堆排序,。,问题：如何在输出堆顶元素后，调整剩余元素为一个新的堆？,7,、堆排序,问题：如何在输出堆顶元素后，调整剩余元素为一个新的堆？,解决方案：输出堆顶元素之后，以堆中最后一个元素替代,之，然后重新构建堆。,7,、堆排序,例题：用堆排序将序列,20,60,26,30,36,10,调整为递增序列。,（,1,）构建小根堆,7,、堆排序,（,2,）提取堆顶,10,，并用最后一个元素替换堆顶，重新构建小根堆。,7,、堆排序,（,3,）提取堆顶,20,，并用最后一个元素替换堆顶，重新构建小根堆。,7,、堆排序,（,4,）提取堆顶,26,，并用最后一个元素替换堆顶，重新构建小根堆。,7,、堆排序,（,5,）提取堆顶,30,，并用最后一个元素替换堆顶，重新构建小根堆。,（,6,）提取堆顶,36,，剩余一个数,60,，提取,60,。,8,、计数排序,排序原理：,利用哈希的方法，将每个数据出现的次数都统计下来。哈希表是顺序的，所以我们统计完后直接遍历哈希表，将数据再重写回原数据空间就可以完成排序。,8,、计数排序,对一组数据进行排序做出图解：,8,、计数排序,MATLAB,代码,X=1,9,6,6,3,11,3,12,18;,x=max(X);,Y=;,for,i=0:x,a=find(X=i);,if,isempty(a)=1,continue,else,b=size(a,2),y=i*ones(1,b);,Y=Y,y;,end,end,Y,