《排序算法及MATLAB实现PPT优秀课件》由会员分享，可在线阅读，更多相关《排序算法及MATLAB实现PPT优秀课件（41页珍藏版）》请在装配图网上搜索。
1、排序排序算法算法12021/5/26排序排序例：对例：对1、9、6、11、3这这5个数字个数字进行从小到大排序？进行从小到大排序？结果：结果：1、3、6、9、11思考：如何编程让计算机完成排思考：如何编程让计算机完成排序？序？22021/5/26排序算法的种类： 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、桶排序（
2、Bucket Sort） 10、基数排序（Radix Sort）32021/5/261、冒泡排序 原理：原理：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。42021/5/261、冒泡排序例：对例：对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、1152021/5/261、冒泡排序 MATLAB程序实现：X=1,9,6,11,3;a=size(X,2)
3、;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 Xend62021/5/262、选择排序 原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。72021/5/262、选择排序例：对例：对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、
4、3、6、9、1182021/5/262、选择排序 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; Xend92021/5/263、插入排序 原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。102021/5/263、插入排序 例：对例：对1、9、6、11、3这这5个数字进行从小到大个数字进行从小到大排序？排序？选择排序：（1）1、9、6、11、3（2）1、6、9、11、3（3）1、6、9、11、3（
5、4）1、3、6、9、11112021/5/263、插入排序 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 end122021/5/264、希尔排序 插入排序当原始数据比较有序时，效率非常高。但当原始数据无序时，效率比较低。 希尔排序是对插入排序的改进希尔排序是对插入排序的改进。 希尔排序目标：在进行排序之前让数据变得更为有序，提高排序效率。132021/5/264、希尔排序 步骤：将待
6、排序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。142021/5/264、希尔排序 例：利用希尔方法对592、401、874、141、348、72、911、887、820、283进行排序。152021/5/265、归并排序 基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列。 在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列。162021/5/265、归并排序v如何进行两路归并？ 将两个有序表的元素进行比较，小者复制到目标表中。172021/5/265、归并排序52435 74222()1923
7、30()ij()k51923243035 74222两路归并动画演示ikjkjkikjksmtm+1182021/5/265、归并排序 具体实现步骤 假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止。192021/5/265、归并排序初始时：初始时： 49 38 65 97 76 13 27初始关键字：初始关键字： 49 38 65 97 76 13 27一趟归并后：一趟归并后： 38 49 65 97 13 76 27二趟归并后：二趟归并后： 38 49 65
8、97 13 27 76三趟归并后：三趟归并后： 13 27 38 49 65 76 97202021/5/266、快速排序思考：利用冒泡排序将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 65212021/5/266、快速排序 （7）38 13 27 49 65 （8）38 13 27 49 65 （9）13 38 27 49 65 （10）13 27 38 49 65冒泡算法最少需
9、要冒泡算法最少需要10步。步。能否用更少的步数完成排序？能否用更少的步数完成排序？222021/5/266、快速排序 基本思想：基本思想：（1）从数列中挑出一个元素，称为 “基准”（2）所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（3）对上步分成的两端无序数组重复（1）和（2）步操作，直到完成排序。232021/5/266、快速排序例：利用快速排序将38、49、65、13、27完成排序？（1）选取38为基准，将大于38的值放右边，小的放左边：（2）在左边数组选取13为基准，重复上步（3）在右边数组选取49为基准，重复上步1327384965242021/5/266、快
10、速排序 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 X22252021/5/267、堆排序堆的定义：堆的定义：若若n个元素的序列个元素的序列a1 a2 an 满足满足则分别称该序列则分别称该序列a1 a2 an为为和和262021/5/267、堆排序 例: 下面序列为堆，对应的完全二叉树分别为:98 77 35 62 55 14 35 4814 48 35 62 55 98
11、 35 779877356255143548(a) 一个大根堆1448356255983577(b) 一个小根堆9877356255143548(a) 一个大根堆1448356255983577(b) 一个小根堆272021/5/267、堆排序建堆建堆 在实际应用中，大多数数据构建的二叉树并不是堆，比如：解决方案：调整次序，构建大根堆或小根堆。282021/5/267、堆排序建堆建堆 例： 292021/5/267、堆排序建堆建堆例：将序列28,25,16,36,18,32构建成大根堆302021/5/267、堆排序堆排序原理堆排序原理 若若在输出堆顶的最小值（最大值）后，使得剩在输出堆顶的最
12、小值（最大值）后，使得剩余余n-1个元素的序列重又建成一个堆，则得到个元素的序列重又建成一个堆，则得到n个个元素的次小值（次大值）元素的次小值（次大值）如此反复，便能得如此反复，便能得到一个有序序列，这个过程称之为到一个有序序列，这个过程称之为。问题：如何在输出堆顶元素后，调整剩余问题：如何在输出堆顶元素后，调整剩余元素为一个新的堆？元素为一个新的堆？312021/5/267、堆排序问题：如何在输出堆顶元素后，调整问题：如何在输出堆顶元素后，调整剩余元素为一个新的堆？剩余元素为一个新的堆？解决方案：输出堆顶元素之后，以堆解决方案：输出堆顶元素之后，以堆中最后一个元素替代中最后一个元素替代之，然
13、后重新构之，然后重新构建堆。建堆。322021/5/267、堆排序 例题：用堆排序将序列20,60,26,30,36,10调整为递增序列。（1）构建小根堆332021/5/267、堆排序（2）提取堆顶10，并用最后一个元素替换堆顶，重新构建小根堆。342021/5/267、堆排序（3）提取堆顶20，并用最后一个元素替换堆顶，重新构建小根堆。352021/5/267、堆排序（4）提取堆顶26，并用最后一个元素替换堆顶，重新构建小根堆。362021/5/267、堆排序（5）提取堆顶30，并用最后一个元素替换堆顶，重新构建小根堆。（6）提取堆顶36，剩余一个数60，提取60。372021/5/268
14、、计数排序 排序原理：排序原理：利用哈希的方法，将每个数据出现的次数都统计下来。哈希表是顺序的，所以我们统计完后直接遍历哈希表，将数据再重写回原数据空间就可以完成排序。382021/5/268、计数排序 对一组数据进行排序做出图解：392021/5/268、计数排序 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 Y402021/5/26部分资料从网络收集整理而来，供大家参考，感谢您的关注！
排序算法及MATLAB实现PPT优秀课件
