算法导论：第二章总结

SELECTION-SORT(A)

n : length[A]
	for j : 1 to n − 1
		do smallest : j
			for i : j + 1 to n
				do if A[i] < A[smallest] 
					then smallest : i
			exchange A[j] and A[smallest]

INSERTION-SORT（A）

for j : 2 to length[A]
	do key : A[j]
	i : j-1
	while i>0 and A[i]>key
		do A[i+1] : A[i]
			i : i-1
	A[i+1] : key

MERGE(A, p, q, r) 
n1 : q-p+1 
n2 : r-q 
create arrays L[1..n1+1] and R[1..n2+1]
for i : 1 to n1     
	do L[i] : A[p+i-1] 
for j : 1 to n2     
	do R[j] : A[q+j]
L[n1+1] :  ∞
L[n2+1] :  ∞
i : 1
j : 1
for k : p to r
	do if L[i]<=R[j]
		then A[k] : L[i]
			i : i+1
		else A[k] : R[j]
			j : j+1

MERGE-SORT(a, p, r)

if p<r
	then q : (p+r)/2
		MERGE-SORT(A, p , q)
		MERGE-SORT(A, q+1, r)
		MERGE(a, p, q, r)

BUBBLESORT(A)

for i : 1 to length[A]
    do for j : length[A] downto i+1
        do if A[j] < A[j-1]
            then exchange A[j] and A[j-1]

自己的插入排序：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define N 12
 4 
 5 int A[N] ={0,4,8,5,9,1,6,3};
 6 
 7 
 8 void insertion_sort(int A[]){
 9     int key,i,j;
10     for(j=2; j<8; ++j){
11         key = A[j];
12         i = j-1;
13         while(i>0 && A[i]>key){
14             A[i+1] = A[i];
15             i = i-1;
16         }
17         A[i+1] = key;
18     }
19 }
20 
21 int main(int argc, char const *argv[])
22 {
23     
24     insertion_sort(A);
25     for (int i = 0; i < 10; ++i)
26     {
27         printf("%d ", A[i]);
28     }
29     printf("
");
30     return 0

自己写的合并排序：

 1 #include <stdio.h>  
 2 #include <iostream>  
 3 using namespace std; 
 4  
 5 void Merge(int* A,int p,int q,int r) 
 6 { 
 7     int n1= q-p+1; 
 8     int n2= r-q; 
 9      
10     int *L= new int[n1+1]; 
11     int *R= new int[n2+1]; 
12  
13     int i=0; 
14     int j=0; 
15  
16     for(i=0;i<n1;i++) 
17     { 
18         L[i]=A[p+i-1]; 
19          
20     } 
21      
22     for(j=0;j<n2;j++) 
23     { 
24         R[j]=A[q+j]; 
25      
26     } 
27     L[n1] = 100;
28     R[n2] = 100;
29      
30     i = 0; 
31     j = 0; 
32      
33     for(int k = p-1;k < r; k++) 
34     { 
35         if(L[i]<=R[j]) 
36         { 
37             A[k] = L[i]; 
38             i = i+1;    
39         } 
40         else 
41         { 
42             A[k] = R[j]; 
43             j = j+1;     
44         } 
45     } 
46 }  
47  
48 void Merge_Sort(int *A,int p,int r) 
49 { 
50     if(p<r) 
51     { 
52         int q=(p+r)/2; 
53         Merge_Sort(A,p,q); 
54         Merge_Sort(A,q+1,r); 
55         Merge(A,p,q,r); 
56     } 
57 } 
58  
59 int A[15] = {11,12,13,14,15,1,2,3,4,5,6,7,8,9,10};  
60  
61 int main(int argc, char **argv) 
62 { 
63     Merge_Sort(A,1,15); 
64      
65     for(int i=0;i<15;i++) 
66     { 
67         cout<<A[i]<<"	"; 
68     } 
69     cout<<endl; 
70     return 0; 
71 }