堆排序

维护堆:

MAX-HEAPIFY(A,i)
  l=LEFT(i)
  r = RIGHT(i)
  if l <= A.heap-size and A[l]>A[i]
      largest = l
  else largest = i
  if r <= A.heap-size and A[r]>A[i]
      largest = r
  if largest <> i
      exchange A[i] with A[largest]
      MAX-HEAPIFY(A,largest)

唯一难理解就是递归结束条件:当是叶子节点或者已经是最大堆的时候就可以结束了.

建堆:

BUILD-MAX-HEAP(A)
    A.heap-size = A.length
    for i = [A.length/2] downto 1
        MAX-HEAPIFY(A,i)

明显A.length/2到n的都是叶子节点,因此不用维护.

堆排序算法:

HEAPSORT(A)
    BUILD-MAX-HEAP(A)
    for i = A.length downto 2
        exchange A[1] with A[i]
        A.heap_size = A.heap_size - 1 
        MAX-HEAPIFY(A,1)

c语言代码:

#include <iostream>
using namespace std;
#define maxn 101;
int heap_size = 0;
int length = 0;
// 维护堆的过程
void maxHeapfity(int A[],int i)
{
    printf("maxHeapfity(A,%d)\n",i);
    for(int i = 0;i<=heap_size-1;i++)
        cout << A[i]<< " ";
    cout << endl;
    int left = 2*i+1;
    int right = 2*(i+1);
    int largest = i;
    if(left < heap_size && A[left]>A[i])
        largest = left;
    if(right < heap_size && A[right]>A[largest])
        largest = right;
    if(largest != i){
        printf("exchange %d with %d\n",A[i],A[largest]);
        int temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        maxHeapfity(A,largest);
    }
}
//建堆的过程
void buildMaxHeap(int *A)
{
    heap_size = length;
    for(int i = (length/2-1);i>=0;i--)
        maxHeapfity(A,i);
}

//排序算法

void heapSort(int *A)
{
    buildMaxHeap(A);
    for(int i = length-1;i>=1;i--){
        printf("the max is %d\n",A[0]);
        int temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        heap_size -= 1;
        maxHeapfity(A,0);
    }
}
int main() {
    int A[] = {0,16,14,10,8,59,1,5};
    length = sizeof(A)/sizeof(int);
    heapSort(A);
    for(int i =0;i<=length-1;i++){
        printf("%d ",A[i]);
    }
    return 0;
}

以1开始的代码:

#include <iostream>
using namespace std;
#define maxn 101;
int heap_size = 0;
int length = 0;
// 维护堆的过程
void maxHeapfity(int A[],int i)
{
    printf("maxHeapfity(A,%d)\n",i);
    for(int i = 1;i<=heap_size;i++)
        cout << A[i]<< " ";
    cout << endl;
    int left = 2*i;
    int right = 2*i+1;
    int largest = i;
    if(left <= heap_size && A[left]>A[i])
        largest = left;
    if(right <= heap_size && A[right]>A[largest])
        largest = right;
    if(largest != i){
        printf("exchange %d with %d\n",A[i],A[largest]);
        int temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        maxHeapfity(A,largest);
    }
}
//建堆的过程
void buildMaxHeap(int *A)
{
    heap_size = length;
    for(int i = length/2;i>=1;i--)
        maxHeapfity(A,i);
}

//排序算法

void heapSort(int *A)
{
    buildMaxHeap(A);
    for(int i = length;i>=2;i--){
        printf("the max is %d\n",A[1]);
        int temp = A[1];
        A[1] = A[i];
        A[i] = temp;
        heap_size -= 1;
        maxHeapfity(A,1);
    }
}
int main() {
    int A[] = {0,16,14,10,8,7,9,3,2,4,1};
    length = 10;
    heapSort(A);
    for(int i =1;i<=length;i++){
        printf("%d ",A[i]);
    }
    return 0;
}