常用排序算法——C实现

1.1 冒泡排序

[算法描述]

所给的N个数中,先拿第一个数来和第二个比较,然后让较大的一个排在后面(即如果N1>N2,则让N1与N2交换位置),然后又拿第二个数来和第三个数比较,又把较大的一个排在后面,如此往下做下去,直到第N-1个数和第N个数比较完后,最大的那个数就会被升到了最后面来.接下来又照同样的方法来把前N-1个数中最大的数排到第N-1的位置上,做到最后,整一列数都被排好了.不过下面的代码和上面描述的相反,是从后面开始比较的.

[源程序]

方案一:

for (i=1;i<=n-1;i++)

for(j=n;j>=i+1;j--)

if(a[j-1]>a[j]) //降序:a[j-1]<a[j]

{

k="a"[j-1];

a[j-1]=a[j];

a[j]=k;

}

方案二:

for (i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++)

if (a[i]>a[j]) //降序:a[j-1]<a[j]

{

k="a"[i];

a[i]=a[j];

a[j]=k;

}

1.2 选择排序

[算法描述]

第一趟扫描所有数据,选择其中最小的一个与第一个数据互换;第二趟从第二个数据开始向后扫描,选择最小的与第二个数据互换;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程.

[源程序]

for (i=1;i<=n-1;i++)

{

k="i";

for(j=i+1;j<=n;j++)

if (a[j]<a[k]) k="j"; //降序:a[j]>a[k]

x="a"[i];

a[i]=a[k];

a[k]=x;

}

1.3 插入排序

[算法描述]

假设一个有序数组a有n个元素,现在要向a中插入一个元素x并且使数组a仍然有序列.

1.从左至右扫描数组a,记录下第一个大于(或小于)x的元素的下标,记为k;

2.如果k=0则向数组末尾插入x

否则:

(1)将a[k..n]的所有元素向右移动一位;

(2)a[k]:=x;

(3)n:=n+1.

[源程序]

void Insert(struct stack *s, int x)

{

inti,k;

k="0";

for(i=1;i<=s->top;i++)

if (x<s->data[i]) //降序:x>s.data[i]

{

k="i";

break;

}

if(k==0)

{

++s->top;

s->data[s->top]=x;

}

else

{

for (i=s->top;i>=k;i--) s->data[i+1]=s->data[i];

s->data[k]=x;

++s->top;

}

}

1.4 快速排序

[算法描述]

设有一无序数组a有n个元素.

1.以数组a的中点元素为参考值;

2.将中点左边大于(或小于)参考值的与中点右边小于(或大于)参考值的元素互换位置;

3.对中点左边的元素执行快排操作;

4.对中点右边的元素执行快排操作.

[源程序]

void QuickSort(int a[], int l, int r)

{

inti,j,Mid,k;

i="l";

j="r";

Mid="a"[(int)((l+r)/2)];

do

{

while (a[i]<Mid) ++i; //降序:a[i]>mid

while (Mid<a[j]) --j; //降序:mid>a[j]

if (i<=j)

{

k="a"[i];

a[i]=a[j];

a[j]=k;

++i;

--j;

}

} while(i<=j);

if(i<r) QuickSort(a,i,r);

if(l<j) QuickSort(a,l,j);

}

1.5 哈希排序

[算法描述]

首先建立一个很长的数组做Hash表,表中元素类型为布尔型,初始值为False.然后读入数据,把Hash表中下标等于这个数的元素赋值为True.然后:

for (i=1;i<=n;i++) //从小到大

if(Hash[i]) printf("%d ",i);

for (i=n;i>=1;i--) //从大到小

if(Hash[i]) printf("%d ",i);

[源程序]

/* init */

for (i=1;i<=100;i++) hash[i]=0;

/* sort */

for (i=1;i<=10;i++)

{

scanf("%d",&x);

Hash[x]=1;

}

/* output */

for(i=1;i<=100;i++) //从小到大

if(Hash[i]) printf("%d ",i);

for(i=100;i>=1;i--) //从大到小

if(Hash[i]) printf("%d ",i);

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/power721/archive/2009/08/30/4500696.aspx