《C语言算法排序与查找》由会员分享，可在线阅读，更多相关《C语言算法排序与查找（23页珍藏版）》请在金锄头文库上搜索。
1、1,排序 程序设计中的常见算法,选择法 冒泡法 插入法 ,2,从所有的数中找出最小的一个，将其放在最前面；接着在余下的数中找出最小的一个，将其放在第二位，依次类推，数列由前往后逐渐成型。,用选择法对10个整数按照从小到大的顺序排列。,思 路,下面以6个数(22、34、10、5、89、45)为例，用图示说明。,3,选择法第一轮：先找出序列中最小的一个放在i=0位置。,i,0,1,2,3,4,5,排i=0位置,i=0,22 34?,22 10?,10 5?,5 89?,5 45?,min!=i?,4,选择法第二轮：找出序列中次小的一个放在i=1位置。,i,0,1,2,3,4,5,排i=1位置,i=
2、1,34 10?,10 22?,10 89?,10 45?,min != i?,5,选择法第三轮：找出序列中第三小的放在i=2位置。,i,0,1,2,3,4,5,排i=2位置,i=2,34 22?,22 89?,22 45?,min != i?,6,选择法第四轮：找出序列中第四小的放在i=3位置。,i,0,1,2,3,4,5,排i=3位置,i=3,34 89?,34 45?,min != i?,7,选择法第五轮：找出序列中第五小的放在i=4位置。,i,0,1,2,3,4,5,排i=4位置,i=4,89 45?,min != i?,中心段出现为 for (i = 0; i arrj) min =
3、 j; if (min != i) temp = arri; arri = arrmin; arrmin = temp; ,分析结果： 输入：n个数存入数组中 输出：排序后的n个数（小大） 方法：选择法，当i：0n-2，初值min=i，j：i+1n-1，比较min与j所指元素值的大小，用min记下较小值的位置，当min！= i时，交换i与min所指元素的值，最小者最先排好，序列从前向后形成。,#include int main(void) int arr10, i, j, temp, min; printf(“Please input 10 numbers:n“); for (i = 0; i
4、 arrj) min = j; if (min != i) temp = arri; arri = arrmin; arrmin = temp; printf(“The sorted numbers:n“); for (i = 0; i 10; i+) printf(“%4d“, arri); printf(“n“); return 0; ,11,对相邻两个数进行比较，将较小的调到前面，两两比较一轮之后，最大的一个数被放置在最后面；接着从头开始重复执行以上操作，次大的数被放置在倒数第二位，依次类推，数列由后往前逐渐成型。,用冒泡法对10个整数排序（从小到大）。,思 路,冒泡法的核心：小数上浮，
5、大数下沉。 冒泡法第一轮：使最大的数放在最后一个位置上,i,0,1,2,3,4,5,排i=5位置,i=0,22 34?,34 10?,10,34,34 5?,34,5,34 89?,89 45?,45,89,冒泡法的核心：小数上浮，大数下沉。 冒泡法第二轮：使次大的数放在倒数第二个位置上,i,0,1,2,3,4,5,排i=4位置,i=1,22 10?,22 5?,22 34?,10,34 45?,22,5,22,冒泡法的核心：小数上浮，大数下沉。 冒泡法第三轮：使第三大的数放在倒数第三个位置上,i,0,1,2,3,4,5,排i=3位置,i=2,10 5?,10 22?,22 34?,5,10,
6、冒泡法的核心：小数上浮，大数下沉。 冒泡法第四轮：使第四大的数放在倒数第四个位置上,i,0,1,2,3,4,5,排i=2位置,i=3,5 10?,10 22?,冒泡法的核心：小数上浮，大数下沉。 冒泡法第五轮：使第五大的数放在倒数第五个位置上,i,0,1,2,3,4,5,排i=1位置,i=4,5 10?,17,中心段程序为 for (i = 0; i arrj+1) temp = arrj; arrj = arrj+1; arrj+1 = temp; ,分析结果： 输入：n个数存入数组中 输出：排序后的n个数（从小大） 方法：冒泡法，当i：0n-2， j：0n-i-2，比较j与j+1所指元素值
7、的大小，小者往前移，大者往后移，最大者最先排好，排在最后，依次类推，序列从后向前形成。,19,#include int main(void) int arr10, i, j, temp; printf(“Please input 10 numbers:n“); for ( i = 0; i arrj+1) temp = arrj; arrj = arrj+1; arrj+1 = temp; printf(“The sorted numbers:n“); for ( i = 0; i 10; i+) printf(“%4d“, arri); printf(“n“); return 0; ,查找算
8、法,顺序查找： 适用范围：一般针对无序表的查找 方法：从数组的第一个元素开始，将被查找数与数组元素进行比较，直到找到或确定不存在为止。 折半查找： 适用范围：有序表 方法：设置变量low和high分别指向查找数据段的起始位置和末位置，用mid指向中间位置，将被查找数与mid位置指向的数进行比较，若被查找数大于mid位置指向的数，则将low与mid之间的数折掉， low定位于mid+1位置；若被查找数小于mid位置指向的数，则将mid 与high之间的数折掉， high定位于mid-1位置；继续求mid位置，并比较被查找数与mid位置指向的数，直到找到或确定不存在为止。,顺序查找,int Sea
9、rch(long a, int n, long x) int i; for (i=0; in; i+) if (ai = x) return (i); return (-1); ,x=34,折半查找,x=34,0,1,2,3,4,5,34 22,3445,34=34,int BinSearch(long a, int n, long x) int low, high, mid; low = 0; high = n - 1; while (low amid) low = mid + 1; else if (x amid) high = mid - 1; else return (mid); return(-1); ,
