C语言 最大堆排序

C语言 最大堆排序

#include
using namespace std;

int left(int i){
 return 2*i;
}
int right(int i){
 return 2*i+1;
}
int parent(int i){
 return i/2;
}
void maxHeapify(int *arr, int length, int i){
 if(arr == 0 || i < 0){
  return ;
 }
 int l = left(i);
 int r = right(i);
 int largest = i;
 if(l < length && arr[l] > arr[largest]){
  largest = l;
 }
 if(r < length && arr[r] > arr[largest]){
  largest = r;
 }
 if(largest != i){
  int temp = arr[i];
  arr[i] = arr[largest];
  arr[largest] = temp;
  maxHeapify(arr, length, largest);
 }
}
void buildMaxHeap(int *arr, int length){
 if(arr == 0 || length <= 0){
  return;
 }
 for(int i=length/2-1; i>=0; i--){
  maxHeapify(arr, length, i);
 }
}
void maxHeapSort(int *arr, int length){
 if(arr == 0 || length <= 0){
  return;
 }
 int temp;
 for(int i=length; i>1; i--){
  temp = arr[i-1];
  arr[i-1] = arr[0];
  arr[0] = temp;
  buildMaxHeap(arr, i-1);
 }
}

int main(){
 int arr[7] = {2, 3, 5, 1, 8, 6, 4};
 maxHeapSort(arr, 7);
 for(int i=0; i<7; i++){
  printf("%d\n", arr[i]);
 }
 return 0;
}

最大堆排序 #include using namespace
std;int left(int i){return 2*i;}int right(int i){return 2*i+1;}int
parent(int i){return i/2;}void maxHeapify(int *arr, int
length,…

相关文章