子若的本本——C语言

C语言数组排序小结
/c4m0_aQ7@J0
| l)p%vGkU-J0数组排序小结（for beginner) IXPUB技术博客
p$[J Jvqphk
很多朋友是以谭浩强老师编的《c语言教程》作为学习C语言的入门教程的。书中涉及排序问题一般都以“冒泡法”和“选择法”实现。为了扩大视野，增加学习编程的兴趣，我参阅了有关书籍，整理了几种排序法，写出来同大家共勉。（高手们不要笑，这篇文章是写给出学者的，而且我自己也是只菜鸟，虽然内容陈旧，但值得初学者一看）。 IXPUB技术博客R3Ucb.j
让我们先定义一个整型数组a[n],下面用五种方法对其从小到大排序。 IXPUB技术博客#l(Uf'M?7C"E2N
（1）“冒泡法”
,h9[N
l
w%ai:[k0冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码： IXPUB技术博客,h*RYiKw

0D]K ]0i#ic0void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
R6ACk Y6Mn0Uzf0{ IXPUB技术博客5[&J$@1{*T
int i,j,temp; IXPUB技术博客e`EW)V(pFv
for(i=0;i<n-1;i++) IXPUB技术博客LJ:\9F0|I9H}
for(j=i+1;j<n;j++) /*注意循环的上下限*/
y!K@-gxJ0if(a>a[j]) {
~
P'R+[`CrS0temp=a;
1gM%mB(AJN&B8}C0a=a[j]; IXPUB技术博客 YWe+L#E4aJ
a[j]=temp;
J KPn-w&aw(GHW0} IXPUB技术博客c2W(D"X*v8I']
} IXPUB技术博客_,B"ga4q)^
IXPUB技术博客P ]2_? DM
冒泡法原理简单，但其缺点是交换次数多，效率低。 IXPUB技术博客7|8I[#b0c$o-Tg:fw
下面介绍一种源自冒泡法但更有效率的方法“选择法”。 IXPUB技术博客S O C+Z2N'S0A.S

cMU
K%|X2`0（2）“选择法”
@ o)zQ,oDii0选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a,这样就比冒泡法省下许多无用的交换，提高了效率。
x
F({1D9Bo+XO0IXPUB技术博客 |k:q)lQ
void choise(int *a,int n)
5~z+ms[zB0{
l;rH)QS)egj4}L0int i,j,k,temp;
"z*x^-AlaA0for(i=0;i<n-1;i++) {
~{Y)Qf0k=i; /*给记号赋值*/
\X1Z_
B:C9[s)T E ec0for(j=i+1;j<n;j++) IXPUB技术博客[fhg*^P
if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/
"c;S$WG2^0if(i!=k) { /*当k!=i是才交换，否则a即为最小*/ IXPUB技术博客GK/v,U
i9XnP
temp=a;
%j`*|zL$z!F3~@0a=a[k]; IXPUB技术博客qa5z9e'Ib-y9P
a[k]=temp; IXPUB技术博客|0Z-~.r$F#gp
}
!Z#Q~O2h-z0} IXPUB技术博客$C%Je%],vKz.xv;C/_|r
} IXPUB技术博客jz7Y&JnBx1V:S
IXPUB技术博客#M8A:Va?3c
选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。
s-M,C5D_,V}/cl%o0IXPUB技术博客"?2n2_W,F
（3）“快速法” IXPUB技术博客#?']vO6@;hJ
快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。下面分析其代码：
1be#e VP w
O#I)l8o0IXPUB技术博客'| x2_+~&SJ$kO
void quick(int *a,int i,int j) IXPUB技术博客p;@,R%`2m~8m5r$ez
{
"Q$Sn%MS*JZ3\"[0int m,n,temp; IXPUB技术博客w!UE3A._Pc~K
int k;
8C2k,r.Y8p6^0m=i; IXPUB技术博客;vN2Q V!NlZ,N$N
n=j;
|#xG'Hm0k=a[(i+j)/2]; /*选取的参照*/ IXPUB技术博客6thnb m&nK4PsK_
do { IXPUB技术博客n)uEpOp%^!K
while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/ IXPUB技术博客+EN'C d"aDu
while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/
n1L1K"foE%d0if(m<=n) { /*若找到且满足条件，则交换*/ IXPUB技术博客T:[ ^2R:Hh8j
b-v
temp=a[m]; IXPUB技术博客U9?I;bWY
a[m]=a[n];
_d(yCU:Kx7imfN H(L0a[n]=temp;
"sF9_4jm3|%BI1D0m++;
{zI]a$M\0n--;
#ROh J P&Sg0} IXPUB技术博客$s!v0o1l7z
}while(m<=n);
'Z tx%D{0if(m<j) quick(a,m,j); /*运用递归*/ IXPUB技术博客#TLh/i$Q
if(n>i) quick(a,i,n); IXPUB技术博客_5yn#waF$u
} IXPUB技术博客ts&c c%ai v5d!BN
IXPUB技术博客tbCz"KQ(o8OF*zxQ/I
（4）“插入法” IXPUB技术博客0~]F3Nem"I1U
插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。 IXPUB技术博客cwc#L2O6Y
IXPUB技术博客p8I x!fh/tl$\
void insert(int *a,int n)
.U4^!\P7?0{ IXPUB技术博客!?.Jgl2g8I1d
int i,j,temp;
JV?2l7SF0for(i=1;i<n;i++) { IXPUB技术博客%{I?u4l{_2gE;g
temp=a; /*temp为要插入的元素*/ IXPUB技术博客e@Vv[$WX
j=i-1; IXPUB技术博客5k.P(L6I} a#OL
while(j>=0&&temp<a[j]) { /*从a[i-1]开始找比a小的数，同时把数组元素向后移*/
"qPJq
u0a[j+1]=a[j]; IXPUB技术博客0j'pbGb'k y
j--;
"MJt)n-L0}
Y!{5DCc0a[j+1]=temp; /*插入*/
i9GWr.~H$[8v6rm0}
b#q%]lrP%AR$qKu0}
$]7H8|/X,t {w0IXPUB技术博客 l#eW[vP(es
X*C
（5）“shell法” IXPUB技术博客JgBpJdQ4uK
shell法是一个叫 shell 的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序，再缩小k值（一般取其一半），再排序，直到k=1时完成排序。下面让我们来分析其代码： IXPUB技术博客/lcY Z$bm
IXPUB技术博客|A&V&p(r"E
void shell(int *a,int n) IXPUB技术博客c+q5Q7s ~ a\k MWe
{ IXPUB技术博客-}M~/t7|:]d
R|
int i,j,k,x; IXPUB技术博客+a0F
L(d/R*i
k=n/2; /*间距值*/ IXPUB技术博客6nu4S2J0x(a
while(k>=1) {
FuA]2g)\]6^t:[0for(i=k;i<n;i++) {
2^v8nX:M0x=a;
@!eV`:M"gdC0j=i-k;
HekFCu0while(j>=0&&x<a[j]) { IXPUB技术博客4UhL)tBm6m
a[j+k]=a[j];
1q Z|-E~Ej$X0j-=k;
.^A zb;C6iv_0} IXPUB技术博客}Ob?-RaEM
a[j+k]=x;
9`AdbV0} IXPUB技术博客kT
\4J3s#|*[
k/=2; /*缩小间距值*/ IXPUB技术博客y[x7C p m![^4I
} IXPUB技术博客6s(hM7X5k
} IXPUB技术博客Twk0~"FKl
IXPUB技术博客Hbx$s%w)D
上面我们已经对几种排序法作了介绍，现在让我们写个主函数检验一下。 IXPUB技术博客;N@,u0G-wa
IXPUB技术博客B%r"u [`(Y2~'fc Q
#include<stdio.h> IXPUB技术博客7{_c*M:A0W-eUM7?
IXPUB技术博客X
@/g]^I
/*别偷懒，下面的"..."代表函数体，自己加上去哦！*/
$t{"hnAP+w7s)F1P0void bubble(int *a,int n)
l j~uG7k]g3A9f'[0{
u y
I#|l0... IXPUB技术博客I.P#Z'a {u TV
} IXPUB技术博客9B9rG}&|:@ojH3}
void choise(int *a,int n) IXPUB技术博客u/L|-S Y7I
{
!V E}'lR.n;HR^$V0... IXPUB技术博客;B;oi.y1H4|F$D _6k
}
M8I g7uh(fzX9J0void quick(int *a,int i,int j) IXPUB技术博客5t O,R ^"G:O4U
{
,S kjX7[&Nk.JK0K0...
WKMt$\:Q*rRv0}
RBM|"HG0void insert(int *a,int n) IXPUB技术博客;l*Kw$}{
{
%n zm*YTGs]f0... IXPUB技术博客qbTfKK\?,}!@&m
} IXPUB技术博客f|wY-^Ck#t'ze
void shell(int *a,int n) IXPUB技术博客Vz.TrEPr
Y
{
zp5Wp slHU0... IXPUB技术博客O$Y6zA4q&bH1T }"`
}
$y;P7?4Xvd9YN(Q!p0
!N3M0dO#Z'U0/*为了打印方便，我们写一个print吧。*/
y"Y;YJ e
{0K0void print(int *a,int n) IXPUB技术博客foo\.Ei#E(Bu/iO
{ IXPUB技术博客&Jv-f*l9Y
i.n$Nn7Z
int i;
g M0^$j#Ll0for(i=0;i<n;i++)
;~?0JY.Y2{\@|.w0printf("%5d",a);
NAD!`2g7F{0printf("\n");
Zc U2g?0}
8x&Tw9d8T:{0IXPUB技术博客(u
Qg4LbE9Cpk
main() IXPUB技术博客%HlkH{"@8r'W
{ /*为了公平，我们给每个函数定义一个相同数组*/ IXPUB技术博客_;L-Q$s.aWkJu&O~F
int a1[]={13,0,5,8,1,7,21,50,9,2};
3M_T2J[F(Q0int a2[]={13,0,5,8,1,7,21,50,9,2}; IXPUB技术博客(T5w&\+Cx-|l#`
int a3[]={13,0,5,8,1,7,21,50,9,2};
3@6kbDjD/s[0int a4[]={13,0,5,8,1,7,21,50,9,2};
/GTu)d L2oG P0int a5[]={13,0,5,8,1,7,21,50,9,2}; IXPUB技术博客:Y3^eWR H[

JhS r2n*N7|H0printf("the original list:");
G}U1u4Ls7pn;BP4i,c0print(a1,10);
1Z(c6C;A A(X.y0printf("according to bubble:"); IXPUB技术博客'~OJs\ Dx
bubble(a1,10); IXPUB技术博客{V"O qZ4pw6km
print(a1,10); IXPUB技术博客*z0XO:vRxS9M
printf("according to choise:"); IXPUB技术博客|F$_Q^T8iZ
choise(a2,10); IXPUB技术博客@n9c:s
`v:@
print(a2,10);
OSK H|ft0printf("according to quick:");

r"A1Hqb ?7Uq0quick(a3,0,9); IXPUB技术博客4Bk'o4D)f#Xx?]`
print(a3,10);
q&R9HIn,QjLf!F0printf("according to insert:"); IXPUB技术博客1M|$D ]r rB"i
insert(a4,10);
H'T$k\t0print(a4,10);
A V `zVB8Z0printf("according to shell:");
0oHG!S
r&L"s'F|P0shell(a5,10);
h/j&\.R R.hA*}0print(a5,10);
Q2o$[4@%w0}