两个重要排序算法.ppt

Dept.of Computer Sci. Tech.,YBU 问题：在线性查找方法中，如果要查找的数不存在，比较次数达到最高，等于查找对象的数据规模N（数组元素的总个数），如当N=1024时，比较1024次之后才能决定该数是否存在 原因：每次比较只排除一个数 解决方案 重新组织原始数据（使原始数据排列有规律） 采用高效查找算法（每次比较排除多个数） 两个重要算法 * Intelligent Information Processing LabComputer Sci. Tech.,YBU 排序（Sorting）：重新排列数据集的值，使之满足有序规则 设原始数据存放在数组a中，该数组有N个元素: a[0],a[1],…,a[N-1] 交换数组元素的值，使之满足 a[0]=a[1]=…=a[N-1]（升序排序） 或 a[0]=a[1]=…=a[N-1]（降序排序） 两个重要算法-排序 * Dept.of Computer Sci. Tech.,YBU 基本思路 Step 0 在a[0],a[1],…,a[N-1]中查找最小元素的下标m 交换a[0]与a[m]的值?最小值在a[0]中 Step 1 在a[1],a[2],…,a[N-1]中查找最小元素的下标m 交换a[1]与a[m]的值?次最小值在a[1]中 … Step N-2 在a[N-2], a[N-1]中查找最小元素的下标m 交换a[N-2]与a[m]的值?次最大值在a[N-2]中，最大值在a[N-1]中 两个重要算法-排序 * Dept.of Computer Sci. Tech.,YBU 基本思路 两个重要算法-排序 5 3 6 2 4 2 3 6 5 4 2 3 6 5 4 2 3 4 5 6 i==0 m==3 i==1 m==1 i==2 m==4 i==3 m==3 i: 0~N-2，是尚未排序的起始元素下标 a[i]与a[m]的值需要交换（排序的核心） * Dept.of Computer Sci. Tech.,YBU 关键问题 确定处理范围 第i次处理范围：a[i],a[i+1],…,a[N-1] i: 0,1,…,N-2（是一个循环） 查找最小元素 在a[i],a[i+1],…,a[N-1]中查找最小元素 确定最小元素的下标m（是一个内层循环） 交换数据 把当前范围内的最小元素值与当前范围内的首元素值交换 由于是交换，原始数据只改变排列顺序，而不丢失 两个重要算法-排序 * Dept.of Computer Sci. Tech.,YBU 算法 输入：原始数据存放到数组a中，元素个数为N 输出：a的元素，满足a[0]=a[1]=…=a[N-1] for (i=0; i=N-2; i++) { 确定a[i],a[i+1],…,a[N-1]中最小元素的下标m 交换a[i]与a[m]的值 } 两个重要算法-排序 i为当前处理范围的首元素下标 * Dept.of Computer Sci. Tech.,YBU 算法细化 确定a[i],a[i+1],…,a[N-1]中最小元素的下标m 假定首元素a[i]最小：m=i 扫描a[i+1],a[i+2],…,a[N-1]，一旦发现比a[m]还小的元素，m立即更新为该元素的下标 for (m=i, j=i+1; j=N-1; j++) if (a[ j ]a[m]) m=j; 两个重要算法-排序 a[m]始终是目前为止的最小元素 最初第i个元素是最小的 与第i+1~第N-1个元素比较 * Dept.of Computer Sci. Tech.,YBU 两个重要算法-排序 #include stdio.h #define N 10 main( ) { int a[N], i, j, m, t; for (i=0; i=N-1; i++) scanf(”%d”, a[i]); for (i=0; i=N-2; i++) { for (m=i, j=i+1; j=N-1; j++) if (a[ j ]a[m]) m=j; t=a[m]; a[m]=a[i]; a[i]=t; } for (i=0; i=N-1; i++) printf(”%d, ”, a[i]); } 输入：9? 5?2?0?1?3?6?4?8?7? 输出：0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 输入 排序 输出 确定最小值 交换元素值 * Dept.of Computer Sci. Tech.,YBU 改进 j=N-1 两个运算：-、= 改为jN, 则只有一个运算，且效果相同 在第i步，当a[i],a[i+1],…,a[N-1]中首元素a[i]本身就是最小元素时（