从制造到创造
软件工程师成长之路
posts - 292,  comments - 96,  trackbacks - 0
常用算法

  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 阅读(446) 评论(0)  编辑  收藏 所属分类: 算法

只有注册用户登录后才能发表评论。


网站导航:
 

<2006年9月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(9)

我参与的团队

随笔分类(245)

随笔档案(239)

文章分类(3)

文章档案(3)

收藏夹(576)

友情链接

搜索

  •  

积分与排名

  • 积分 - 454027
  • 排名 - 115

最新评论

阅读排行榜

评论排行榜