常用排序算法C语言实现及总结
添加：2009-12-27 点击：2006次 编辑：冰枫工作室 字体：【大 中 小】
我们的约定：
1.各排序算法对整形变量进行排序。
2.排序范围从a[1]到a[n]。
3.排序后生成递增序列。
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
/*随机函数*/
int MyRand()
{
return rand()+(unsigned)time(NULL);
}
/*
直接插入排序：将一个记录插入到已排好的有序表里，从而得到一个新的记录数增1的有序表。
时间复杂度：O(n^2)
稳定性：稳定
适用性：基本有序，长度较小
*/
void InsertSort(int *a,int n)
{
int i,j;
for(i=2;i<=n;i++)
{
if(a<a[i-1])
{
a[0]=a;
for(j=i-1;a[0]<a[j];j--)
{
a[j+1]=a[j];
}
a[j+1]=a[0];
}
}
}
/*
希尔排序：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，再对全体记录进行一次直接插入排序。
时间复杂度：O(n^1.5)
稳定性：不稳定
适用性：随机乱序，长度不太大
*/
void ShellSort(int *a,int n)
{
int i,j,k,t;
int *dlta=(int*)malloc(n*sizeof(int));
/*计算增量序列,dlta[k]=2^(t-k+1),其中1<=k<=t<=log(n+1)/log(2)*/
j=2;
t=log(n+1)/log(2);
for(i=t-1;i>=0;i--)
{
dlta=j-1;
j*=2;
}
for(i=0;i<t;i++)
{
printf("%d ",dlta);
for(j=dlta+1;j<=n;j++)
{
if(a[j]<a[j-dlta])
{
a[0]=a[j];
for(k=j-dlta;k>0&&a[0]<a[k];k-=dlta)
{
a[k+dlta]=a[k];
}
a[k+dlta]=a[0];
}
}
}
printf("\n");
free(dlta);
}
/*
起泡排序：关键字较小的记录像水中气泡逐趟向上浮漂，而关键字较大的记录像石块往下沉。
时间复杂度：O(n^2)
稳定性：稳定
适用性：基本有序，长度较小
*/
void BubbleSort(int *a,int n)
{
int i,j,temp;
int change;
for(i=n,change=1;i>1&&change;i--)
{
change=0;
for(j=1;j<i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
change=1;
}
}
}
}
/*
快速排序：通过一趟排序将待排记录分割成两部分，其中某一部分的关键字比另一部分的小。
时间复杂度：O(n*logn)
稳定性：不稳定
适用性：随机乱序，长度较大
*/
void QuickSort(int *a,int low,int high)
{
int low2=low;
int high2=high;
if(low<high)
{
a[0]=a[low];
while(low<high)
{
while(low<high&&a[high]>=a[0])
{
high--;
}
a[low]=a[high];
while(low<high&&a[low]<=a[0])
{
low++;
}
a[high]=a[low];
}
a[low]=a[0];
QuickSort(a,low2,low-1);
QuickSort(a,low+1,high2);
}
}
/*
选择排序：从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换。
时间复杂度：O(n^2)
稳定性：不稳定
适用性：长度较小
*/
void SelectSort(int *a,int n)
{
int i,j,t;
for(i=1;i<n;i++)
{
t=i;
for(j=i+1;j<=n;j++)
{
if(a[t]>a[j])
{
t=j;
}
}
if(t!=i)
{
j=a[t];
a[t]=a;
a=j;
}
}
}
/*
堆排序：在输出堆顶后，将剩余的记录重新建成堆，反复执行。
时间复杂度：O(n*logn)
稳定性：不稳定
适用性：随机乱序，长度较大
*/
void HeapAdjust(int *a,int s,int m)
{
int i,key=a[s];
for(i=2*s;i<=m;i*=2)
{
if(i<m&&a<a[i+1])
{
i++;
}
if(key>=a)
{
break;
}
a[s]=a;
s=i;
}
a[s]=key;
}
void HeapSort(int *a,int n)
{
int i,temp;
for(i=n/2;i>0;i--)
{
HeapAdjust(a,i,n);
}
for(i=n;i>1;i--)
{
temp=a;
a=a[1];
a[1]=temp;
HeapAdjust(a,1,i-1);
}
}
/*用于测试各排序算法*/
int main()
{
int *a,n,i;
n=20;
a=(int*)malloc((n+1)*sizeof(int));
for(i=1;i<=n;i++)
{
a=MyRand()%(n*15)+1;
printf("%d ",a);
}
printf("\n");
/*InsertSort(a,n);
ShellSort(a,n);
BubbleSort(a,n);
QuickSort(a,1,n);
SelectSort(a,n);
HeapSort(a,n);*/
for(i=1;i<=n;i++)
{
printf("%d ",a);
}
printf("\n");
system("pause");
return 0;
}
0%
0%
来源：中国黑客联盟
数据载入中……