C语言课件(查找和排序).ppt

1、查找与排序,查找与排序,查找 顺序查找 折半查找 排序 直接插入排序 简单选择排序 冒泡排序,查找,查找 根据指定的关键字查找数组中的特定元素。 常用方法 顺序查找 折半查找,顺序查找,顺序查找 适用于小型和（或）没有排序的数组。 用关键字与数组的元素依次进行比较。 平均而言，要与数组的一半元素进行比较,87,查找表,关键字,#define N 10 void main() int listN+1=0,65,72,83,79,97,87,75,57,91,78; int key,i; printf(Input search key:); scanf(%d, ,顺序查找,顺序查找举例（cw100

2、9.c）,折半查找,折半查找 适用于已经排好序的数组。 用关键字与数组的中间元素比较 如果相等，则查找结束找到 如果keymiddle，则继续在后半部分查找 如果没有可查找的部分，则查找结束没有找到,83,low,mid,high,折半查找,折半查找举例（cw1010.c）,#include #define N 10 void main() int i, low, mid, high, key, found; int listN+1=0,57,65,72,75,78,79,83,87,91,97; printf(Sorted list:n); for (i=1;i=N;i+) printf(%

3、-4d, listi); printf(n); printf(Input search key:); scanf(%d, ,折半查找,折半查找举例,low=1; high=N; found=0; while (lowlistmid) low=mid+1; else if (key=listmid) found=1; else high=mid-1; if (found) printf(Success! The position is %d., mid); else printf(Not found!); ,考虑不要found变量,排序,排序 按特定的顺序来安排数据。 常用方法 直接插入排序 简

4、单选择排序 冒泡排序,数据插入,问题 把一个数据插入到已排好序的有序表中，从而得到一个新的、长度增1的有序表。,83,1.找到插入点,2.腾出位置,3.插入数据,数据插入,数据插入（cw1011.c） 把一个数据插入到一个有序表中。,#include #define N 20 void main() int i, j, x, len=9; int listN=57,65,72,75,78,79,87,91,97; printf(Sorted list:n); for (i=0;ilen;i+) printf(%-4d, listi); printf(n); printf(Input a int

5、eger to be inserted into the list:); scanf(%d,数据插入,数据插入 续,for (i=0;(xlisti) ,找到插入点,“腾出位子”,插入数据,直接插入排序,直接插入排序,直接插入排序,直接插入排序（cw1012.c） 输入任意个数，按从小到大的顺序对它们进行排序。,#include #define N 10 void main() int i, j, k, len; int listN, x; printf(Input several integers to construct a listn); printf(“How many?(%d)”,

6、N); scanf(%d, ,任意个数： 程序运行时确定,直接插入排序,直接插入排序 续,printf(nTo sort.n); for (i=1;ilistj) ,记住listi,把listi插入有序数列：list0.listi-1 （1）查找插入点 （2）移动数据 （3）插入,简单选择排序,简单选择排序,一趟简单选择排序的操作：通过n-i次数据间的比较，从n-i+1个记录中选出最小的数，并和第i个数交换。,简单选择排序,简单选择排序（cw1013.c） 输入任意个数，按从小到大的顺序对它们进行排序。,#include #define N 10 void main() int i, j, l

7、en, min; int listN, tmp; printf(Input several integers to construct a list.n); printf(“How many?(%d)”, N); scanf(%d, ,简单选择排序,简单选择排序 续,printf(nTo sort.n); for (i=0;ilistj) min=j; tmp=listi; listi=listmin; listmin=tmp; printf(Finished! The list has been sorted:n); for (i=0;ilen;i+) printf(%-4d,listi);

8、 ,冒泡排序,冒泡排序 将相邻两个数比较，把小的调到前面，大数放到后面。,冒泡排序,冒泡排序（cw1014.c） 输入任意个数，按从小到大的顺序对它们进行排序。,#include #define N 10 void main() int i, j, len; int listN, tmp; printf(Input several integers to construct a list.n); printf(“How many?(%d)”, N); scanf(%d, ,冒泡排序,冒泡排序 续,printf(nTo sort.n); for (i=0;ilistj+1) tmp=listj; listj=listj+1; listj+1=tmp; printf(Finished! The list has been sorted:n); for (i=0;ilen;i+) printf(%-4d,listi); ,