读取10个整型数据12 63 58 95 41 35 65 0 38 44,然后通过选择排序,堆排序,分别对该组数据进行排序,输出2次有序结果,每个数的输出占3个空格
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string>
typedef int ElemType;
typedef struct {
ElemType *elem; //存储元素的起始地址
int TableLen; //元素个数
}SSTable;
void ST_Init(SSTable &ST,int len)
{
ST.TableLen=len;
ST.elem=(ElemType *) malloc(sizeof (ElemType)*ST.TableLen); //申请一块空间,当数组来使用
}
//打印数组中的元素
void ST_print(SSTable ST)
{
for (int i = 0; i < ST.TableLen; i++) {
printf("%3d",ST.elem[i]);
}
printf("\n");
}
//交换
void swap(ElemType &a,ElemType &b)
{
ElemType tmp;
tmp=a;
a=b;
b=tmp;
}
void SelectSort(ElemType *A,int n)
{
int i,j,min; //min记录最小元素的下标
for (i = 0; i < n-1 ; i++)
{
min=i; //认为i最小
for (j = i+1; j < n; j++) //找到从i开始到最后序列的最小值下标
{
if (A[j]<A[min]) //当某个元素A[j]小于了最小元素
{
min=j; //将下标j赋值给min,min就记录下来最小值的下标
}
}
if (min!=i)
{
//遍历完毕找到最小值的位置后,与A[i]交换,这样最小值被放到了最前面
swap(A[i],A[min]);
}
}
}
//把某个子树调整为大根堆
void AdjustDown1(ElemType A[],int k,int len)
{
int dad=k; //父亲的下标
int son=2*dad+1; //左孩子的下标
while (son<len)
{
if (son+1<len&&A[son]<A[son+1]) //如果左孩子小于右孩子
{
son++; //拿右孩子
}
if (A[son]>A[dad]) //如果孩子大于父亲交换
{
swap(A[son],A[dad]);
dad=son; //son重新作为dad,去判断下面的子树是否符合大根堆
son=2*dad+1; //
} else{
break;
}
}
}
void HeapSort(ElemType A[],int len)
{
int i;
//把堆,调整为大根堆
for (i=len/2-1;i>=0;i--)
{
AdjustDown1(A,i,len);
}
swap(A[0],A[len-1]);//交换根部元素和最后一个元素
for (i = len-1; i>1 ; i--) { //i代表剩余无序数的数组长度
AdjustDown1(A,0,i); //调整剩余元素变为更大堆
swap(A[0],A[i-1]); //交换根部元素和无序数的数组的最后一个元素
}
}
int main() {
SSTable ST;
ST_Init(ST,10); //初始化
ElemType A[10];
int i;
//读取标准输入,读入10个元素
for (i = 0; i<10 ; i++) {
scanf("%d",&A[i]);
}
memcpy(ST.elem,A,sizeof (A));
SelectSort(ST.elem,10); //选择排序
ST_print(ST);
memcpy(ST.elem,A,sizeof (A)); //copy A数组中的元素
HeapSort(ST.elem,10);
ST_print(ST);
return 0;
}