黑马程序员技术交流社区

标题: 堆排序问题 [打印本页]

---

作者: 文密    时间: 2012-4-8 00:14
标题: 堆排序问题
public class SelectionSort {
        public void straitSelectionSort(double [] sorted){
                int sortedLen= sorted.length;
                for(int j=1;j<sortedLen;j++){
                        int jMin= getMinIndex(sorted,j);
                        exchange(sorted,j,jMin);
                }
        }
        public void exchange(double [] sorted,int i,int j){
                int sortedLen= sorted.length;
                if(i<sortedLen && j<sortedLen && i<j && i>=0 && j>=0){
                        double temp= sorted[i];
                        sorted[i]=sorted[j];
                        sorted[j]=temp;
                }
        }
        public int getMinIndex(double [] sorted, int i){
                int sortedLen= sorted.length;
               
                int minJ=1;
                double min= Double.MAX_VALUE;
                for(int j=i;j<sortedLen;j++){
                        if(sorted[j]<min){
                                min= sorted[j];
                                minJ= j;
                        }
                }
                return minJ;
        }
               
        public void heapAdjust(double [] sorted,int start,int end){
                if(start<end){
                        double temp= sorted[start];
                                                                    
                        for(int j=2*start;j<=end;j *=2){        //如果改为j<end不会报错，但是改为和书上面一样j<=end会报错，这是为什么？：
                                if(j+1<end && sorted[j]-sorted[j+1]>10e-6){
                                        ++j;                       
                                }
                                if(temp<=sorted[j]){
                                        break;
                                }                       
                                sorted[start]=sorted[j];
                                start=j;                       
                        }
                        sorted[start]=temp;
                }
        }       
        public void heapSelectionSort(double [] sorted){
                int sortedLen = sorted.length;
               
                for(int i=sortedLen/2;i>0;i--){
                        heapAdjust(sorted,i,sortedLen);
                }
                for(int i=sortedLen;i>1;--i){                       
                        exchange(sorted,1,i);                       
                        heapAdjust(sorted,1,i-1);                       
                }               
        }
        public static void main(String [] args){
                Random random= new Random(6);
               
                int arraysize=9;
                double [] sorted=new double[arraysize];
                System.out.print("Before Sort:");               
                for(int j=1;j<arraysize;j++){
                        sorted[j]= (int)(random.nextDouble()* 100);
                        System.out.print((int)sorted[j]+" ");
                }       
                System.out.println();
                               
                SelectionSort sorter=new SelectionSort();               
//                sorter.straitSelectionSort(sorted);
                sorter.heapSelectionSort(sorted);
               
                System.out.print("After Sort:");
                for(int j=1;j<sorted.length;j++){
                        System.out.print((int)sorted[j]+" ");
                }       
                System.out.println();
        }
}


代码中的问题： 有时候第2个和第3个顺序不对（原因还没搞明白到底代码哪里有错）

---

作者: 宋蕈    时间: 2012-4-8 09:06
堆排序没那么复杂吧。。
试试我这个，逻辑比较紧。。
public class T_1{
        public static void main(String[] args){
                int[] a={1,4,2,6,3,7,5};
                heapSort(a,a.length);
        }

        public static void createHeap(int[] a,int n,int h){
                int i,j;  
                int flag;
                int temp;
                i=h;        // i 为要建堆的二叉树根结点下标
                j=2*i+1;                // j为i的左孩子结点的下标
                temp=a[i];
                flag=0;
               
                // 沿左右孩子中值较大者重复向下筛选
                while(j<n && flag!=1){       
                       
                        //  寻找左右孩子几点中的较大者，j为其下标
                        if(j<n-1 && a[j]<a[j+1]) j++;

                        if(temp>a[j]){
                                flag=1;
                        }else{
                                a[i]=a[j];
                                i=j;
                                j=2*i+1;
                        }
                }
                a[i]=temp;   // 把最初的a[i] 赋值最后的a[j]
        }

        public static void initCreateHeap(int[] a,int n){
                int i;
                for(i=(n-1)/2;i>=0;i--){
                        createHeap(a,n,i);
                }
        }

        public static void heapSort(int[] a,int n){
                int i;
                int temp;
                initCreateHeap(a,n);  // 初始化创建最大堆
                for(i=n-1;i>0;i--){    // 当前最大堆个数每次递减1
                        temp=a[0];
                        a[0]=a[i];
                        a[i]=temp;
                        createHeap(a,i,0);   // 调整根节点满足最大堆
                }
                for(int x=0;x<a.length;x++){
                        System.out.println(a[x]+" ");
                }
        }
}

---

作者: pray    时间: 2014-4-26 04:52
呵呵,支持一下哈

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2