c语言各种排序算法的实现.doc

....
/NUMPAGES7
在学习算法的过程中，排序算法是很基础的。下面我用C语言实现了5中基础的排序算法：插入排序、选择排序、冒泡排序、并归排序、快速排序。
1.>插入排序插入排序很简单，在《算法导论》中的解释是这样的。插入排序的工作机理与很多人打牌时，整理手上的牌的做法差不多。开始的时候我们的左手是空的。接着我们从桌面上一一的摸牌，并将它放到左手的一个正确的位置上。为了找到这个正确的位置，要将它与左手的牌从右到左地进行比较，无论在什么时候左手的牌都是排好序的。很简单吧,不过当初为了理解这个算法也花了一点时间，下面是C语言对插入排序的一个简单实现：
HYPERLINK"://muyu1993/1015.html"帮助
1
2
3
4
5
6
7
8
9
10
11
12
13//插入排序intinsert_sort(inta[],intsize)
{
inti,j,temp;
for(i=1;i<size;i++){
temp=a[i];
for(j=i-1;j>=0&&temp<a[j];j--)
a[j+1]=a[j];

a[j+1]=temp;
}
return0;
}//endinsert_sort2>.选择排序选择排序的工作原理是这样的，对数据进行遍历，找出最小的元素（升序）作为第一个元素，再在剩下的数中找出最小的作为第二个元素，一直循环下去，最后的你会发现这个数组中的数据已经排好序了。下面是C语言的选择排序的一个简单实现：
HYPERLINK"://muyu1993/1015.html"帮助
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//选择排序intselect_sort(inta[],intsize)
{
inti,j,temp;
for(i=0;i<size;i++){
for(j=i+1;j<size;j++)
if(a[i]>a[j]){
//交换位置temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
return0;
}//endselect_sort3>.冒泡排序冒泡排序是重复交换相邻的两个反序元素。它的工作工作机理我觉得跟选择排序差不多。因为在第一个遍历整个数组交换反序元素之后，数组的第一个元素就已经是整个数组中最小的元素了。下面是C语言实现的一个冒泡排序。
HYPERLINK"://muyu1993/1015.html"帮助
1
2
3
4
5
6
7
8
9
10
11
12//冒泡排序intbubble_sort(intdata[],intsize)
{
inti,j,temp;
for(i=0;i<size;i++)
for(j=size-1;j>i;j--)
if(data[j]<data[j-1]){
temp=data[j];
data[j]=data[j-1];
data[j-1]=temp;
}
}//endbubble_sort4>.并归排序并归排序，你也可以叫它合并排序。它采用了递归的思想，将数据分成两个部分，将这两个部分排好序之后再进行合并，一直重复这个过程，得出最后的结果。可能说的比较抽象，大家看下面的代码。
HYPERLINK"://muyu1993/1015.html"帮助
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55//合并两个已经排好的结果intmerg_result(intdata[],intstart,intmiddle,intend)
{
ints1,s2,
i,i1,i2;
s1=middle-start+1;
s2=end-middle;

i1=i2=0;
//两个临时的数组inttemp1[s1],temp2[s2];
//复制数据前后两个段的数据进临时数组for(i=0;i<s1;i++)
temp1[i]=data[start+i];
for(i=0;i<s2;i++)
temp2[i]=data[middle+1+i];

//开始合并for(i=start;i<s1+s2+start;i++){
if(temp1[i1]<temp2[i2]){
if(i1>=s1)
break;//无法将两个临时数组的最后一个
元素设为无穷大
data[i]=temp1[i1++];
}
else{
if(i2>=s2)
break;
data[i]=temp2[i2++];
}
}
//添加两个循环，将最后的数