今天复习了下一些常见的排序算法,并用c语言实现了下。代码如下：
#include<stdio.h>
#include<stdlib.h>
#define MAX 65536 /*用于归并排序中的哨兵*/
/*简单插入排序,时间复杂度为o(n2),稳定排序，适合已经排好序的*/
void insertSort(int arr[],int len)
{
int i,j;
int key;
for(i=1;i<len;i++)
{
key=arr[i];
for(j=i-1;j>=0;j--)
{
if(arr[j]>key)
arr[j+1]=arr[j];
else
break;
}
arr[j+1]=key;
}
}
/*选择排序，时间复杂度为o(n2),不稳定排序，适合规模比较小的*/
void selectSort(int arr[],int len)
{
int i,j,temp;
for(i=0;i<len;i++)
{
for(j=i+1;j<len;j++)
{
if(arr[i]>arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
/*冒泡排序，时间复杂度为o(n2),稳定排序，适合规模比较小的*/
void bubbleSort(int arr[],int len)
{
int i,j,temp;
for(i=0;i<len;i++)
{
for(j=0;j<len-i-1;j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
/*合并（归并）排序,时间复杂度为o(nlogn),稳定排序，适合规模比较大的排序*/
void merge(int arr[],int p,int q,int r)
{
int *A,*B;
int n1,n2,i,j,k;
n1=q-p+1;
n2=r-q;
if((A=(int*)malloc((n1+1)*sizeof(int)))==NULL)
{
perror("malloc error");
exit(1);
}
if((B=(int*)malloc((n2+1)*sizeof(int)))==NULL)
{
perror("malloc error");
exit(1);
}
for(i=0;i<n1;i++)
{
A[i]=arr[p+i];
}
A[i]=MAX;
for(i=0;i<n2;i++)
{
B[i]=arr[q+i+1];
}
B[i]=MAX;
i=0;j=0;
for(k=p;k<=r;k++)
{
if(A[i]>B[j])
{
arr[k]=B[j];
j++;
}else{
arr[k]=A[i];
i++;
}
}
}
void mergeSort(int arr[],int begin,int end)
{
int mid;
if(begin<end)
{
mid=(begin+end)/2;
mergeSort(arr,begin,mid);
mergeSort(arr,mid+1,end);
merge(arr,begin,mid,end);
}
}
int main()
{
int a[8]={5,2,4,7,1,3,2,6};
int b[8]={5,2,4,7,1,3,2,6};
int c[8]={5,2,4,7,1,3,2,6};
int d[8]={5,2,4,7,1,3,2,6};
int i;
/*测试插入排序*/
insertSort(a,8);
printf("after 插入排序\n");
for(i=0;i<8;i++)
{
printf("%d ",a[i]);
}
printf("\n");
/*测试选择排序*/
selectSort(b,8);
printf("after 选择排序\n");
for(i=0;i<8;i++)
{
printf("%d ",b[i]);
}
printf("\n");
/*测试冒泡排序*/
bubbleSort(c,8);
printf("after 冒泡排序\n");
for(i=0;i<8;i++)
{
printf("%d ",c[i]);
}
printf("\n");
/*测试归并排序*/
mergeSort(d,0,7);
printf("after 归并排序\n");
for(i=0;i<8;i++)
{
printf("%d ",d[i]);
}
printf("\n");
}