heapsort.cpp

快速排序、堆排序、冒泡排序等各种排序算法

#include "StdAfx.h"
#include ".\heapsort.h"

CHeapSort::CHeapSort(void)
{
}

CHeapSort::~CHeapSort(void)
{
}

void CHeapSort::Sort(int* pData, int nLen)
{
	int k = nLen/2 -1;
	int i;
	int nTemp;

	for(i=k;i>=0;i--){
		this->Sift(pData,i,nLen-1);
	}
	for(i=nLen-1;i>0;i--){
		nTemp = pData[0];
		pData[0] = pData[i];
		pData[i] = nTemp;

		this->Sift(pData,0,i-1);

	}
}

void CHeapSort::Sift(int* pData, int nStart, int nEnd)
{
	int i,j;
	int x = pData[nStart];

	i=nStart;
	j= nStart*2;
	while(j<= nEnd){
		if((j<nEnd)&&(pData[j] > pData[j+1]))
			j++;

		if(x<= pData[j])
			break;
		else{
			pData[i] = pData[j];
			i=j;
			j=j*2;
		}		
	}
	pData[i] = x;
}