堆排序

HeapSort.c

// 维护堆的性质
void maxHeapify(int *arr,int i,int heapSize) {
    int left = i*2+1;
    int right = i*2+2;
    int largest;
    
    if (left <= heapSize && arr[left] > arr[i]) {
        largest = left;
    } else {
        largest = i;
    }
    
    if (right <= heapSize && arr[right]>arr[largest]) {
        largest = right;
    }
    
    if (largest != i) {
        swap(arr, i, largest);
        maxHeapify(arr, largest, heapSize);
    }
    
}

//建堆
void buildMaxHeap(int *arr, int arrSize) {
    
    for (int i = arrSize/2; i>=1; i--) {
        maxHeapify(arr, i,arrSize);
    }
}

// 堆排序
void heapSort(int *arr, int arrSize) {
    buildMaxHeap(arr, arrSize);
    for (int i = 0; i < 12; i++) {
        NSLog(@"----i:%d,arr[i]:%d",i,arr[i]);
    }
    int heapSize = arrSize;
    for (int i = arrSize-1; i>=1; i--) {
        swap(arr, 1, i);
        heapSize -= 1;
        maxHeapify(arr, i, heapSize);
    }
}