常见三种排序方法

数组操作■(1)选择排序法(2)冒泡排序法(3)比较排序法■

(1)顺序查找法(2)折半查找法(1)数组元素插入(2)数组元素删除(1)选择排序——第17、26套的填空题简单选择排序：从1到n

选出关键值最(大)小的记录,交换到第一个位置上，然后从2到n

选

出

键

值

最

(

大

)

小

的

记

录

，

交

换

到

第

二个位置上，

..数组下标

0初态

i=0→54k=0

↑54k=0

54k=0个54i=0判

断a[j]<a[k]?k=jk!=i,

交

换用选择法对数组

int

a[5]={54,71,58,29,31}进行升序排序431313131j=4^3292929j=3

个

29

k=358

j=2^

5858171j=1

个717171258互换第

一

趟判

断a[j]<a[k]?k=jk=jk=jk!=i,

交

换543154

3154

31k=3|j=454

31k=4互换29

31

58

54

71292929297171

i=1个

71

i=1585858第二趟判断a[j]<a[k]?k!=i,交换k=i,

不交换29

31

58

54713131第

三

趟

第四趟292954“选择排序法”(由小到大排序)■

选择法(递增)■基本思想：□(1

)

从n

个数的序列中选出最小的数，与第1个数交

换位置

；□

(

2)除第1个数外，其余n-1个数再按(1)的方法选出

次小的数，与第2个数交换位置；□

(3)

重复(1)n-1遍，最后构成递增序列。■

实现方法：采用双重循环(循环的嵌套)□

外循环为i:

控制排序趟数□

内循环为j:

第i趟排序过程中的下标变量“选择”排序法的结构形式。K

是记下最值的下标for(i=0:i-n-1;i++)

if(a[k]>bj)k=j;{t=a[i];a[i]=a[k];a[k]=t;}}n不在本次排序中的位置#include<stdio.h>#include

"stdlib.h"voidmain(){const

int

N=10;inti,j,k,t,a[N];{a[i]=rand()%61;printf("%d,",a[i]);}printf("ln");for(i=0;i<N-1;i++)for(j=i+1;j<N;j++)if(a[k]>a[j])k=j;if(k!=i){t=a[k];a[k]=a[i];

a[i]=t;

}

}for

printf("%5d",a[i]);printf("In");{k=i;第二种：“冒泡法”

(由小到大排序)■

基本思想：□

(1)从第一个元素开始，对数组中两两相邻的元素

比较，将值较小的元素放在前面，值较大的元素

放在后面，

一轮比较完毕，最大的数存放在a[N-1]

中；□(

2)然后对a[0]到a[N-2]的N-1个数进行同(1)的

操作，次最大数放入a[N-2]元素内，完成第二趟

排序；依次类推，进行N-1趟排序后，所有数均有

序。实现方法：采用双重循环(循环的嵌套)2525252511111156494911252525495611494136367811564136411165413649654136564136653678交换排序：俩俩比较待排序记录的键值，若逆序，则交换，

直到全部满足为止第一趟排序后初始关键字第五第四第三第二趟

排

序

后趟

排

序

后(2)冒泡排序第六趟排序后排

序

后挡1

A

国交换排序

—

“冒泡”排序法特点：逐个对数组中每相邻二数进行比较，若条件满足，则互相交换，否则保持原位置不变。排序过程：

(设数据存于A

数组中，n个数据，按递增

次序排序)A[0]与A[1]比较

A[0]<A(1)不换，否则对调A[1]与A[2]比较

A[1]<A[2]不换，否则对调A[n-2]与A[n-1]比较A[n-2]<A[n-1]不换，否则对调千万要注意!!若有n个数据，需要进行i=n-1轮比较。每轮中比较

的次数为j=n-i+1次

。冒泡法排序用冒泡法对10个数排序(由小到大)。48275924587924857924S78925789245789冒泡排序的结构形式(递增)for(i=0;i<N-1;i++)for(j=0;j<N-i-1;j++)if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}关键代码：for(i=1;i<n;

i++)for(j=0;j<n-i;j++)if(a[i]>a[j+1]){t=a[j];alil-i11ei:11=t;}注意i的边界注意排序堂数i的初值for(i=

n-1

i++)for(j=0

;j<

n-i-1

;j++)if(a[j]>a[j+1){t=aL,la[j]=a[j+1];a[j+1]=t;}注意j的边界14inti,j,t,a[N];printf("inputNnumbers:\n");for(i=0;i<N;i++)scanf("%d",&a[i]);printf("\n");for(i=0;i<N-1;i++)for(j=0;j<N-i-1;j++)if(a[j]>a[j+1]{t=a[j];a[j]=a[j+1];a[j+1]=t;}

for(i=0;i<N;i++)printf("%5d,",a[i]);printf("\n");#include<stdio.h>

#define

N6voidmain()冒泡程序{}注意排序堂数i的初值for(i=

O

;i<for(j=i+1

;j<

n注意i的边界;i++);j++)if(a[i]>a[j]){t=a[i;ai]=a[j];a[j]=t;}第三种：比较排序(上机19、52套编程题)注

意a[i]与a[j]

比较注意j的边界补充知识一：查找查找的方法很多。如：顺序查找、二分法查找等等。1、顺序查找：最简单的查找方法，基本思想是利用循环顺序扫描整个数组，依次将每个元素

与待查找值比较，直至找到或找不到。·

对于无序数组，顺序查找是唯一可行的办法·

对大批量数据用顺序查找占机器时间较多。int

Search(long

a[],int

n,long

x){int

i;for(i=0;i<n;i++){if(a[i]==x){return

(i);}return(-1);2、二分法查找/折半查找：二分法查找的条件：必须是有序数列，即数组中的各元素已按数值大小按递增或递减

次序排列!查找过程：(1)将数列对分，找出中间数据(2)用此数据与要查的数据比较(3)数值相等则结束查询，否则确定要查的数据所在区间，逐步缩小查找范围，每次将

数列区间缩小一半，直到找到或找不到为

止。(08,

14,23,37,46,

55,

68,

79,91)mid

hig(08,1OW

14,

23,

37,

46,

55,

68,79.

91)lomidhigh=mid-1(08,14,23,

37,

46,55,68,

79,

91)lowmidhigh(08,

14,23,37,

46,55,68,79,

91)lowmidhig(08,

14,23,

37,

46,

55,68,

79,

91)lowmidhigh(08,

14,

23,37,

46,

55,

68,

79,

91)折半查找(二分法查找)下标

0

1

2

3

4

5

6

7

8low

highmidhh折

半

查

找1,5,6,9,11,17,25,34,38,41个

个

食

↑

↑共有10个已排好序的数据：查找9。up=9low=0mid=(up+low)/2=3查找范围：上

界up

→下

界low中

值midint

BinSearch(long

a[],int

n,long

x){int

low,high,mid;low

=0;high=n-1;while(low<=high){

mid

=(high

+low)/2;if(x

>a[mid])

{low

=mid

+1;}elseif(x<a[mid]){high=mid-1;}

else{return(mid);}}return(-1);2#include<stdio.h>main(){int

up=9,low=0,mid,found=0,find;int

a[10]={1,5,6,9,11,17,25,34,38,41};scanf(“%d”,&find);printf("\n");while(up>=low&&!found){mid=(up+low)/2;if(a[mid]==find){found=1;break;}else

if(a[mid]>find)up=mid-1;elselow=mid+1;i

f(found)printf("found

number

is

%dth"mid);

else

printf("no

found");}}折查找程补充知识二：数组元素的插入、删除前提：被操作数组已经是有序数组，操作前

后不改变数组的有序性1、插入数据·

在有序数组中插入数据后，数组仍然有序。·

要求数组有足够的空间。插入过程：(1)确定数据插入位置(2)从最后一个元素开始逐个后移，直

到将第i个位置腾出。

(a[i+1]=a[i])(3)将数据插入到指定下标元素位置中aoa1·ai-1Xa;ai+1·