首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    堆排序(HeapSort)之java实现

    堆是一种重要的数据结构,为一棵完全二叉树, 底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1), 如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整。分为最大堆和最小堆,最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点。所谓堆排序就是利用堆这种数据结构来对数组排序,我们使用的是最大堆。处理的思想和冒泡排序,选择排序非常的类似,一层层封顶,只是最大元素的选取使用了最大堆。最大堆的最大元素一定在第0位置,构建好堆之后,交换0位置元素与顶即可。堆排序为原位排序(空间小), 且最好与最坏运行时间是都是O(nlogn)。而且堆排序还是原地算法(in-place algorithm),是渐进最优的比较排序算法。

    02

    JNI之路径初探---5

    qsort是一个C语言的排序函数,这不是我们讨论的重点, jint * (JNICALL *GetIntArrayElements) (JNIEnv *env, jintArray array, jboolean *isCopy); 这个函数的作用是得到一个jni数组元素的指针,jintarray里面的每一个元素都是jint类型,数组的特性就是第一个元素的地址就是它的指针,根据元素类型就可以往下得到所有元素,这个函数的第三元素是一个jboolean类型的指针,它的含义就是说如果我现在在C语言层处理这个数组,它要不要复制,不复制代表处理的是和JAVA同一个内存即数组,这里官方建议填NULL,那么数组排序后,操作的也是同一块内存为什么还要去同步一下呢?这里我打印了一下他们的地址,发现不同,由此可以得出NULL和JNI_TRUE都会复制内存,如果有兴趣的同学可以试一下JNI_FALUSE,这个参数同样还是复制了,而填入JNI_TURE后再同步内存会提示JVM运行时的异常,所以不管是哪一个参数其实都不是操作同一块内存,最后如果要在JAVA层去处理结果一定要同步一下内存。

    01

    扫码

    添加站长 进交流群

    领取专属 10元无门槛券

    手把手带您无忧上云

    扫码加入开发者社群

    相关资讯

    热门标签

    活动推荐

      运营活动

      活动名称
      广告关闭
      领券