数据结构实验二排序算法代码实现.docx

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#defineMAXK10
usingnamespacestd;

intget_int(void);
intcountSort(int*array,intn,intd);
intget_value(inta,intd);
voidradixSort(int*a,intn,intd);
voidquickSort(inta[],int,int);
//选择排序
voidselectionSort(inta[],intn)
{
boolsorted=false;
for(intsize=n;!sorted&&(size>1);size--)
{
intindexOfMax=0;
sorted=true;
for(inti=1;i<size;i++)
if(a[indexOfMax]<=a[i])
indexOfMax=i;
else
sorted=false;
swap(a[indexOfMax],a[size-1]);
for(inti=0;i<n;i++)
cout<<a[i]<<"";
cout<<"\n";
}
}

//冒泡排序
boolbubble(inta[],intn)
{
boolswapped=false;
for(inti=0;i<n-1;i++)
{
if(a[i]>a[i+1])
{
swap(a[i],a[i+1]);
swapped=true;
}
for(intx=0;x<6;x++)
cout<<a[x]<<"";
cout<<"\n";
}
returnswapped;
}

voidbubbleSort(inta[],intn)
{
for(inti=n;i>1&&bubble(a,i);i--);
}

//插入排序
voidinsertionSort(inta[],intn)
{
for(inti=1;i<n;i++)
{
intt=a[i];
intj;
for(j=i-1;j>=0&&t<a[j];j--)
a[j+1]=a[j];
a[j+1]=t;
for(inti=0;i<n;i++)
cout<<a[i]<<"";
cout<<"\n";
}
}

//基数排序
voidradixSort(int*a,intn,intd)
{
for(inti=0;i<=d;i++)
countSort(a,n,i);
}

intcountSort(int*array,intn,intd)
{
intk[MAXK]={0};
int*temp,*b;
inti;
temp=(int*)malloc(sizeof(int)*n);
b=(int*)malloc(sizeof(int)*n);
if(NULL==temp)
return0;
for(i=0;i<n;i++)
b[i]=get_value(array[i],d);
for(i=0;i<n;i++)
k[b[i]]++;//记录与数组下标相等的数值的个数
for(i=1;i<10;i++)
k[i]+=k[i-1];//储存自己数组下标数值在目标数组对应的位置
for(i=n-1;i>=0;i--)
temp[--k[b[i]]]=array[i];//将原数组按大小顺序储存到另一个数组
//显示temp数组
for(i=0;i<n;i++)
printf("%d",temp[i]);
printf("\n");
for(i=0;i<n;i++)
array[i]=temp[i];
free(temp);
free(b);
return1;
}

intget_value(inta,intd)
{
intb=a;
for(;d>0&&a>0;d--)
b/=MAXK;
returnb%MAXK;
}

intget_int(void)
{
intinput;
charch;
while(scanf("%d",&input)!=1)
{
while((ch=getchar())!='\n')
putchar(input);
printf("isnotaninteger.\nPleaseenteranintegervalue,suchas25,-178,or3;\n");
}
returninput;
}

//快速排序
voidquickSort(ints[],intl,intr)
{
if(l<r)
{
inti=l,j=r,x=s[l];
while(i<j)
{
while(i<j&&s