常用算法
1 ////////////////////////////////////////////////////////////////////////////////
2 //
3 // 常用算法
4 //
5 ////////////////////////////////////////////////////////////////////////////////
6
7 #include <stdio.h>
8 #include <string.h>
9
10 void BubbleSort( int nArr[], int nLength );
11 void SelectSort( int nArr[], int nLength );
12 void InsertSort( int nArr[], int nLength );
13 void QuickSort( int nArr[], int nLength );
14 int Search( int nArr[], int nLength, const int nFindVal );
15 int HalfSearch( int nArr[], int nLength, const int nFindVal );
16
17
18 ////////////////////////////////////////////////////////////////////////////////
19 //
20 // 1、排序
21 //
22 ////////////////////////////////////////////////////////////////////////////////
23
24 ////////////////////////////////////////////////////////////////////////////////
25 //
26 // 1.1、冒泡排序
27 //
28 // 冒泡排序的基本思想:
29 // 从R[0]开始，逐个比较R[i]和R[i+1](i=0,1,
,n-1)的大小，若R[i] > R[i+1]
30 // 则交换R[i]和R[i+1]的位置。第一趟全部比较完毕后R[n-1]是序列中最大的元素。再从
31 // R[1]开始逐个比较R[i]和R[i+1](i=0,1,,n-2)的大小若R[i] > R[i+1]则交换R[i]
32 // 和R[i+1]的位置。等第二趟全部比较完毕后R[n-2]是序列中最大的元素。如此反复进行
33 // n-1趟冒泡排序后，序列中的元素便排好序了。
34 //
35 ////////////////////////////////////////////////////////////////////////////////
36
37 void BubbleSort( int nArr[], int nLength )
38 {
39 int i, j, iTemp;
40 bool bIsChange = true;
41
42 for ( i = 0; i < nLength - 1; i++ )
43 {
44 if ( !bIsChange )
45 {
46 break;
47 }
48
49 bIsChange = false;
50 for ( j = 0; j < nLength - 1 - i; j++ )
51 {
52 if ( nArr[j] > nArr[j + 1] )
53 {
54 iTemp = nArr[j];
55 nArr[j] = nArr[j + 1];
56 nArr[j + 1] = iTemp;
57
58 bIsChange = true;
59 }
60 }
61 }
62 }
63
64 ////////////////////////////////////////////////////////////////////////////////
65 //
66 // 1.2、选择排序
67 //
68 // 选择排序的基本思想:
69 // 设所排列序列的元素个数为n，对i值取0,1,2,,n-2，从R[i],,R[n-1]这些
70 // 元素中找出最小的元素，与R[i]进行交换，执行n-1趟后完成了元素排序。
71 //
72 ////////////////////////////////////////////////////////////////////////////////
73
74 void SelectSort( int nArr[], int nLength )
75 {
76 int i, j, nMinIndex, nTemp;
77
78 for ( i = 0; i < nLength; i++ )
79 {
80 nMinIndex = i;
81 for ( j = i + 1; j < nLength; j++ )
82 {
83 if ( nArr[j] < nArr[nMinIndex] )
84 {
85 nMinIndex = j;
86 }
87 }
88
89 if ( i != nMinIndex )
90 {
91 nTemp = nArr[nMinIndex];
92 nArr[nMinIndex] = nArr[i];
93 nArr[i] = nTemp;
94 }
95 }
96 }
97
98 ////////////////////////////////////////////////////////////////////////////////
99 //
100 // 1.3、插入排序
101 //
102 // 插入排序的基本思想:
103 // 把n个元素的序列划分为己排序部分和未排序部分，即在处理第i个元素R[i-1]时，
104 // R[0],R[1],,R[i-2]是已排好的有序部分，R[i-1],R[i],,R[n-1]属于未排序的
105 // 部分。这时，用R[i-1]依次与R[0],R[1],,R[i-2]进行比较，找出在该有序序列中
106 // 应插入的位置，将R[i-1]插入，原位置上的元素R[i-1]均顺序后移一位。将上述过程
107 // 从i=1到i=n-1执行n-1趟，就完成了这个序列的所有元素的排序。
108 //
109 ////////////////////////////////////////////////////////////////////////////////
110
111 void InsertSort( int nArr[], int nLength )
112 {
113 int i, j, nCurVal;
114
115 for ( i = 1; i < nLength; i++ )
116 {
117 nCurVal = nArr[i];
118 j = i - 1; // j指向有序序列的最后一个元素
119
120 while ( ( j >= 0 ) && ( nCurVal < nArr[j] ) )
121 {
122 nArr[j + 1] = nArr[j]; // 后移一位
123 j--;
124 }
125
126 nArr[j + 1] = nCurVal; // 插入当前元素
127 }
128 }
129
130 ////////////////////////////////////////////////////////////////////////////////
131 //
132 // 1.4、快速排序
133 //
134 // 快速排序的基本思想:
135 // 在要排序的n个元素中任取一个元素R(这里取中间元素)，以该元素为基准，将所有
136 // 剩下的n-1元素分为两个子序列，第一个子序列中每个元素均小于或等于R，第二个子序
137 // 列中每个元素均大于R；然后将R放在第一个序列之后及第二个序列之前，使得待排序
138 // 序列成为<子序列1> R <子序列2>的形式，这完成了快速排序的第一趟排序；分别对子
139 // 序列1和子序列2重复上述划分，直到每个子序列中只有一个元素时为止。
140 //
141 ////////////////////////////////////////////////////////////////////////////////
142
143 void Sort( int nArr[], int nLeft, int nRight )
144 {
145 int i = nLeft, j = nRight, x, y;
146
147 x = nArr[( nLeft + nRight ) / 2];
148
149 do
150 {
151 while ( ( nArr[i] < x ) && ( i < nRight ) )
152 {
153 i++;
154 }
155 while ( ( nArr[j] > x ) && ( j > nLeft ) )
156 {
157 j--;
158 }
159
160 if ( i <= j )
161 {
162 y = nArr[i];
163 nArr[i] = nArr[j];
164 nArr[j] = y;
165
166 i++;
167 j--;
168 }
169 }
170 while ( i <= j );
171
172 if ( nLeft < j )
173 {
174 Sort( nArr, nLeft, j );
175 }
176 if ( nRight > i )
177 {
178 Sort( nArr, i, nRight );
179 }
180 }
181
182 void QuickSort( int nArr[], int nLength )
183 {
184 Sort( nArr, 0, nLength - 1 );
185 }
186
187 ////////////////////////////////////////////////////////////////////////////////
188 //
189 // 2、查找
190 //
191 ////////////////////////////////////////////////////////////////////////////////
192
193 ////////////////////////////////////////////////////////////////////////////////
194 //
195 // 2.1、顺序查找
196 //
197 // 顺序查找的基本思想:
198 // 从第一个元素开始，逐个地将元素与给定值X进行比较，若相等，则查找成功；
199 // 若直至最后一个元素都不相等，则查找失败。
200 //
201 ////////////////////////////////////////////////////////////////////////////////
202
203 int Search( int nArr[], int nLength, const int nFindVal )
204 {
205 int nIndex = -1;
206 int i = 0;
207
208 while ( ( i < nLength ) && ( nArr[i] != nFindVal ) )
209 {
210 i++;
211 }
212
213 if ( i != nLength )
214 {
215 nIndex = i;
216 }
217
218 return nIndex;
219 }
220
221 ////////////////////////////////////////////////////////////////////////////////
222 //
223 // 2.1、折半查找
224 //
225 // 折半查找的前提是所有元素是有序的，其基本思想:
226 // 将要查找的x先与中间位置的元素比较，若相等，则查找成功；若x大于该中间位置
227 // 的元素，则在后半部继续进行折半查找，否则在前半部进行折半查找，直到查找到成功
228 // 或失败为止。
229 //
230 ////////////////////////////////////////////////////////////////////////////////
231
232 int HalfSearch( int nArr[], int nLength, const int nFindVal )
233 {
234 int nIndex = -1;
235
236 int nLeft = 0, nRight = nLength - 1;
237 int nMid;
238
239 bool bIsFind = false;
240
241 while ( ( nLeft <= nRight ) && ( !bIsFind ) )
242 {
243 nMid = ( nLeft + nRight ) / 2;
244
245 if ( nFindVal == nArr[nMid] )
246 {
247 bIsFind = true;
248 }
249 else if ( nFindVal > nArr[nMid] )
250 {
251 nLeft = nMid + 1;
252 }
253 else
254 {
255 nRight = nMid - 1;
256 }
257 }
258
259 if ( nRight )
260 {
261 nIndex = nMid;
262 }
263
264 return nIndex;
265 }
266
posted on 2006-09-08 19:28
CoderDream 阅读(452)
评论(0) 编辑 收藏 所属分类:
算法