sort.c

来自「几种排序算法的C语言实现 用函数实现如下算法： （1） 直接插入排序, 希尔」· C语言 代码 · 共 158 行

#include<conio.h>

#define FALSE 0
#define TURE 1
#define MAXSIZE 100

/* Declaration for functions */
void selectsort(int *list,int index);
/*
void creatheap(int *heap,int root,int index);
*/
void heapsort(int *heap,int index);
void build(int *a,int i,int n);

void main()
{
    int array[MAXSIZE];
    int node;
    int index=0;
    int i;

    clrscr();
    textmode(2);

    printf("Please input the primitive data(Exit for 0):\n");
    scanf("%d",&node);
    while(node!=0)
    {
         array[index]=node;
         scanf("%d",&node);
         index++;
    }

    selectsort(array,index);
    printf("\nThe selectsort result is:\n");
    for(i=0;i<index;i++)
         printf("%d  ",array[i]);

    heapsort(array,index-1);
    printf("\nThe heapsort result is:\n");
    for(i=0;i<index;i++)
         printf("%d  ",array[i]);
    getch();
}

void selectsort(int *list,int index)
{
    int i,j,k;
    int minnode;                                /*to store the smallest node*/
    int indexmin;                               /*to store the index of the smallest node*/
    int temp;

    for(i=0;i<index-1;i++)
    {   
         minnode=32767;                         /*the smallest node currently*/
         indexmin=0;

         for(j=i;j<index;j++)
         {
              if(list[j]<minnode)                /*found the smallest node*/
              {
                   minnode=list[j];              /*leave the smallest node to the variable of minnode*/
                   indexmin=j;
              }
         }
         temp=list[i];
         list[i]=list[indexmin];
         list[indexmin]=temp;

         printf("\n Current sorting result:");    /*print the current result*/
         for(k=0;k<index;k++)
              printf("%d  ",list[k]);
    }
}

/*establish a heap*/
void build(int *a,int i,int n)
{
    int k;
    int j;
    int tmp;

    k=i;
    j=2*k+1;

    while(j<=n)
    {
	 if(j<n && a[j]<a[j+1])
	      j++;
	 if(a[k]>=a[j])
	      break;
	 tmp=a[k];
	 a[k]=a[j];
	 a[j]=tmp;
	 k=j;
	 j=2*j+1;
    }
}

/*go on sorting the heap*/
void heapsort(int *heap,int index)
{
    int i,j,temp; 

    for(i=(index/2);i>=0;i--)              /*change the binary tree into a heap*/
         build(heap,i,index);
/*
         creatheap(heap,i,index);
  */
    printf("\n");
 
    for(i=index-1;i>=0;i--)                /*go on sorting the heap*/
    {
         temp=heap[i+1];
         heap[i+1]=heap[0];
         heap[0]=temp;

         build(heap,i,index);
/*
         creatheap(heap,i,index);
  */
                                              /*establish heap for other nodes*/

         printf("Sorting process:");       /*print the disposing process*/
         for(j=0;j<=index;j++)
              printf("%d  ",heap[j]);
         printf("\n");
    }
}

/*
void creatheap(int *heap,int root,int index)
{
    int i,j;
    int temp;                              /*temporal variable for exchanging*/
    int finish;                            /*to judge whether the heap's establishment has been finished*/

    j=2*root;                              /*subnode's index*/
    temp=heap[root];                       /*temporal variable for root*/
    finish=0;                              /*default heap's establishment is unfinishde*/

    while(j<index-1&&finish==0)
    { 
         if(j<index)                       /*found the largest subnode*/
              if(heap[j]<heap[j+1])
                   j++;

         if(temp>=heap[j])
              finish=1;                    /*finish the heap's establishment*/
         else
         {
              heap[j/2]=heap[j];           /*parent's node equal to the current node*/
              j=2*j;
         }
    }
    heap[j/2]=temp;                        /*parent's equal to the root*/
}