[工学]第6章数组.ppt

排序算法——选择法排序（3） 选择法排序算法描述(P213) for (i=0; in-1; i++) { k = i; for (j=i+1; jn; j++) { if (score[j] score[k]) 记录此轮比较中最高分的元素下标 k = j; 若k中记录的最大数不在位置i，则 交换成绩score[j]和score[i]， 交换学号num[j]和num[i]； } } void DataSort(int score[], long num[], int n) /*选择法*/ { int i, j, k, temp1; long temp2; for (i=0; in-1; i++) { k = i; for (j=i+1; jn; j++) { if (score[j] score[k]) { k = j; /*记录最大数下标位置*/ } } if (k != i) /*若最大数不在下标位置i*/ { temp1 = score[k]; score[k] = score[i]; score[i] = temp1; temp2 = num[k]; num[k] = num[i]; num[i] = temp2; } } } 排序和查找 查找（Searching）算法 顺序查找 折半查找 【例】顺序查找学号 int LinSearch(long num[], long x, int n) { int i; for (i=0; in; i++) { if (num[i] == x) { return (i); } } return (-1); } 哈，找到了！ 事先不必排序 折半查找示意图 查找算法——折半查找(1) 数组下标 0 1 2 3 4 99011 99013 99015 99017 99019 第1次循环 low high mid 查找值x=99017 xa[mid] low=mid+1 99011 99013 99015 99017 99019 第2次循环 high low=mid x=a[mid] 找到 条件:low=high 折半查找示意图 查找算法——折半查找(1) 折半查找示意图 查找算法——折半查找(2) 数组下标 0 1 2 3 4 99011 99013 99015 99017 99019 第1次循环 low high mid 查找值x=99016 xa[mid] low=mid+1 99011 99013 99015 99017 99019 第2次循环 high low=mid xa[mid] high=mid-1 99011 99013 99015 99017 99019 第3次循环 low high 不满足low=high,循环结束 未找到! int BinSearch(long num[], long x, int n) { int low, high, mid; low = 0; high = n - 1; while (low = high) { mid = (high + low) / 2; if (x num[mid]) { low = mid + 1