排序算法及MATLAB实现-课件

排序算法及排序算法及MATLABMATLAB实现实现排序排序例例:对对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、111、冒泡排序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 Xend2、选择排序原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中接着寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。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、112、选择排序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;Xend3、插入排序原理:通过构建有序序列,关于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。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、113、插入排序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;Xend4、希尔排序插入排序当原始数据比较有序时,效率特别高。但当原始数据无序时,效率比较低。希尔排序是对插入排序的改进希尔排序是对插入排序的改进。希尔排序目标:在进行排序之前让数据变得更为有序,提高排序效率。4、希尔排序步骤:将待排序列划分为若干组,在每一组内进行插入排序,以使整个序列基本有序,然后再对整个序列进行插入排序。4、希尔排序例:利用希尔方法对592、401、874、141、348、72、911、887、820、283进行排序。5、归并排序基本思想:将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中,通常采纳的是2-路归并排序。即:将两个位置相邻的有序子序列归并为一个有序序列。5、归并排序v如何进行两路归并？将两个有序表的元素进行比较,小者复制到目标表中。5、归并排序52435 74222()192330()ij()k51923243035 74222两路归并动画演示ikjkjkikjksmtm+15、归并排序具体实现步骤 假设初始序列含有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 976、快速排序考虑:利用冒泡排序将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 656、快速排序(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为基准,重复上步13273849656、快速排序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 X227、堆排序堆堆的的定定义义:若若n个个元元素素的的序序列列a1 a2 an 满满足足则则分分别别称称该该序序列列a1 a2 an为为小小小小根根根根堆堆堆堆 与与大大大大根根根根堆堆堆堆。7、堆排序例:下面序列为堆,对应的完全二叉树分别为:77 35 62 55 14 35 4814 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;endendY感谢您的聆听！感谢您的聆听！