排序算法概括之堆排序
发布时间:2021-11-18 18:37:32 所属栏目:教程 来源:互联网
导读:一,堆排序介绍 堆是一个优先级队列,对于大顶堆而言,堆顶元素的权值最大。将 待排序的数组 建堆,然后不断地删除堆顶元素,就实现了排序。关于堆,参考:数据结构--堆的实现之深入分析 http://www.linuxidc.com/Linux/2016-05/131796.htm 下面的堆排序算法
一,堆排序介绍 堆是一个优先级队列,对于大顶堆而言,堆顶元素的权值最大。将 待排序的数组 建堆,然后不断地删除堆顶元素,就实现了排序。关于堆,参考:数据结构--堆的实现之深入分析 http://www.linuxidc.com/Linux/2016-05/131796.htm 下面的堆排序算法将数组中的元素从小到大排序,用大顶堆来实现。 二,堆排序算法分析 现给定了一维数组,需要将数组中的元素使用堆排序。首先,得创建一个堆,可以在这个给定的一维数组上建堆。 对N个元素 建堆的时间复杂度为O(N) 堆排序具体的细节实现有两种方式:一种方式是将堆顶元素删除后,放到一个辅助数组中,然后进行堆调整使之成为一个新。继续删除堆顶元素,直至将堆中所有的元素都出堆,此时排序完成。这种方式需要一个额外的辅助空间O(N) 另一种方式是:将每次删除的堆顶元素放到数组的末尾。因为,对于堆的基本操作 delMin/delMax 而言(delMin针对的是小顶堆,delMax针对的是大顶堆,原理一样)是将堆中的最后一个元素替换堆顶元素,然后向下进行堆调整。因此,可以利用这个特点将每次删除的堆顶元素保存在数组末尾,当所有的元素都出堆后,数组就排好序了。这种方式不需要额外的辅助空间,空间复杂度为O(1) 三,堆排序算法实现 public class HeapSort { public static <T extends Comparable<? super T>> void heapSort(T[] arr){ //build heap for(int i = arr.length/2 - 1; i >= 0; i--) percDown(arr, i, arr.length); for(int i = arr.length - 1; i >= 0; i--) { swapReference(arr, 0, i);//delete Max percDown(arr, 0, i);// 从根开始向下堆调整 } } private static <T extends Comparable<? super T>> void swapReference(T[] arr, int from, int to){ T tmp; tmp = arr[from]; arr[from] = arr[to]; arr[to] = tmp; } //求解 i 的左孩子 private static int leftChild(int i){ return 2*i + 1; } /** * * @param arr 存储堆的一维数组 * @param i 从 i 位置开始进行向下堆调整 * @param n 堆中元素的个数(不是数组的长度) */ private static <T extends Comparable<? super T>> void percDown(T[] arr, int i, int n){ int child; T tmp;//保存当前待调整的结点,当找到了合适的位置后,需要将之放入到合适位置,以保持堆序性质 for(tmp = arr[i]; leftChild(i) < n; i = child) { child = leftChild(i); if(child != n-1 && arr[child].compareTo(arr[child+1]) < 0) child++;//右孩子更大 if(tmp.compareTo(arr[child]) < 0) arr[i] = arr[child];//父节点下移 else break;//父节点比左右孩子都大时,不需要再向下移动了 } arr[i] = tmp;//将节点放入合适的位置 } //for test purpose public static void main(String[] args) { Integer[] arr = {31,41,59,26,53,58,97}; heapSort(arr); for (Integer i : arr) { System.out.print(i + " "); } } } 有几个细节地方解释一下: ①在第3行的heapSort方法中,第5-6行是建堆操作,因为数组中的元素是从下标0开始存储的,故最后一个非叶子结点的下标为:arr.length/2 - 1 ②第9-14行是进行堆排序的操作。swapReference方法相当于删除堆顶元素,因为它把堆顶元素交换到数组的末尾去了,此时堆顶元素不再是最大值(大顶堆)。删除了堆顶元素之后,就要进行堆调整以保持堆序性质,故percDown方法 完成向下进行堆调整的功能。 ③在堆调整的过程中,需要求解某个结点的左 右孩子结点的位置。故有一个leftChild方法用来求解左孩子的位置(注意元素是从数组下标0开始存储的) ④percDown方法实现向下的堆调整功能。第37行 tmp 变量 保存当前待调整的结点,当找到了合适的位置后,需要将之放入到合适位置,以保持堆序性质。对于建堆而言,待调整的结点是从 非叶结点 开始,直至根的那些结点。对于删除堆顶元素而言,则总是从堆顶元素起开始调整(待调整的结点是根) ⑤第39行的for循环实现得非常巧妙,首先tmp保存当前待调整的结点 arr[i],然后判断 arr[i] 是否有左孩子,如果有左孩子的话,又在第42行的if语句中判断它是否还有右孩子(child != n-1),然后左右孩子进行比较,child记录下权值大的那个孩子。 ⑥第44-45行的if语句完成的功能是:将权值大的孩子与父结点比较,如果父结点的权值小,则需要将那个较大的孩子上移到父结点的位置(也相当于父结点下移到孩子的位置) 如果父结点的权值大,已经找到了合适的位置了。说明不需要再进行堆调整了,执行else break; ⑦第49行,就待调整的结点入到到合适的位置i处。整个过程并没有用交换操作,而是用的是赋值操作来隐式地实现了交换操作完成的功能,这是一个优化。 四,堆排序算法复杂度分析 对N个元素建堆的时间复杂度为O(N),删除堆顶元素的时间复杂度为O(logN),尽管随着元素的不断删除,堆的调度越来越小,但是总的而言,删除堆所有元素的时间复杂度为O(NlogN) 故堆排序的时间复杂度为O(NlogN),空间复杂度为O(1) 其实,堆排序是一个非常稳定的算法,最坏和平均情况下的时间复杂度都为O(NlogN) 此外,对于堆排序而言,数据的初始顺序对它的复杂度没有影响。不管数组初始时就是有序的还是逆序的,它都会先建堆,变成了堆序的性质。 (编辑:常州站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |