目录
首先,排序之前要先建立一个堆来实现排序
由于兄弟之间无大小关系,所以:
实现升序要创建大堆
实现降序要创建小堆
1.利用AdjustUp(向上调整):
从第二个数据(因为第一个数据上面无父节点),也就是下标为1的那个点开始遍历调整数据,只要该节点上面的父节点比该点小,就互换数据(Swap),最后就会建立出一个大堆。
- // 建大堆
- // O(N*logN)
- for (int i = 1; i < n; i++)
- {
- AdjustUp(a, i);
- }
2.利用AdjustDown(向下调整):
从倒数第一个非叶子节点,也就是倒数第一个父节点开始(建成分成许多个分散的大堆),只要该节点上面的父节点比该点小,就互换数据(Swap),最后就会建立出一个大堆。
- // O(N)
- for (int i = (n - 1 - 1) / 2; i >= 0; --i)
- {
- AdjustDown(a, n, i);
- }
这两种方法中,更推荐下面这种,因为时间复杂度稍低,而且下方排序也要用到向下调整接口,这样就节省了一个接口。
通过大堆的顶端元素最大的特性,可以将尾数据和top数据交换(Swap),AdjustDown的参数中传进去的end是个判断点,size--后,就可以将top那个最大的数据保存在尾部,然后利用向上调整的特性,次大的数据又到了top点,再次交换,size--,依次进行下去,最后就将最大,次大,次次大......依次放到了尾部,就排序完成了。
- //0(N*logN)
- int end = n - 1;
- while (end > 0)
- {
- Swap(&a[0], &a[end]);
- AdjustDown(a, end, 0);
- end--;
- }
- void AdjustUp(HPDataType* a, int child)
- {
- int parent = (child - 1) / 2;
- while (child > 0)
- {
- if (a[child] < a[parent])
- {
- Swap(&a[child], &a[parent]);
- child = parent;
- parent = (child - 1) / 2;
- }
- else
- {
- break;
- }
- }
- }
-
- void AdjustDown(int* a, int size, int parent)
- {
- int child = parent * 2 + 1;
-
- while (child < size)
- {
- // 假设左孩子大
- if (child + 1 < size && a[child + 1] > a[child])
- {
- ++child;
- }
- if (a[child] > a[parent])
- {
- Swap(&a[child], &a[parent]);
- parent = child;
- child = parent * 2 + 1;
- }
- else
- {
- break;
- }
- }
- }
- #include
- #include
- #include
- #include
- #include
-
-
- typedef int HPDataType;
-
- void Swap(HPDataType* p1, HPDataType* p2)
- {
- HPDataType tmp = *p1;
- *p1 = *p2;
- *p2 = tmp;
- }
-
- void AdjustUp(HPDataType* a, int child)
- {
- int parent = (child - 1) / 2;
- while (child > 0)
- {
- if (a[child] < a[parent])
- {
- Swap(&a[child], &a[parent]);
- child = parent;
- parent = (child - 1) / 2;
- }
- else
- {
- break;
- }
- }
- }
-
- void AdjustDown(int* a, int size, int parent)
- {
- int child = parent * 2 + 1;
-
- while (child < size)
- {
- // 假设左孩子大
- if (child + 1 < size && a[child + 1] > a[child])
- {
- ++child;
- }
- if (a[child] > a[parent])
- {
- Swap(&a[child], &a[parent]);
- parent = child;
- child = parent * 2 + 1;
- }
- else
- {
- break;
- }
- }
- }
-
- // 升序
- void HeapSort(int* a, int n)
- {
- // 建大堆
- // O(N*logN)
- /*for (int i = 1; i < n; i++)
- {
- AdjustUp(a, i);
- }*/
-
- // O(N)
- for (int i = (n - 1 - 1) / 2; i >= 0; --i)
- {
- AdjustDown(a, n, i);
- }
-
- //0(N*logN)
- int end = n - 1;
- while (end > 0)
- {
- Swap(&a[0], &a[end]);
- AdjustDown(a, end, 0);
- end--;
- }
- }
-
- int main()
- {
- int a[] = { 4, 6, 2, 1, 5, 8, 2, 9 };
- HeapSort(a, sizeof(a)/sizeof(int));
- for (int i = 0; i < sizeof(a)/sizeof(int); i++)
- {
- printf("%d ", a[i]);
- }
- printf("\n");
- return 0;
- }