废话不多说先上代码
void heapSort(int arr[], int length) {
int *heap = heapBuild(arr, length);
for(int i = 0; i < length; ++i) {
arr[i] = heapPop(heap, length);
}
return;
}
int* heapBuild(int arr[], int length) {
int *heap = (int*)calloc(length + 1, sizeof(int));
int middle = length >> 1;
for(int i = middle; i > 0; --i) {
heapfiy(heap, i, length);
}
return heap;
}
void heapfiy(int *heap, int index, int length) {
int swap = index;
int temp;
while(1) {
if(index * 2 <= length && heap[index * 2] < heap[swap])
swap = index * 2;
if(index * 2 + 1 <= length && heap[index * 2 + 1] < heap[swap])
swap = index * 2 + 1;
if(index == swap)
break;
temp = heap[index];
heap[index] = heap[swap];
heap[swap] = temp;
index = swap;
}
return;
}
int heapPop(int *heap, int *length) {
int result = heap[1];
heap[1] = heap[*length];
(*length)--;
heapfiy(heap, 1, *length);
return result;
}
时间复杂度
O(n * log n)
空间复杂度
O(1) 原地排序,注意我这里写的代码不是原地排序。
稳定排序
不是稳定排序，因为弹出堆顶元素要和最后一个元素互换，保证二叉树的完全性。
算法核心思想
将待排序数组构建为二叉堆，不断弹出堆顶元素。
关于什么是二叉堆我就不详细说了，以后有时间再写。
堆排序的实现
将待排序数组构建成二叉堆
//堆排序
void heapSort(int arr[], int length) {
int *heap = heapBuild(arr, length);
}
//建堆函数
int* heapBuild(int arr[], int length) {
//为了方便计算数的下标 我们申请一个比length大的一的空间
int *heap = (int*)calloc(length + 1, sizeof(int));
//我们只需对非子节点进行堆化；
int middle = length >> 1;
for(int i = middle; i > 0; --i) {
heapfiy(heap, i, length);
}
return heap;
}
//堆化过程
void heapfiy(int *heap, int index, int length) {
int swap = index;
int temp;
while(1) {
//如果左节点小于当前节点就交换
if(index * 2 <= length && heap[index * 2] < heap[swap])
swap = index * 2;
//如果右节点小于当前节点 或 小于右节点且小于当前节点就交换
if(index * 2 + 1 <= length && heap[index * 2 + 1] < heap[swap])
swap = index * 2 + 1;
//终止条件 当前节点大于子节点
if(index == swap)
break;
temp = heap[index];
heap[index] = heap[swap];
heap[swap] = temp;
index = swap;
}
return;
}
弹出对顶元素并赋值
//堆排序
void heapSort(int arr[], int length) {
int *heap = heapBuild(arr, length);
for(int i = 0; i < length; ++i) {
arr[i] = heapPop(heap, length);
}
return;
}
//建堆函数
int* heapBuild(int arr[], int length) {
//为了方便计算数的下标 我们申请一个比length大的一的空间
int *heap = (int*)calloc(length + 1, sizeof(int));
//我们只需对非子节点进行堆化；
int middle = length >> 1;
for(int i = middle; i > 0; --i) {
heapfiy(heap, i, length);
}
return heap;
}
//堆化过程
void heapfiy(int *heap, int index, int length) {
int swap = index;
int temp;
while(1) {
//如果左节点小于当前节点就交换
if(index * 2 <= length && heap[index * 2] < heap[swap])
swap = index * 2;
//如果右节点小于当前节点 或 小于右节点且小于当前节点就交换
if(index * 2 + 1 <= length && heap[index * 2 + 1] < heap[swap])
swap = index * 2 + 1;
//终止条件 当前节点大于子节点
if(index == swap)
break;
temp = heap[index];
heap[index] = heap[swap];
heap[swap] = temp;
index = swap;
}
return;
}
//弹出堆顶元素
int heapPop(int *heap, int *length) {
int result = heap[1];
heap[1] = heap[*length];
(*length)--;
heapfiy(heap, 1, *length);
return result;
}
堆排序到这就结束了，动手写一遍会更容易理解~
堆排序，堆排序你必须理解什么是堆，再谈排序。以后有时间我会写写这类数据结构的。
都看到这了，点个赞再走啊~。
