堆排序(heap sort)應(yīng)用的是堆數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的排隊(duì)算法
主要是由3部分組成:
max_heapify主要是來(lái)維持max heap的數(shù)據(jù)結(jié)構(gòu)，其算法復(fù)雜度為O(lgn)【應(yīng)用master定理的第二條來(lái)得到】
build_max_heap，從整個(gè)堆數(shù)列長(zhǎng)度length的1/2開(kāi)始到1，進(jìn)行調(diào)用max_heapify函數(shù)得到，其算法復(fù)雜度為O(n)
heap_sort首先是調(diào)用build_max_heap，來(lái)構(gòu)造一大堆，然后再將arr[1]和堆最大長(zhǎng)度進(jìn)行更換，將堆長(zhǎng)度減一，再調(diào)用max_heapify來(lái)完成了排序功能，算法復(fù)雜度為O(nlogn)
主要代碼實(shí)現(xiàn)為:
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstdlib>
#include <time.h>
#include <windows.h>
#define MAXSIZE 100
int arr[MAXSIZE];
using namespace std;
void print(bool flag=true)
{
if(flag)
{
copy(arr,arr+MAXSIZE,ostream_iterator<int>(cout," "));
cout<<endl;
}
}
void merge(int A[],int p,int q,int r)
{
int left = q-p+1;
int right = r-q;
int* L=new int[left];
int* R = new int[right];
int i,j,k;
for(i=0;i<left;i++)
L[i]=A[p+i];
for(j=0;j<right;j++)
R[j]=A[q+j+1];
for(k=0,i=0,j=0;(i<left)&&(j<right);k++)
{
if(L[i]<=R[j])
{
A[p+k]=L[i];
i++;
}
else
{
A[p+k]=R[j];
j++;
}
}
if(i<left)
{
for(;i<left;i++,k++)
A[p+k]=L[i];
}
if(j<right)
{
for(;j<right;j++,k++)
A[p+k]=R[j];
}
delete [] L;
delete [] R;
}
void mergesort(int A[],int p, int r)
{
if(p<r)
{
int q = (p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
/*********************************
/**** Heap Sort Functions
/********************************/
void max_heapify(int i,int size)//size stands for heap size
{
int left = i<<1;
int right = left+1;
//get the largest of the i/left/right
int largest;
if((left<=size)&&(arr[left]>arr[i]))
{
largest = left;
}
else
largest = i;
if((right<=size)&&(arr[right]>arr[largest]))
largest = right;
//exchange the value of i and largest
if(i!=largest)
{
int temp =arr[i];
arr[i]=arr[largest];
arr[largest]=temp;
max_heapify(largest,size);
}
}
void build_max_heap()
{
int size = sizeof(arr)/sizeof(arr[0])-1;
for(int i=size/2;i>0;i--)
max_heapify(i,size);
}
void heapsort()
{
build_max_heap();
int size = sizeof(arr)/sizeof(arr[0])-1;
int heapsize = size;
for(int i=size;i>1;i--)
{
int temp = arr[1];
arr[1]=arr[i];
arr[i]=temp;
heapsize--;
max_heapify(1,heapsize);
}
}
int main(int argc,char* argv[])
{
int size = MAXSIZE;
for(int i=0;i<size;i++)
{
arr[i] = rand()%MAXSIZE;
}
print();
DWORD start = timeGetTime();
//mergesort(arr,0,MAXSIZE-1);
heapsort();
DWORD end = timeGetTime();
print();
cout<<end-start<<endl;
system("pause");
return 0;
}