算法設(shè)計(jì)與分析作業(yè)

作業(yè)一：給一個(gè)數(shù)組，用冒泡排序、選擇排序、合并排序與快速排序四種方法

實(shí)現(xiàn)過(guò)程且比較，并把排序時(shí)間顯示出來(lái)。

冒泡排序：

原理：

將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上

浮。在冒泡排序算法中我們要對(duì)這個(gè)“氣泡”序列處理若干遍。所謂一遍處理，就

是自底向上檢查一遍這個(gè)序列，并時(shí)刻注意兩個(gè)相鄰的元素的順序是否正確。如

果發(fā)現(xiàn)兩個(gè)相鄰元素的順序不對(duì)，即“輕”的元素在下面，就交換它們的位置。

代碼：

packagemaopao;

publicclassmaopao(

publicvoidpaixu(){

intarray[]={1,3,-2,0,8,7,-1,13,63,-20,120};

longstart=System.wori/ne();〃開(kāi)始時(shí)間

for(inti=0;i<array.length;i++){

for(intj=i+1;j<array.length;j++){

if(array[i]<array[j]){

inttempt=array[i];

array[i]=array[j];

array[j]=tempt;

)

}

)

for(inti=0;i<array.length;i++){

System.out.println(""+array[i]+"");

)

longend=System〃結(jié)束時(shí)間

System,out.printIn("所花費(fèi)的時(shí)間為:"+(end-start)+"納秒”)；〃運(yùn)行時(shí)間

)

publicstaticvoidmain(String[]args){

maopaom=newmaopao();

m.paixu();

)

}

運(yùn)行結(jié)果:

:Problems@Javadoc圖聲明日控制臺(tái)漢

止〉maopao[Java，主用是國(guó)C:\ProgramFiles\Java\jrel.8.060\bin\javaw.

120

63

13

8

7

3

1

0

-1

-2

-20

斫花費(fèi)的時(shí)冏為：714420比個(gè)

選擇排序：

原理：

對(duì)待排序的記錄序列進(jìn)行n-1遍的處理，第i遍處理是將L[i..n]中最小者與

L[i]交換位置。這樣，經(jīng)過(guò)i遍處理之后，前i個(gè)記錄的位置已經(jīng)是正確的。

代碼：

packagexuanze;

publicclassxuanze(

publicstaticvoidmain(String[]args){

int[]arr={l,3,-2,0,8,7,-1,13,63,-20,120};

inttemp=0;

intmin=0;

longstart=System.nanoTime();

for(inti=0;i<am.length-l;i++){

min=i;

for(intj=i+l;j<arr.length;j++){

if(arr[min]>arr[j])

min=j;

}

if(min!=i){

temp=arr[min];

arr[min]=arr[i];

arr[i]=temp;

}

}

System.out.println("排序后的數(shù)組為：

for(inti=0;i<arr.length;i++){

System.out.println(arr[i]+"");

)

longend=System.nanoTime();

System.out.printin("所花費(fèi)的時(shí)間為：”+(end-start)+"納秒");

)

)

運(yùn)行結(jié)果：

VMM1ILA.___nrJ/\.

4

Problems@Javadoc艮聲明且控制臺(tái)區(qū)，X笈|x/E

xuanze[JavaC:\ProgramFiles\Java\jrel,8.060\bin\javaw.exe(2015^

舞子舌的女公力：

?20

-2

-1

0

1

3

7

8

13

63

120

年花費(fèi)約廿旬為：873530比號(hào)

合并排序：

原理：

是指將若干個(gè)已排序的子文件合并成一個(gè)有序的文件。

代碼：

packagehebing;

importjava.util.Arrays;

publicclasshebing

{

privatestaticvoidmergeSort(int[]array,intstart,intend,int[]

tempArray)

{

if(end<=start)

{

return;

)

intmiddle=(start+end)/2;

mergeSort(array,start,middle,tempArray);

mergeSort(array,middle+1,end,tempArray);

intk=0,leftindex=0,rightindex=end-start;

System.arraycopy(array,start,tempArray,0,middle-start+1);

for(inti=0;i<end-middle;i++)

{

tempArray[end-start-i]=array[middle+i+1];

}

while(k<end-start+1)

{

if(tempArrayfrightlndex]>tempArrayfleftlndex])

{

array[k+start]=tempArray[leftIndex++];

}

else

{

array[k+start]=tempArrayfrightlndex--];

}

k++;

}

)

publicstaticvoidmain(String[]args)

{

int[]array=newint[]{1,3,?2,0,8,7,-1,13,63,-20,120};

longstart=System.nanoH/we();

mergeSort(array,0,array.length-1,newint[array.length]);

System.out.printin(Arrays.toString(array));

longend=System.nanoTime();

System.out.printIn("所花費(fèi)的時(shí)間為：”+(end-start)+"納秒");

)

}

■Problems@Javadoc”Y后控制臺(tái)漢涉SB試

hebing[JavaC:\ProgramFiles\Java\jrel.8Q_60\binyavaw.exe(

[-20,-2,-1,0,1,3,7,8,13,63,120]

廂花曼的什何有：540543楞0

快速排序：

原理：

通過(guò)一趟掃描后，使得排序序列的長(zhǎng)度能大幅度地減少。

代碼：

packagekuaisu;

publicclasskuaisu

{

publicstaticvoidmain(String[]args)

(

quicksortqs=newquicksort();

intdata[]={1,3,-2,0,8,7,-1,13,63,-20,120};

longstart=System.nanoTi/we();

qs.data=data;

qs?sort(0,qs.data.length-1);

qs.display();

longend=System.nanoTime();

System.out.println("所花費(fèi)的時(shí)間為：”+(end-start)+"納秒”)；

}

}

classquicksort

{

publicintdata[];

privateintpartition(intsortArray[],intlow,inthight)

(

intkey=sortArray[low];

while(low<hight)

{

while(low<hight&&sortArray[hight]>=key)

hight--;

sortArray[low]=sortArray[hight];

while(low<hight&&sortArray[low]<=key)

low++;

sortArray[hight]=sortArray[low];

}

sortArray[low]=key;

returnlow;

}

publicvoidsort(intlow,inthight)

(

if(low<hight)

{

intresult=partition(data,low,,hight);

sort(low,result-1);