10 65
865
9761059 95 97.6
2009-7-28
3
()
2009-7-28
4
2.8
2.8.1
1
2
2009-7-28
5
MAX
0
1
2
3
4
…
…
…
key info#define MAX 20
typedef struct
{ int key;
float otherinfo;
}RedType;
2009-7-28
6
2009-7-28
7
2.8.2
1:
2
8-2-1
2009-7-28
8
2.8.2
n O(n2).
1:
2
[53] 27 36 15 69 42
[27 53] 36 15 69 42
[27 36 53] 15 69 42
[15 27 36 53] 69 42
[15 27 36 53 69] 42
[15 27 36 42 53 69]
nn-1
2009-7-28
9
void insertSort(RedType L[ ],int n)
{ int i,j;
for(i=2; i<=n; i++)
if(L[i].key<L[i-1].key)
{ L[0]=L[i]; /* */
for( j=i-1; L[0].key<L[j].key;j )
L[j+1]=L[j]; /* */
L[j+1]=L[0]; /* */
}
}
:KiKi-1,K i-2,… K1,
2009-7-28
10
2
8-2-2
2009-7-28
112
65 6
[ 15 27 36 53 69 ] 42
low?mid? high
[ 15 27 36 53 69 ] 42
low? high
mid
[ 15 27 36 53 69 ] 42
high?low
[ 15 27 36 42 53 69 ]
(high<low low high+1 )
( 42>36 )
( 42<53 )
2009-7-28
12void BinsertSort(RedType L[ ],int n)
{ int i,low,high,mid;
for(i=2; i<=n; ++i){
L[0]=L[i]; /* r[0]*/
low=1; high=i-1;
While(low<=high)
{mid=(low+high)/2;
if (L[0].key<L[mid].key) high=mid-1; //
else low=mid+1; }
for( j=i-1; j>=high+1;j )
L[j+1]=L[j]; /* */
L[high+1]=L[0]; /* */
} /* for*/
}/**/
/**/
2009-7-28
13
1
1~n2 n
O(n2)
2.8.3
8-2-3
2009-7-28
14
2.8.3
1
1~n2 n
O(n2)
8 3 9 1 6
8 3 9 1 6
8 3 9 1 6
8 3 9 1 6
i j
k
i jk
i jk
i jk
1 3 9 8 6
i j
k
1 3 9 8 6
i
k
j
1 3 9 8 6
i
k
j
1 3 9 8 6
i k j
2009-7-28
15
void SelectSort( RedType L[ ],int n)
{ int i,j,k,t;
for (i=1,i<=n;++i /*i*/
{ k=i
for(j=i+1;j<=n;++j)
if ( L[j].key<L[k].key) k=j; /*L[k] I*/
if(k!=i) { t=L[i]; /**/
L[i]=L[k]; L[k]=t }
} /*FOR*/
} /* SelectSort*/
2009-7-28
162
(1)
89
76 24
33 15 10
11
25 36
49 7856
(a),(b):
(2)
1
2
8-2-4
2009-7-28
17(3) ()
65
25 36
56 49 78 41
11
(b)
65 36
56 49 78 41
11 (c)
25
11
25 36
56 49 78 41
65
(a)
25
49 36
56 65 78 41
(d)11
2009-7-28
184
25
56 49
78 11 65 41
36
(a)
n=8,int(n/2)=4
25
56 49
36 11 65 41
78 (b),78
25
56 41
36 11 65 49
78
(c),49
25
11 41
36 56 65 49
78
(d),56 (e),
11
25 41
36 56 65 49
78
2009-7-28
19
E
typedef Sqlist HeapType; //
void HeapAdjust( HeapType &H,int s,int m){
// H.r[s..m]H.r[s],key
//H.r[s],keyH.r[s..m]
rc=H.r[s];
for(j=2*s; j<=m; j*=2) {
//
if( j<m && H.r[j].key <H.r[j+1].key) + +j;// j key
if( rc.key >= H.r[j].key) break;
H.r[s]=H.r[j]; s=j; //
}// for
H.r[s]=rc;
}
33
76
10
15
24j
s 10 76 24 33 15
1 2 3 4 5
rc.key = 10
m = 5
s = 1
2009-7-28
20
typedef Sqlist HeapType;
void HeapAdjust( HeapType &H,int s,int m){
rc=H.r[s];
for(j=2*s; j<=m; j*=2) {
if( j<m && H.r[j].key <H.r[j+1].key) + +j;
if( rc.key >= H.r[j].key) break;
H.r[s]=H.r[j]; s=j; //
}// for
H.r[s]=rc;
}
33
10
76
15
24
j
s
76 10 24 33 15
j=2*j=4
33
10
76
15
24
s
76 33 24 10 15
j=2*j=8>m
2009-7-28
21
void HeapSort( HeapType &H)
{
//H
for( i=H.length/2; i>0;i)
HeapAdjust(H,i,H.length); // H.r[1..H.length]
For(i=H.length; i>1;i){
//
rc=H.r[1]; H.r[1]=H.r[i]; H.r[i]=rc;
HeapAdjust(H,1,i-1); //H.r[1..i-1]
}
}
F
2009-7-28
22
A,25
56 49
78 11 65 41
36
i=4
(1)
25
56 49
78 11 65 41
36
i=3
(2)
25
56 65
78 11 49 41
36 (3)(4)
25
56 65
78 11 49 41
36
i=2
(5)
25
78 65
56 11 49 41
36
i=1
F
2009-7-28
23
(7)
25
56 65
36 11 49 41
78
B:
(6)
78
56 65
36 11 49 41
25
(8)
11
25 36
41 49 56 65
78
2009-7-28
24
2.8.4
1
1223
……
n-1
n-1
O(n) O(n2)
nn-1 8-2-5
2009-7-28
25
4936416511
7836
653641
56364165
413641561178
36364149115649
25252511494956
11111125252525
2009-7-28
26
C
Void bubsort(RedType L[ ],int n)
{ int i,x,j=1,k=1;
while (j<n)&&(k>0);
{ k=0;
for (i=1;i<=n-j; i++)
if (L[i+1].key<L[i].key)
{k++;x=L[i];L[i]=L[i+1];L[i+1]=x;}
j++;
} /*while*/
} /*Bobsort*/
2009-7-28
27
2 (
lowhigh key highlow low=high
O(log2n)
8-2-6
2009-7-28
28
6 18 23 52 67
key
23 52 6 67 18
low high
18 52 6 67 23
low high
18 23 6 67 52
high
[18 6] 23 [67 52]
//
low high
2009-7-28
29
2.8.5
[23] [52] [67] [6] [18] [10]
[23 52] [6 67] [10 18]
[6 23 52 67] [10 18]
[6 10 18 23 52 67]
nn1[n/2]21n
2009-7-28
30
2.8.6
n
n
2009-7-28
31
P77 34
P78 35~44