注册 登录
编程论坛 JAVA论坛

插入排序

hllSaturn 发布于 2017-05-25 22:50, 1139 次点击
文件IntList.java包含一个整数列表类的代码,它可以创建一个固定大小的list并添加元素,如果list已经满了将打印出一条信息,文件ListTest.java中创建IntList类的对象,编译运行程序。
编写一个SortedIntList类,从IntList类继承而来。SortedIntList与IntList相似,但它所有的元素都从小到大排列,意味着当你插入一个元素时,它必须被放到合适的位置。具体做法如下:
遍历数组找到新元素应该存放的位置。
将新元素所存放位置之后的元素向后移,然后存放新元素
以上内容应放在add方法中,覆盖父类中的add方法。还需要修改其他方法吗?
修改ListTest.java测试你新撰写的类,创建SortedIntList类的对象并输出,观察所输出的对象是否有序。
排序有问题~~求助

public class SortedIntList extends IntList
{
    //protected int[] list;
    //protected int numElements = 0;
    public SortedIntList(int size)
        {
            super(size);   
        //list = new int[size];
        }
public void add(int value)
{
    if (numElements == list.length-1)
        System.out.println("Can't add, list is full");
        else
        {
        /*for(int i=1;i<list.length;i++)
         {
             int temp=value;
             int j=i-1;
         while (j>=0 && list[j]>temp)
         {
             list[j+1]=list[j];
             j--;
         }
         list[j+1]=temp;
        
         } */
            int i,j,num = value;
            for(i=0;i<list.length;i++)
            for(j=0;j<list.length+1;)
                {
                    if(num<list[i])
                    {
                        list[j] = num;
                        list[j+1] = list[i];
                        j=j+2;                 
                    }
                    else
                        {
                        list[j] = list[i];
                        j++;
                        }
                }
             for(i=0;i<list.length+1;i++)
             for(j=0;j<list.length+1;j++)
                 list[i] = list[j];
                    
        numElements++;
        }
}
public String toString()
{
String returnString = " ";//+numElements;
for (int i=0; i<numElements; i++)

    returnString += list[i] + "\n";

return returnString;
}
}
1 回复
#2
林月儿2017-05-29 09:52
程序代码:
//遍历数组找到新元素应该存放的位置。
//将新元素所存放位置之后的元素向后移,然后存放新元素
public class Test {
    int[] list;
    static int numElements = 0;
    public Test(int size) {
        list = new int[size];
    }
    /**
     * sort by asc
     *
@param value to be added element
     
*/
    public void add(int value) {
         //check if the size of array is full
         if (numElements == list.length) {
             System.out.println("Can't add, list is full");
             return;
         }
         
         // find place where value can be inserted
         int index = -1;
         for (int i = 0; i < numElements - 1; i++) {
             if (list[i] < value && list[i+1] > value) {
                 index = i + 1;
                 break;
             }
         }
         // if value not in middle of array
         if (index < 0) {
             if (value < list[0]) {
                index = 0;
             } else {
                 index = numElements;                          
             }
         }
         
         for (int i = ++numElements - 1; i > index; i--) {
             list[i] = list[i-1];
         }
         list[index] = value;
         
    }
    /**
     * display list
     
*/
    @Override
    public String toString() {
        return java.util.Arrays.toString(list);
    }
    //test
    public static void main(String[] args) {
        Test test = new Test(9);
        java.util.Random rand = new java.util.Random();
        for(int i=0;i<10; i++){
            test.add(rand.nextInt(100));
        }
        System.out.println(test);
    }
}


[此贴子已经被作者于2017-5-29 10:10编辑过]

1