堆排序法是选择排序法的一种。它的基本思想是,将无序区建成一个大头堆或小头堆。然后交换最顶端元素与最尾端元素,然后通过下虑将交换后的无序区重新修改成可用堆。依次类推,直到将所有元素排序完毕
算法
void percdown(int arr[], int i, int N)
{
int tmp;
int child;
for(tmp = arr[i]; (2*i+1) < N; i=child)
{
child = 2 * i + 1;
if (child != N -1 && arr[child + 1] > arr[child])
child++;
if(tmp < arr[child])
arr[i] = arr[child];
else
break;
}
arr[i] = tmp;
}
void buildheap(int arr[], int N)
{
int i;
for(i = N / 2; i >=0; i++)
percdown(arr[], i, N);
}
void heapsort(int arr[], int N)
{
int i;
buildheap(arr[], N);
for(i=N - 1; i>0; i--)
{
arr[0] = arr[0] ^ arr[i];
arr[i] = arr[0] ^ arr[i];
arr[0] = arr[0] ^ arr[i];
percdown(arr[], 0, N);
}
}
阅读(1541) | 评论(0) | 转发(0) |