算法的一些小心得

1、插入排序

#include<stdio.h>
void insort(int a[],int n)
{
int i,j;
for(i=2;i<=n;i++)
{
j=i-1;
a[0]=a[i];
while(a[0]<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=a[0];
}
}
void main()
{
int a[11];
int i;
for(i=1;i<=10;i++)
scanf("%d",&a[i]);
insort(a,10);
for(i=1;i<=10;i++)
printf("%d ",a[i]);
}

2、快速排序

#include <stdio.h>
int partions(int l[],int low,int high)
{
int prvotkey=l[low];
l[0]=l[low];
while (low<high)
{
while (low<high&&l[high]>=prvotkey)
--high;
l[low]=l[high];
while (low<high&&l[low]<=prvotkey)
++low;
l[high]=l[low];
}

l[low]=l[0];
return low;
}

void qsort(int l[],int low,int high)
{
int prvotloc;
if(low<high)
{
prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴
qsort(l,low,prvotloc-1); //递归调用排序 由low 到prvotloc-1
qsort(l,prvotloc+1,high); //递归调用排序 由 prvotloc+1到 high
}
}
void quicksort(int l[],int n)
{
qsort(l,1,n); //第一个作为枢轴 ，从第一个排到第n个
}
void main()
{
int a[11]={0,2,32,43,23,45,36,57,14,27,39};
int b,c;
for (b=1;b<11;b++)
printf("%3d",a[b]);
printf("\n");
quicksort(a,11);
for(c=1;c<11;c++)
printf("%3d",a[c]);
}

3、归并排序

int is1[n],is2[n];// 原数组is1，临时空间数组is2，n为个人指定长度
void mergeSort(int a,int b)// 下标，例如数组int is[5]，全部排序的调用为mergeSort(0,4)
{
if(a<b)
{
int mid=(a+b)/2;
mergeSort(a,mid);
mergeSort(mid+1,b);
merge(a,mid,b);
}
}
void merge(int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
while(i<=mid&&j<=high)
if(is1[i]<=is1[j]) // 此处为排序顺序的关键，用小于表示从小到大排序
is2[k++]=is1[i++];
else
is2[k++]=is1[j++];
while(i<=mid)
is2[k++]=is1[i++];
while(j<=high)
is2[k++]=is1[j++];
for(i=low;i<=high;i++)// 写回原数组
is1[i]=is2[i];
}

2楼wkupaochuan昨天 21:09

不错。

1楼aoxiangzhiguanjun昨天 16:47

呵呵，互相学习