常用排序算法的实现(C语言版)-堆排序
程序员文章站
2024-01-09 21:58:34
...
堆排序:
/** *排序过程中使用到的堆的结构 */ typedef struct heap { int heapSize; int *ap; int apLength; } Heap; /* *调整i位置上的元素,以保持最大堆的性质 */ void maxHeapify(int a[], int i, int hSize) { int l, r, largest; l = 2 * i + 1; r = l + 1; if (l < hSize && a[l] > a[i]) { largest = l; } else { largest = i; } if (r < hSize && a[r] > a[largest]) { largest = r; } if (largest != i) { swap(a, i, largest); maxHeapify(a, largest, hSize); } } /* *构建最大堆 */ Heap buildMaxHeap(int a[], int n) { Heap hp; int i; hp.ap = a; hp.heapSize = n; hp.apLength = n; for (i = n / 2 - 1; i >= 0; i--) { maxHeapify(a, i, n); } return hp; } /* *堆排序算法 */ void heapSort(int a[], int n) { int i; //build max-heap Heap heap = buildMaxHeap(a, n); for (i = n - 1; i > 0 ; i--) { swap(a, i , 0); heap.heapSize--; maxHeapify(a, 0, heap.heapSize); } }