树形选择排序


题:写出树形选择排序的实现
一般而言,我们不会直接使用树形选择排序到实际工程中。因为这种方法需要额外的存储空间来建树。
但这种排序方法不失为练习逻辑能力的好机会;同时它也是堆排序思想的基础。
请写出树形选择排序的实现。
注意:
1. 树形的表达,未必使用真正的二叉树来表达,完全二叉树的父节点与孩子节点的序号有固定关系。用数组就可以了。
2. 根节点输出后,如何处理?寻找其值来源?很麻烦!可不可以在树的节点中不要存储值,只存待排序数组的元素序号?

源码TNSort.java


package TNSort;

public class TNSort {
    public static int[] Sort(int[] t) {
        int l = t.length;
        int tl = 2*l-1;
        int[] rt = new int[l];
        String[] tri = new String[tl];
        String[] x = new String[l];
        for (int i=0; i<l; i++) {
            x[i] = t[i]+"";
        }
        
        for (int k=0; k<l; k++) {
            for (int i=0; i<l; i++) {
                tri[tl-1-i] = x[l-1-i];
            }
            for (int i=tl-1; i>0; i-=2) {
                tri[i/2-1] = tri[i-1].compareTo(tri[i])<0? tri[i-1]:tri[i];
            }
            for (int i=0; i<l; i++) {
                if (x[i].equals(tri[0])) {
                    x[i] = "null";
                    break;
                }
            }
            rt[k] = Integer.parseInt(tri[0]);
        }
        return rt;
    }
    
    public static void main(String[] args) {
        int[] t = {49,38,65,97,76,13};
        int[] s = Sort(t);
        for (int i=0; i<s.length; i++) {
            System.out.println(s[i]);
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注