heapsort.cpp

包含8种常用的排序。如快速排序

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream.h>
//#include <algorithm>
//using namespace std;
int E[10000];

void fixHeap(int E[], int heapSize, int root, int K) //调整为大根堆
{
    int left=2*root, right=2*root+1;
    int largerSubHeap;  //堆中值最大的结点的序号

    if(left>heapSize)  //堆中只有一个结点
        E[root]=K;
    else 
	{
        if(left==heapSize) //堆中只有两个结点
            largerSubHeap=left;
        else if(E[left]>E[right])
            largerSubHeap=left;
        else
            largerSubHeap=right;

        if(K>=E[largerSubHeap])
            E[root]=K;
        else 
		{
            E[root]=E[largerSubHeap];
            fixHeap(E,heapSize,largerSubHeap,K);//继续往下查找堆中值最大的结点的序号
        }
    }
    return;
}

void constructHeap(int E[], int root, int N) //初建堆
 {
    int left=2*root,right=2*root+1;          //左，右孩子的序号
    int K;

    if(left<=N||right<=N) 
	{
        constructHeap(E,left,N);
        constructHeap(E,right,N);
        K=E[root];   //用k记录根结点的值
        fixHeap(E,N,root,K);//调整为大根堆
    }
    return;
}

void HeapSort(int E[], int N) 
{
    int heapsize,curMax,K;

    constructHeap(E,1,N);

    for(heapsize=N;heapsize>1;heapsize--) 
	{
		curMax=E[1];   //堆顶为当前堆中值最大的一个结点
        K=E[heapsize]; //当前堆中最后一个结点
		E[heapsize]=curMax;        //将堆顶和堆中最后一个结点交换 
        fixHeap(E,heapsize-1,1,K); //将剩余的结点heapsize-1重新调整为大根堆 

    }
    return;
}

void main() 
{   
	clock_t start=clock();/*程序开始运行的时间*/
    int i,N;

    printf("Please input N:");
    scanf("%d",&N);

    //srand((unsigned)time(NULL));//随时间的不同产生不同的随机数
    for(i=1;i<=N;i++)
	{ E[i]=rand()%N+1; }

    printf("The %d nums is produced automatically:\n",N);
    for(i=1;i<=N;i++)
	{ printf("%10d",E[i]); }

    getch();
    HeapSort(E,N);

    printf("\nThe result after ordered:\n");
    for(i=1;i<N;i++)
	{ printf("%d->",E[i]); }
	printf("%d\n",E[N]);

    clock_t end=clock();/*程序结束运行的时间*/
    cout<<"整个程序运行的时间为:";
    cout<<(end-start)<<"毫秒\n";
    getch();
}