void swap(int *arr, int a, int b){//交互两个数的位置 int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } void BuildMaxHeap(int *arr, int i, int n){//建立大顶堆,进行调整 int parent = arr[i], j; for(j = 2 * i; j <= n;j *= 2){ if(j < n && arr[j] < arr[j+1]) j++; if(parent >= arr[j]) break; arr[i] = arr[j]; i = j; } arr[i] = parent; } void BuildMinHeap(int *arr, int i, int n){//建立小顶堆,进行调整 int parent = arr[i], j; for(j = 2 * i; j <= n;j *= 2){ if(j < n && arr[j] > arr[j+1]) j++; if(parent <= arr[j]) break; arr[i] = arr[j]; i = j; } arr[i] = parent; } void HeadSort(int *arr, int n){//堆排序 for(int i = n/2;i >= 1;i--){//建堆 // BuildMaxHeap(arr, i, n);//最大堆 BuildMinHeap(arr, i, n);//最小堆 } for(int i = n;i >= 1;i--)//调整排序 { swap(arr, 1, i); // BuildMaxHeap(arr, 1, i-1);//最大堆 BuildMinHeap(arr, 1, i-1);//最小堆 } }