《2013教科版选修1《排序》课件1》由会员分享，可在线阅读，更多相关《2013教科版选修1《排序》课件1（25页珍藏版）》请在金锄头文库上搜索。
1、第五章排序 课程目标课程目标何谓排序交换式排序冒泡排序法快速排序法选择式排序选择排序法插入式排序插入排序法本章体验项目 本程序启动后，进入到彩票机的界面，在界面的又上角有一组单选框，分别 是手选和机选（默认）。 如果是机选，则点击“开始”按钮生成一组1到30的随机数并显示在7个小文 本框里（没有控制是否有重复数）。点击“排序”按钮将7个数进行排序后 并显示在界面中间的文本域中。 如果是手选，则自己在7个文本框中填写所喜欢的号码，然后点击“开始” 按钮将7个号码排序后输出。 “清除”按钮是将显示区域的数据清除，“退出”按钮是退出程序。5.1 何谓排序 5.1.1排序的意义 所谓排序是将一组数据依
2、照一定的顺序排列起来。最 常见的排序是“从小到大”的“递增排序”和“从大到小”的“ 递减排序”。 以下列数组为例进行说明递增排序：递减排序： 5.1.2排序的特性 稳定性 不稳定性 排序过后能使值相同的数据保 持原顺序中的相对位置 排序过后不能使值相同的数据 保持原顺序中的相对位置 例如：稳定排序的结果： 不稳定排序的结果： 排序后7（）仍旧在7（）之前，二者相对位置不变 排序后7（）则在7（）之后，二者相对位置发生了改变 5.1.2排序的分类排序的分类大致上可分为两种 内部排序 外部排序 将欲处理的数据整个存放到内部存储器中 排序，数据可被随机存取 交换式排序 选择式排序 插入式排序 欲处理
3、的数据两过于庞大，无法全部存放到内部存储 器，必须借助外部的辅助存储器（比如：硬盘）， 由于数据是存在外存中，故数据不可随机被存取 合并排序法 直接合并排序法 在本书中只介绍内部 排序法。以下所有排序均为从 小到大升序排列 5.2交换式排序 内部排序中的交换式排序，是运用数据值比较后，以 判断规则对数据位置进行交换，已达到排序的目的。 交换式排序法又可分为两种 冒泡排序法（Bubble Sort） 快速排序法（Quick Sort） 5.2.1冒泡排序法 排序方法 从数组第一个元素开始，将第一个元素ai同下一个 元素ai+1进行比较，如果ai大于ai+1则将两者相交换 。直到比较完最后一个元素
4、。这时数组中最小的元素会 被交换成为数组首端。 由于该比较法每次可以将最大或者最小的元素以交换 的方式移动到数组首或数组为，就像气泡从水底浮向水 面一样，到水面时气泡最大，故称该排序法为冒泡排序 法。举例说明 如数组：int a=6,5,8,3,7; 该数组中一共有5个数据，所以要比较4趟，每趟相互比较4次。 第一趟： （1）a0 VS a1，因为a0a1，所以交换a0和a1 （2）a1 VS a2，因为a1a3，所以交换a2和a3。 （4）a3 VS a4，因为a3a4，所以交换a3和a4。 这样第一趟就比较完了，数组中最大的8也 到了最后一位，成为第一个吐出的泡泡。按照这样的步骤继续循环直
5、到所有元素都排 序完成为止。 public class BubbleSort public void bubbleSort(int a) int t=0; for(int i=0;iaj) t=ai; ai=aj; aj=t; for(int k=0;km) if(ii) quickSort(a,i,right,index); 如果两边扫描的下标交错，就停止（完成一次）将数组分段后递归调用自己再排序直到找到比m值大时停止 直到找到比m值小时停止 该排序方法为不稳定排序，即排序后数值 相同的元素之间相对位置会发生改变。此方法是所有排序方法中速度最快的。 5.3选择式排序 选择式排序可分为两种选择
6、排序法 堆排序法 在本教材中只给大家介绍选择排序法，堆排序法如读者有兴趣请 查阅其他相关书籍 5.3.1 选择排序法 选择排序法排序的方法是： 先在n个元素中找出最小的元素。 然后将此元素和数组第一个元素交换。 再从剩下的（n-1）个元素中找出最小的和第二个元素交 换。 这样不断循环，直到所有元素均已排序完成，从而达到排 序的目的。 下面我们来看一个选择式排序的例子：public void selectionSort(int a) int temp; for(int i=0;i=0 j-; aj+1=insertNode; System.out.print(“正在排序：“); for(k=0;ka.length;k+) System.out.print(ak+“ “); System.out.println(); 寻找合适的空间来放置 当前要排序的元素 打印当前排序情况 直接插入排序是稳定的排序方法 本章小节何谓排序 交换式排序冒泡排序法 快速排序法 选择式排序 选择排序法 插入式排序 插入排序法
