`
hy036630
  • 浏览: 3956 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

堆排序

J# 
阅读更多

public class HeapSort   
{   
    int [] a = {3,1,5,2,4,9,8,7,6,4};   
    //数组的索引以0开始 ID也是从0开始   
    //父节点的索引   
       
    public int parentID(int childID)   
    {   
        return (childID-1)/2;   
        }   
       
    //左孩子的索引   
    public int leftChildID(int parentID)   
    {   
        return parentID*2+1;   
        }   
     /*
        创建大顶堆,将数组初始为一个大顶堆
     */
    public void creatMaxHeap()   
    {   
        int lastID = a.length-1;   
        for(int i = parentID(lastID); i >= 0 ; i--)   
                {    
             int k=i;   
        while(leftChildID(k) <= lastID)   
        {   
        int j = leftChildID(k);   
                   if(j < lastID)   //如果有两个孩子
    {   
            if(a[j] < a[j+1])   //选大的那个孩子
                  {   
        j++;   
        }   
             }   
          if(a[k] < a[j])   如果父结点比孩子小
                                {   
                                    int temp = a[k];   
                                    a[k] = a[j];   
                                    a[j] = temp;   
                                    k=j;   
                                    }   
                                    else break;                        
                            }   
                }   
    }   
     //调整大顶堆 
    public void maintainHeap(int lastID)   
    {   
        int k=0;   
         while(k <= parentID(lastID))   
            {   
                int j = leftChildID(k);   
                if( j < lastID)   
                {   
                    if(a[j] <= a[j+1])   
                            j++;   
                       
                    }   
                    if( a[k] <a[j] )   
                    {   
                        int temp = a[j];   
                        a[j] = a[k];   
                        a[k] = temp ;   
                        k = j;   
                        }   
                        else break;   
                        }   
    }   
           
    public void heapSort()   
    {   
        creatMaxHeap();   
        int lastID = a.length-1;   
        while(lastID > 0)   
        {   
            int temp = a[lastID];   
            a[lastID] = a[0];   
            a[0] = temp;   
            lastID--;   
            if(lastID > 0)   
                        maintainHeap(lastID);   
               
            }   
           
        }   
       
    public void printA()   
    {   
        for(int i = 0; i< a.length; i++)   
            {   
                System.out.println(a[i]);   
                }   
        }   
    public static void main(String args[])   
    {   
        HeapSort hs = new HeapSort();   
        hs.heapSort();   
        hs.printA();   
        }   
           
  
} 

分享到:
评论

相关推荐

    堆排序算法源代码

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在本场景中,我们关注的是堆排序的源代码,它适用于openSUSE 11.4操作系统,并且是使用GCC version 4.5.1编译器编译的。在这个名为"sort...

    排序算法编程 堆排序 快速排序

    本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...

    堆排序的c++实现代码

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在大顶堆中,父节点的值总是大于或等于其子节点;而在小顶堆中,父节点的值总是小于或等于其子节点。在C++中,我们可以利用STL中的`...

    算法设计实验报告堆排序代码

    【堆排序算法详解】 堆排序是一种高效的比较排序算法,其主要思想是利用堆这种数据结构进行数据的排序。堆是一个近似完全二叉树的结构,同时满足堆的性质:即父节点的键值总是大于或等于(在最大堆中)或小于或等于...

    堆排序 减治法——C++代码

    堆排序是一种基于比较的排序算法,它利用了数据结构中的“堆”这一概念。在计算机科学中,堆通常被理解为一个完全二叉树,其中每个父节点的值都大于或等于(大顶堆)或小于或等于(小顶堆)其子节点的值。堆排序算法...

    学生成绩管理中实现堆排序

    在这个名为“学生成绩管理中实现堆排序”的项目中,我们看到一个C++编写的学生成绩管理系统,它使用了堆排序方法来管理并排序学生的成绩。 首先,让我们详细了解一下堆。堆通常是一个完全二叉树,可以分为最大堆和...

Global site tag (gtag.js) - Google Analytics