Posted on 2014-07-19 12:27
xLsDg 閱讀(145)
評論(0) 編輯 收藏 引用 所屬分類:
代碼庫
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #define MAXSIZE 10
5
6 typedef struct {
7 int r[MAXSIZE + 1];
8 int length;
9 } SqList;
10
11 void printL( SqList *L )
12 {
13 int i;
14
15 for ( i = 1; i <= L->length; i++ ) {
16 printf( "%d ", L->r[i] );
17 }
18
19 printf( "\n" );
20 }
21
22 void swap( SqList *L, int i, int j )
23 {
24 //printf( "%d ---> %d\n", L->r[i], L->r[j] );
25 L->r[i] ^= L->r[j];
26 L->r[j] ^= L->r[i];
27 L->r[i] ^= L->r[j];
28 printL( L );
29 }
30
31 void BubbleSort0( SqList *L )
32 {
33 int i, j;
34
35 for ( i = 1; i < L->length; i++ ) {
36 for ( j = i + 1; j <= L->length; j++ ) {
37 if ( L->r[i] > L->r[j] ) {
38 swap( L, i, j );
39 }
40 }
41 }
42 }
43
44 void BubbleSort1( SqList *L )
45 {
46 int i, j;
47
48 for ( i = 1; i < L->length; i++ ) {
49 for ( j = L->length - 1; j >= i; j-- ) {
50 if ( L->r[j] > L->r[j + 1] ) {
51 swap( L, j, j + 1 );
52 }
53 }
54 }
55 }
56
57 void BubbleSort2( SqList *L )
58 {
59 int i, j, flag = 1;
60
61 for ( i = 1; i < L->length && flag; i++ ) {
62 for ( j = L->length - 1, flag = 0; j >= i; j-- ) {
63 if ( L->r[j] > L->r[j + 1] ) {
64 swap( L, j, j + 1 );
65 flag = 1;
66 }
67 }
68 }
69 }
70
71 void SelectSort( SqList *L )
72 {
73 int i, j, min;
74
75 for ( i = 1; i < L->length; i++ ) {
76 min = i;
77
78 for ( j = i + 1; j <= L->length; j++ ) {
79 if ( L->r[min] > L->r[j] ) {
80 min = j;
81 }
82 }
83
84 if ( i != min ) {
85 swap( L, i, min );
86 }
87 }
88 }
89
90 void InsertSort( SqList *L )
91 {
92 int i, j;
93
94 for ( i = 2; i <= L->length; i++ ) {
95 if ( L->r[i] < L->r[i - 1] ) {
96 L->r[0] = L->r[i];
97
98 for ( j = i - 1; L->r[j] > L->r[0]; j-- ) {
99 L->r[j + 1] = L->r[j];
100 }
101
102 L->r[j + 1] = L->r[0];
103 printL( L );
104 }
105 }
106 }
107
108 void ShellSort( SqList *L )
109 {
110 int i, j, increment = L->length;
111
112 do {
113 increment = increment / 3 + 1;
114
115 for ( i = increment + 1; i <= L->length; i++ ) {
116 if ( L->r[i] < L->r[i - increment] ) {
117 L->r[0] = L->r[i];
118
119 for ( j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment ) {
120 L->r[j + increment] = L->r[j];
121 }
122
123 L->r[j + increment] = L->r[0];
124 printL( L );
125 }
126 }
127 } while ( increment > 1 );
128 }
129
130 int main()
131 {
132 SqList L;
133
134 L.length = 9;
135
136 L.r[0] = 0;
137 L.r[1] = 9;
138 L.r[2] = 1;
139 L.r[3] = 5;
140 L.r[4] = 8;
141 L.r[5] = 3;
142 L.r[6] = 7;
143 L.r[7] = 4;
144 L.r[8] = 6;
145 L.r[9] = 2;
146
147 printL( &L );
148 //BubbleSort0( &L );
149 //BubbleSort1( &L );
150 //BubbleSort2( &L );
151 //SelectSort( &L );
152 //InsertSort( &L );
153 ShellSort( &L );
154 printL( &L );
155
156 return 0;
157 }
158