最近一段时间对8大排序算法进行了整理，并用C语言进行了简单的实现。
简单选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void selectSort(int a[],int s){
int i,j,t;
for(i=0;i<s;i++)
{
for(j=i+1;j<s;j++)
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
int main(void)
{
int i,a[10]={3,2,5,8,4,7,6,9,0,1};
selectSort(a,10);
for(i=0;i<10;i++)
printf("%3d",a[i]);
}起泡/冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void BubbleSort(int a[],int low,int high)
{
int i,j,flag=1,t;
for(i=high;i>0&&flag;i--)
{
int flag=0;
for(j=0;j<i;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
flag=1;
}
}
}
int main(void)
{
int i,a[10]={3,2,5,8,4,7,6,9,0,1};
BubbleSort(a,0,9);
for(i=0;i<10;i++)
printf("%3d",a[i]);
}插入排序1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void InsertSort(int a[], int n)
{
int i,j;
for(i=1;i<n;i++)
if(a[i]<a[i-1])
{
int temp=a[i];
for(j=i-1;j>=0 && a[j]>temp;j--)
a[j+1]=a[j];
a[j+1]=temp;
}
}
int main(void)
{
int i,a[10]={3,2,5,8,4,7,6,9,0,1};
InsertSort(a,10);
for(i=0;i<10;i++)
printf("%3d",a[i]);
}插入排序2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void insertSort(int a[],int s){
int i,j,k,t;
for(i=1;i<s;i++)
{
j=0;
while(a[j]<a[i]&&(j<i))
j++;
if(i!=j)
{
t=a[i];
for(k=i;k>j;k--)
a[k]=a[k-1];
a[j]=t;
}
}
}
int main(void)
{
int i,a[10]={3,2,5,8,4,7,6,9,0,1};
insertSort(a,10);
for(i=0;i<10;i++)
printf("%3d",a[i]);
}希尔排序1
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
void shellSort(int a[],int n)
{
int j,gap;
for (gap=n/2;gap>0;gap/= 2)
for(j=gap;j<n;j++)
if(a[j]<a[j-gap])
{
int temp=a[j];
int k=j-gap;
while(k>=0 && a[k]>temp)
{
a[k+gap]=a[k];
k-=gap;
}
a[k+gap]=temp;
}
}
int main()
{
int i,a[10]={3,2,5,8,4,7,6,9,0,1};
shellSort(a,10);
for(i=0;i<10;i++)
printf("%3d",a[i]);
}希尔排序2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void ShellSort(int a[],int n){
int d,i,j,temp;
for(d=n/2;d>=1;d/=2){
for(i=d;i<n;i++){
temp=a[i];
for(j=i-d;(j>= 0) && (a[j] >temp);j=j-d){
a[j+d]=a[j];
}
a[j+d]=temp;
}
}
}
int main()
{
int i,a[10]={3,2,5,8,4,7,6,9,0,1};
ShellSort(a,10);
for(i=0;i<10;i++)
printf("%3d",a[i]);
}归并排序（递归实现）
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
int s[10]={3,2,5,8,4,7,6,9,0,1},m[MAX];
void merge(int low,int mid,int high){
int i=low,j=mid+1,k=low;
while(i<=mid&&j<=high)
if(s[i]<s[j])
m[k++]=s[i++];
else
m[k++]=s[j++];
while(i<=mid)
m[k++]=s[i++];
while (j<=high)
m[k++]=s[j++];
for ( i = low; i <=high ; i++)
s[i]=m[i];
}
void mergeSort(int a, int b){
if(a<b){
int mid=(a+b)/2;
mergeSort(a,mid);
mergeSort(mid+1,b);
merge(a,mid,b);
}
}
int main()
{
int i;
mergeSort(0,9);
for(i=0;i<10;i++)
printf("%3d",s[i]);
}快速排序
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
void quicksort(int s[],int l,int r)
{
if(l<r)
{
int i=l,j=r,x=s[l];
while(i<j)
{
while(i<j && s[j]>=x)
j--;
if(i<j)
s[i++]=s[j];
while(i<j && s[i]<x)
i++;
if(i<j)
s[j--]=s[i];
}
s[i]=x;
quicksort(s,l,i-1);
quicksort(s,i+1,r);
}
}
void printlink(int a[],int s2)
{
for(int i=0;i<s2;i++)
printf("%3d",a[i]);
}
int main(void)
{
int a[10]={3,2,5,8,4,7,6,9,0,1};
quicksort(a,0,10);
printlink(a,10);
return 0;
}基数排序
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
int GetNum(int num,int pos)
{
int t=1;
t=num/pow(10,pos-1);
return t%10;
}
void RadixSort(int a[], int s)
{
int *array[10];
for(int i=0;i<10;i++)
{
array[i]=(int *)malloc(sizeof(int) *(s));
array[i][0]=0;
}
for(int pos=1;pos<10;pos++)
{
for(int i=0;i<s;i++)
{
int num=GetNum(a[i],pos);
int sum=++array[num][0];
array[num][sum]=a[i];
}
for(int i=0,j=0;i<10;i++)
{
for(int k=1;k<=array[i][0];k++)
a[j++]=array[i][k];
array[i][0] = 0;
}
}
}
int main()
{
int i,a[10]={3,2,5,8,4,7,6,9,0,1};
RadixSort(a,10);
for(i=0;i<10;i++)
printf("%3d",a[i]);
return 0;
}堆排序
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
void Swap( int *a, int *b )
{
int temp;
temp=*b;
*b=*a;
*a=temp;
}
void HeapAdjust(int a[],int i,int s)
{
int child, temp;
for(temp=a[i];2*i+1<s;i=child)
{
child=2*i+1;
if(child!=s-1 && a[child+1]>a[child])
++child;
if (temp<a[child])
a[i]=a[child];
else
break;
}
a[i]=temp;
}
void HeapSort(int a[], int s)
{
for(int i=s/2-1;i>=0;--i)
{
HeapAdjust(a,i,s);
}
for(int i=s-1;i>0;--i)
{
Swap(&a[0],&a[i]);
HeapAdjust(a,0,i);
}
}
int main()
{
int i,a[10]={3,2,5,8,4,7,6,9,0,1};
HeapSort(a,10);
for(i=0;i<10;i++)
printf("%3d",a[i]);
return 0;
}