堆排序算法(选择排序改进)

首先要理解堆的含义：要么所有节点都不大于其子孩子节点数据，要么都不小于其子孩子节点数据

堆排序的核心思想：就是要满足所有节点都满足上面两点，如何完成，看下面

堆排序的步骤：

1.首先要建成一个大顶堆或者小顶堆，在建的过程中其实就是调整节点的位置，首先要从最后最后一个节点的母亲节点开始，按照堆的含义调整。为什么不是最后一个或者其他？因为要保证完整性和不必要性，所以只需从最后一个的母亲节点开始即可（下面的堆默认存在顺序结构，从索引0开始的，所以有些二叉树的特性请查阅二叉树），直至索引节点为0的节点。调整完成后即成为一个堆，但是这里的数据并没有排序好，所以下一部调整顺序。

2.从最后一个数据开始，与第一个数据进行交换，然后按照堆的含义调整第一个数据。为什么先选择最后一个数据？因为默认情况下，最后一个或者是较大或者是较小，可以满足调整要求。这时就考虑当前所有数据减去最后一个，因为这个已是最大或者是最小，不必再考虑.。直至调整没有任何数据，此时已完成排序。

具体图例不再标识，有此爱好可以参考其他书籍或者网上的介绍，下面看堆排序代码：


代码如下:

int HeapSort(MergeType* L)
{
 int i = 0;
 if (!L->elem)
 {
  return -1;
 }

//创建堆
 for (int i = L->len/2-1; i >= 0; i--)
 {
  HeapAdjust(L, i, L->len-1);
 }

//堆排序
 for (i = L->len-1; i >= 0; i-- )
 {
  swap(L->elem[i], L->elem[0]);
  HeapAdjust(L, 0, i-1);
 }
 return 0; 
}

注意：
1）由于父子节点的关系，for循环第一个数据索引其实是L,len-1，但是其父母节点（i）与 当前节点（p）的关系：p = 2i+1 或者2i+2； 如果存储数据的节点第一个索引不是0而是1，这里p=2i或者p=2i+1，请参看有关书籍的证明，所以当前父母节点：i =（p-1）/ 2 = (L.len-1-1)/2 = L.len/2-1

2）由于再次调整数据的时候是从最后一个数据，所以需要交换数据swap，再进行当前顶点数据也就是第一个数据的堆调整，但是此时调整的对象只是（0~i）这些数据，其他已经排序好，所以不再需要调整

下面看一下调整代码，如下：


代码如下:

int HeapAdjust(MergeType* L, int nPos, int nEnd)
{
 for (int i = nPos*2+1; i < nEnd ; i = 2*i+1)
 {
  if (L->elem[i] <= L->elem[i+1])
  {
   i++;
  }
  if (L->elem[nPos] >= L->elem[i])
  {
   break;
  }
  swap(L->elem[nPos], L->elem[i]);
  nPos = i;
 }
 return 0;
}

这里使用的是在一个层次上是数据直接交换，其实这不是必须的，因为最后才把数据放到最后的位置，所以也可以使用下面的代码，减少复制的次数


代码如下:

int HeapAdjustEx(MergeType* L, int nPos, int nEnd)
{
 int nTempkey = L->elem[nPos];

for (int i = nPos*2+1; i < nEnd ; i = 2*i+1)
 {
  if (L->elem[i] <= L->elem[i+1])//选出最大的子孩子
  {
   i++;
  }
  if (nTempkey >= L->elem[i]) //如果当前节点大于最大子孩子退出
  {
   break;
  }
  L->elem[nPos] = L->elem[i]; //否则进行数据交换
  nPos = i;
 }
 L->elem[nPos] = nTempkey;
 return 0;
}

这里就可以减少较多的复制操作，也就是俗称的移动操作次数;这里for循环的起始节点按照上面的推论，子节点应该为p=2i+1，所以第一个应该为2*nPos+1，对应当前要比较节点的做孩子，右孩子为2*nPos+2，也就是左孩子+1，其他请看注释。
时间复杂度：O（nlogn），分析过程暂略

赞 (0)

相关推荐

  • C# 排序算法之堆排序

    C# 排序算法之堆排序

    一.基本概念 堆:这里是指一种数据结构,而不是我们在C#中提到的用于存储引用类型对象的地方.它可以被当成一棵完全二叉树.  为了将堆用数组来存放,这里对每个节点标上顺序.事实上,我们可以用简单的计算公式得出父节点,左孩子,右孩子的索引: parent(i) = left(i) = 2i right(i)=2i + 1 最大堆和最小堆: 最大堆是指所有父节点的值都大于其孩子节点的堆,即满足以下公式: A[parent[i]]A[i](A是指存放该堆的数组) 最小堆相反. 最大堆和最小堆是堆排序的关

  • python 实现堆排序算法代码

    复制代码 代码如下: #!/usr/bin/python import sys def left_child(node): return node * 2 + 1 def right_child(node): return node * 2 + 2 def parent(node): if (node % 2): return (i - 1) / 2 else: return (i - 2) / 2 def max_heapify(array, i, heap_size): l = left_c

  • 深入理解堆排序及其分析

    深入理解堆排序及其分析

    记得在学习数据结构的时候一味的想用代码实现算法,重视的是写出来的代码有一个正确的输入,然后有一个正确的输出,那么就很满足了.从网上看了许多的代码,看了之后貌似懂了,自己写完之后也正确了,但是不久之后就忘了,因为大脑在回忆的时候,只依稀记得代码中的部分,那么的模糊,根本不能再次写出正确的代码,也许在第一次写的时候是因为参考了别人的代码,看过之后大脑可以进行短暂的高清晰记忆,于是欺骗了我,以为自己写出来的,满足了成就感.可是代码是计算机识别的,而我们更喜欢文字,图像.所以我们在学习算法的时候要注重算

  • 内部排序之堆排序的实现详解

    内部排序之堆排序的实现详解

    堆排序(Heap Sort)只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间.(1)基本概念a)堆:设有n个元素的序列:{k1, k2, ..., kn}对所有的i=1,2,...,(int)(n/2),当满足下面关系:                                                                  ki≤k2i,ki≤k2i+1                                                  或

  • php堆排序（heapsort）练习

    复制代码 代码如下: <?//堆排序应用class heapsort  {    var $a;    function setarray($a)//取得数组      {        $this->a=$a;      }    function runvalue($b,$c)//$a 代表数组,$b代表排序堆,$c代表结束点,      {        while($b<$c)          {            $h1=2*$b;            $h2=(2*$

  • Java实现堆排序(Heapsort)实例代码

    复制代码 代码如下: import java.util.Arrays; public class HeapSort { public static void heapSort(DataWraper[] data){        System.out.println("开始排序");        int arrayLength=data.length;        //循环建堆        for(int i=0;i<arrayLength-1;i++){         

  • 堆排序算法(选择排序改进)

    首先要理解堆的含义:要么所有节点都不大于其子孩子节点数据,要么都不小于其子孩子节点数据 堆排序的核心思想:就是要满足所有节点都满足上面两点,如何完成,看下面 堆排序的步骤: 1.首先要建成一个大顶堆或者小顶堆,在建的过程中其实就是调整节点的位置,首先要从最后最后一个节点的母亲节点开始,按照堆的含义调整.为什么不是最后一个或者其他?因为要保证完整性和不必要性,所以只需从最后一个的母亲节点开始即可(下面的堆默认存在顺序结构,从索引0开始的,所以有些二叉树的特性请查阅二叉树),直至索引节点为0的节点.

  • Java数据结构及算法实例：选择排序 Selection Sort

    /** * 选择排序的思想: * 每次从待排序列中找到最小的元素, * 然后将其放到待排的序列的最左边,直到所有元素有序 * * 选择排序改进了冒泡排序,将交换次数从O(N^2)减少到O(N) * 不过比较次数还是O(N) */ package al; public class SelectSort { public static void main(String[] args) { SelectSort selectSort = new SelectSort(); int[] elements

  • JavaScript算法学习之冒泡排序和选择排序

    JavaScript算法学习之冒泡排序和选择排序

    前言 算法与数据结构构成了程序,数据结构用于实现数据的表示.存储.管理,算法通过使用数据完成一定的业务逻辑与操作,最终实现了程序的功能.因此算法在编程中的重要性是不言而喻的.很多复杂的算法都是借助最基本的算法实现的.本文主要选取经典排序算法中的冒泡排序与选择排序对JavaScript编程实现算法进行简单描述与说明. 程序算法 算法说明 算法(Algorithm)是解决问题的一种策略机制,算法也是有限操作指令的集合.按照算法策略输入符合要求的数据,最终获得解决问题的输出结果.冒泡算法与选择算法主要

  • 排序算法图解之Java选择排序

    目录 1.选择排序简介 2.图解选择排序算法 3.选择排序代码实现 1.选择排序简介 选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾.以此类推,直到全部待排序的数据元素的个数为零.选择排序是不稳定的排序方法. 2.图解选择排序算法 选择排序的基本思想如下: 第一次:从arr[0]~arr[n-1]中选取最小值,

  • C语言排序算法之选择排序(直接选择排序,堆排序)

    C语言排序算法之选择排序(直接选择排序,堆排序)

    目录 前言 一.直接选择排序 1.1 算法思想 1.2 代码实现 1.3 直接选择排序的特征总结 二.堆排序 2.1 什么是堆? 2.2 判断是否是堆 2.3 向下调整算法 2.4 自底向上的建堆方式 2.5 代码实现 2.6 堆排序的特性总结 2.7 堆排序的特性总结 前言 本期为大家带来的是常见排序算法中的选择排序,主要有直接选择排序以及——堆排序(有点难理解),包您一看就会,快来试试吧~ 一.直接选择排序 1.1 算法思想 每一次从待排序的数据元素中选出最小(或最大的)的一个元素,存放在序

  • java数据结构排序算法之树形选择排序详解

    本文实例讲述了java数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序 在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进

  • JavaScript实现的选择排序算法实例分析

    JavaScript实现的选择排序算法实例分析

    本文实例讲述了JavaScript实现的选择排序算法.分享给大家供大家参考,具体如下: 简单选择排序是人们最熟悉的比较方式,其算法思想为:从数组的开头开始,将第一个元素和其他元素进行比较.检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续.这个过程会一直进行,当进行到数组的倒数第二个位置时,所有的数据便完成了排序. 代码如下: <!DOCTYPE html> <html> <head> <meta charset="utf-

  • PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】

    本文实例讲述了PHP四种排序算法实现及效率分析.分享给大家供大家参考,具体如下: PHP的四种基本排序算法为:冒泡排序.插入排序.选择排序和快速排序. 下面是我整理出来的算法代码: 1. 冒泡排序: 思路:对数组进行多轮冒泡,每一轮对数组中的元素两两比较,调整位置,冒出一个最大的数来. //简单版: function bubbleSort($arr) { $n = count($arr); for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮) for($j=0;$j<

  • 10个python3常用排序算法详细说明与实例（快速排序，冒泡排序，桶排序，基数排序，堆排序，希尔排序，归并排序，计数排序）

    我简单的绘制了一下排序算法的分类,蓝色字体的排序算法是我们用python3实现的,也是比较常用的排序算法. Python3常用排序算法 1.Python3冒泡排序--交换类排序 冒泡排序(Bubble Sort)也是一种简单直观的排序算法. 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来. 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 作为最简单的排序算法

  • Java经典算法汇总之选择排序（SelectionSort）

    Java经典算法汇总之选择排序（SelectionSort）

    a)原理:每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕.也就是:每一趟在n-i+1(i=1,2,-n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录.基于此思想的算法主要有简单选择排序.树型选择排序和堆排序.(这里只介绍常用的简单选择排序) b)简单选择排序的基本思想:给定数组:int[]arr={里面n个数据}:第1趟排序,在待排序数据arr[1]~arr[n]中选出最小的数据,将它与arrr[1]交换:第2趟,在待排序数据arr[2]~ar

随机推荐