| 发表于：2007-03-14 17:42:53 楼主 |
我昨天发过帖子,但是大家没明白意思, 我今天想知道答案,请大家帮忙看看
import java.io.*;
unsrotlist{
public int[] thelist;
public int used;
private int countera;
private int counterb;
private int counterc;
private int counterd;
/* precondition: length is positive
* postcondition: thelist is created as an empty array of the input length,
* where each slot is initialised to 0.
* best and worst case: o（length) */
public unsortedintlist（)
{}
public unsortedintlist（int length)
{
thelist = new int[length];
used = 0;
for （int i=0; i <length; i++) thelist[i] = 0;
countera=0;
counterb=0;
counterc=0;
counterd=0;
}
public void setcountera（int a){ countera=a; }
public int getcountera（){return countera;}
public void setcounterb（int b){ counterb=b; }
public int getcounterb（){return counterb;}
public void setcounterc（int c){ counterc=c; }
public int getcounterc（){return counterc;}
public void setcounterd（int d){ counterd=d; }
public int getcounterd（){return counterd;}
/* precondition: none new
* postcondition: returns true if thelist is empty, false otherwise
* best and worst case: o（1) */
public boolean isempty（)
{return （used == 0);}
public boolean isfull（)
{return （used == thelist.length);}
)
public boolean additem（int item)
{
boolean hasspaceleft =（used <thelist.length);
if （hasspaceleft)
{
thelist[used] = item;
used++;
}
return hasspaceleft;
}
/* precondition: none new
* postcondition: returns -1 if the item does not apper in the list, and
* i if the item appears for the first time in position i of the array
* best case: o（1) （first item), worse case: o（n) （not there) */
public int finditem（int item)
{
for （int i=0 ; i < used; i++)
{
if （thelist[i]==item)
{return i;}
}
return -1;
}
/* precondition: none new
* postcondition: returns true if item appears in the list and its leftmost
* occurrence has been eliminated, false if it does not appear.
* best and worst case: o（n) */
public boolean deleteitem（int elem)
{
int index=finditem（elem);
boolean found = （index> =0);
if （found)
{
for （int i=index; i <（used-1); i++)
{thelist[i]=thelist[i+1];}
used--;
}
return （found);
}
public string tostring（)
{
string temp = new string（ " ");
for （int i = 0; i <used; i++)
{
temp += thelist[i]+ " ";
}
return temp;
}
public void swap（int one, int two)
{
int temp=thelist[one];
thelist[one]=thelist[two];
thelist[two]=temp;
}
public void bullesort（)throws exception
{ queue theq=new queue（4);
int a=0;
int b=0;
int d=0;
for（int mark = used-1; mark > 0; mark--)
{
for（int i = 0; i < mark ; i++)
{
if （thelist[i]> thelist[i+1])
{
swap（i, i+1);
theq.append（a++);
countera=theq.serve（)+1;
}
theq.append（b++);
counterb=theq.serve（)+1;
}
theq.append（d++);
counterd=theq.serve（)+1;
system.out.println（counterd+ " "+counterb+ " "+counterc+ " "+countera);
}
}
public void selectionsort（) throws exception
{ queue theq=new queue（4);
int a=0;
for （int mark=0; mark <used-1; mark++)
{
int minindex = findmin（mark);
swap（mark, minindex);
theq.append（a++);
countera=theq.serve（)+1;
}
system.out.println（counterd+ " "+counterb+ " "+counterc+ " "+countera);
}
private int findmin（int mark)
{ queue theq1=new queue（4);
int b=0;
int d=0;
int posmin=mark;
try{ for （int i=posmin+1; i <used; i++)
if（thelist[i] <thelist[posmin])
{ posmin=i;
theq1.append（b++);
counterb=theq1.serve（)+1;
}
theq1.append（d++);
counterd=theq1.serve（)+1;
}
catch（exception e){};
return posmin;
}
public void insertionsort（) throws exception {
queue theq=new queue（4);
theq.reset（);
int c1=0;
for（int mark=1;mark <used;mark++)
{
int temp=thelist[mark];
int i=mark-1;
thelist[i]=temp;
while（i> =0&&thelist[i]> temp)
{ thelist[i+1]=thelist[i];
theq.append（i);
counterb+=theq.serve（)+1;
i--;
}
theq.append（c1++);
counterc+=theq.serve（)+1;
}
system.out.println（ counterc+ " "+ counterb+ " "+ counterc+ " "+ countera);
}
/////////////////////////////////////////////////////////
public class termaiting
{
public static void main（string[] arg)
{
try{ unsortedintlist list=new unsortedintlist（5);
list.additem（2);
list.additem（4);
list.additem（1);
list.additem（5);
list.additem（3);
system.out.println（ "iteration ¦ comparisons ¦ copies ¦ swaps-------bubblesort ");
list.bullesort（);
unsortedintlist list2=new unsortedintlist（5);
list2.additem（2);
list2.additem（4);
list2.additem（1);
list2.additem（5);
list2.additem（3);
system.out.println（ "iteration ¦ comparisons ¦ copies ¦ swaps------selectionsort ");
list2.selectionsort（);
unsortedintlist list3=new unsortedintlist（5);
list3.additem（2);
list3.additem（4);
list3.additem（1);
list3.additem（5);
list3.additem（3);
system.out.println（ "iteration ¦ comparisons ¦ copies ¦ swaps------insertionsort ");
list3.insertionsort（);
}
catch（ exception e){};
}
}
/////////////////////////////////////
我还引用了一个queue相信大家都明白
我想得到的结果
///////////////////////////////
iteration ¦ comparisons ¦ copies ¦ swaps-------bubblesort
1 4 0 2
2 7 0 4
3 9 0 4
4 10 0 4
iteration ¦ comparisons ¦ copies ¦ swaps------selectionsort
1 1 0 4
iteration ¦ comparisons ¦ copies ¦ swaps------insertionsort
10 0 10 0
/////////////////////////////
|
|
|
|
|
