首页 > 代码库 > 排序算法——堆排序
排序算法——堆排序
堆排序是将给定的序列看成完全二叉树的顺序存储结构来进行排序。
在学习堆排序之前,先了解一下完全二叉树的一个性质:
给定一颗完全二叉树bt,采用顺序存储结构来进行存储,那么如何表示父结点与左右孩子结点之间的关系呢?
下面分两种情况:
(a).如果从下标为0的位置开始存储,那么对于下标为i的结点,其左孩子的下标为2i+1,右孩子的下标为2i+2,父结点的下标为(i-1)/2
(b).如果从下标为1的位置开始存储,那么对于下标为i的结点,其左孩子的下标为2i,右孩子的下标为2i+1,父结点的下标为i/2
为了满足我们从下标为0开始存储的习惯,这里采用第一种方式。由此,可以定义堆:给定一个序列K0、K1、...、Kn-1,如果满足Ki ≤ K2i+1且Ki ≤ K2i+2,
则称之为小根堆;如果满足Ki ≥ K2i+1且Ki ≥ K2i+2,则称之为大根堆。
上面所述为堆的基本概念和相关知识,现在我们讨论大根堆的排序。
对于一个大根堆而言,其根结点便是最大元素,选择出最大元素,将其与序列的最后一个元素进行交换,这样最大的元素便成功归位。但是此时堆的结构
遭到了破坏,需要重新调整元素的位置,使其再次满足堆的性质。所以,对于堆排序来说,堆的调整算法是其核心和本质。
堆的调整算法:
#include <stdio.h> #include <stdlib.h> void Adjustment(int A[], int s, int t) { int i, j, temp; i = s; j = 2*i+1; // j为左孩子的下标 temp = A[i]; // 辅助变量temp保存父结点的值 while(j <= t) { if(j < t && A[j] < A[j+1]) j++; // 如果右孩子大于左孩子,则让j保存右孩子的下标 if(temp < A[j]) // 如果父结点的值小于孩子结点的值 { A[i] = A[j]; // 则将让孩子结点交换到父结点的位置 i = j; j = 2*i + 1; } else break; // 满足大根堆的性质,跳出循环 } A[i] = temp; // 将保存的原父结点的值插入到适当的位置 }
在建立初始堆的时候,需要从最后一个非叶子结点开始由后向前进行调整,直到整个序列都满足堆的性质。此时,根结点为最大元素,将根结点与最后一个叶子结点
交换位置,使最大元素归位,但是破坏了堆的结构,因此需要在剩下的n-1个元素调用堆的调整算法进行调整,如此反复,直到元素都有序。
堆排序算法实现如下:
void HeapSort(int A[], int n) { int i, temp; for(i=n/2-1; i>=0; i--) // 从最后一个非叶子结点开始调整,因此i初始为n/2-1 Adjustment(A, i, n-1); // 调用堆的调整算法 for(i=n-1; i>=1; i--) // 进行n-1趟排序 { temp = A[0]; // 辅助变量temp用来保存根结点的值 A[0] = A[i]; // 将根结点值与叶子结点交换 A[i] = temp; Adjustment(A, 0, i-1); // 此时最大元素归位,对剩下的n-1个元素调用堆的调整算法,重新调整为大根堆 } }
堆排序的时间复杂度为O(nlog2n),空间复杂度为O(1),是一种不稳定的排序算法。
排序算法——堆排序