数据结构 选择排序.doc

#include <stdio.h>
#include <stdlib.h>
#include "malloc.h"
#define N 3

void selectsort(int array[],int n)
{
int m=0,s=0;
int i,j,min,temp;
for (i=0; i<n; i++)
{
min= i;
//找到最小的元素，用min保存下标
for (j=i+1; j<n; j++)
{
m++;
if (array[min] > array[j])
{
min=j;
}
}
if (i !=min)
{
s++;
temp=array[min];
array[min]=array[i];
array[i]=temp;
}
}
printf("简单选择排序后结果\n");
for(i=0;i<n;i++)
printf("%5d",array[i]);printf("\n");
printf("比较次数:%d 交换次数%d\n",m,s);
printf("\n");
}

void insert_sort(int a[],int n)
//待排序元素用一个数组a表示，数组有n个元素
{
int i,j,t;
int m=0,s=0;
for ( i=1; i<n; i++) //i表示插入次数，共进行n-1次插入
{
m++;
t=a[i]; //把待排序元素赋给t
j=i-1;
while ((j>=0)&& (t<a[j]))
{
a[j+1]=a[j];
j--; s++;

}
// 顺序比较和移动
a[j+1]=t;
}
printf("简单直接插入排序后结果\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
printf("\n");
printf("比较次数:%d 交换次数%d\n",m,s);
printf("\n");
}

void main()
{
int a[N];
int i,p;
printf("请输入%d个数字\n",N);
for(i=0;i<N;i++)
scanf("%d",&a[i]);
for(i=0;i<N;i++)
printf("%5d",a[i]);
printf("\n");
printf("请输入所要使用的函数：");
do
{
printf("使用直接插入函数请输入：1\n");
printf("使用选择排序的函数排序请输入：2\n");
scanf("%d",&p);
}while(p!=1&&p!=2);

switch(p)
{
case 1:{insert_sort(a,N);break;}
case 2:{selectsort(a,N);break;}
}
}