文章给出用C语言实现的选择排序算法的源代码,在Vc++6.0环境中调试通过,并提供下载源码文本。
选择排序的基本思想是每步从待排序的记录中选出关键字最小的记录,顺序存放在已排序的记录序列的后面,直到全部排完。选择排序中主要使用直接选择排序和堆排序。
直接选择排序的过程是:首先在所有记录中选出关键字最小的记录,把它与第1个记录交换,然后在其余的记录内选出关键字最小的记录,与第2个记录交换......依次类推,直到所有记录排完为止。
无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需要做n-i次比较,因此,总的比较次数为n(n-1)/2=O(n^2)。当初始文件为正序时,移动次数为0;文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O(n^2)。直接选择排序是不稳定的。
程序如下:
// select_sort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
void select_sort(int array[],int n)
{
int i,j,t,k;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(array[j]<array[k])k=j; //k存放一轮中的最小数的下标;
t=array[i];
array[i]=array[k];
array[k]=t;
}
}
int main(int argc, char* argv[])
{
int i,k,n;
n=6;
int array[6];
for(i=0;i<n;i++)
{
printf("please input array value: ");
scanf("%d",&k);
array[i]=k;
}
//打印排序前内容
printf("current array value: ");
for(i=0;i<n;i++)
{
printf("%d ",array[i]);
}
printf(" ");
//排序
select_sort(array,n) ;
//打印排序后9内容
printf("sorted array value: ");
for(i=0;i<n;i++)
{
printf("%d ",array[i]);
}
printf(" ");
return 0;
}
文章参考:
http://cyn227.blog.sohu.com/84172397.html
http://www.programfan.com/club/showtxt.asp?id=202195