堆排序

void heapSort(int arr[],int length);
void unitHeapSort(int arr[],int index,int length);
void swap(int arr[],int a,int b);
void printLog(int arr[]);

int main(int argc, char * argv[])
{
    int arr[10] = {1,3,9,8,7,2,6,5,4,};
    heapSort(arr, 9);
    printLog(arr);
}

void heapSort(int arr[],int length){
    //构建大顶堆
    for(int i = length/2-1;i>=0;i--){
        unitHeapSort(arr,i,length);
    }
    
    printLog(arr);
    
    //替换最大值与最小值，然后再重新构建大顶堆
    for(int j = length-1;j>0 ;j--){
        swap(arr, 0, j);
        unitHeapSort(arr, 0, j-1);
        printLog(arr);
    }
}

void unitHeapSort(int arr[],int index,int length){
    int leftIndex = index*2 + 1;
    if(leftIndex>length) return;
    //默认指向左侧
    int maxIndex = leftIndex;
    int rightIndex = leftIndex + 1;
    //如果右侧比左侧大则指向右侧
    if(rightIndex<length&&arr[leftIndex]<arr[rightIndex]){
        maxIndex = rightIndex;
    }
    //如果子节点大于父节点，交换位置
    if(arr[maxIndex]>arr[index]){
        swap(arr,maxIndex,index);
        unitHeapSort(arr, maxIndex, length);
    }
}


void swap(int arr[],int a,int b){
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}


void printLog(int arr[]){
    for (int i =0;i<9; i++) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}

输出：
9 8 6 5 7 2 1 3 4 
8 7 6 5 4 2 1 3 9 
7 5 6 3 4 2 1 8 9 
6 5 2 3 4 1 7 8 9 
5 3 2 1 4 6 7 8 9 
4 3 2 1 5 6 7 8 9 
3 1 2 4 5 6 7 8 9 
2 1 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9