幾種常見內(nèi)部排序算法比較

第第頁幾種常見內(nèi)部排序算法比較這是在我高校期間學(xué)習(xí)C語言時學(xué)到的幾種常見的內(nèi)部排序算法的。在高校期間,計算機(jī)相關(guān)專業(yè)的同學(xué),只要掌控這幾種排序算法就已經(jīng)足夠了!

常見內(nèi)部排序算法比較

排序算法是數(shù)據(jù)結(jié)構(gòu)學(xué)科經(jīng)典的內(nèi)容，其中內(nèi)部排序現(xiàn)有的算法有許多種，到底各有什么特點(diǎn)呢？本文力圖設(shè)計實(shí)現(xiàn)常用內(nèi)部排序算法并進(jìn)行比較。分別為起泡排序，徑直插入排序，簡約選擇排序，快速排序，堆排序，針對關(guān)鍵字的比較次數(shù)和移動次數(shù)進(jìn)行測試比較。

問題分析和總體設(shè)計

ADTOrderableList

{

數(shù)據(jù)對象：D={ai|ai∈IntegerSet,i=1,2,…,n,n≥0}

數(shù)據(jù)關(guān)系：R1={〈ai-1，ai〉|ai-1,ai∈D,i=1,2,…,n}

基本操作：

InitList(n)

操作結(jié)果：構(gòu)造一個長度為n，元素值依次為1，2，…，n的有序表。Randomizel(d,isInverseOrser)

操作結(jié)果：隨機(jī)打亂

BubbleSort()

操作結(jié)果：進(jìn)行起泡排序

InserSort()

操作結(jié)果：進(jìn)行插入排序

SelectSort()

操作結(jié)果：進(jìn)行選擇排序

QuickSort()

操作結(jié)果：進(jìn)行快速排序

HeapSort()

操作結(jié)果：進(jìn)行堆排序

ListTraverse(visit())

操作結(jié)果：依次對L種的每個元素調(diào)用函數(shù)visit()

}ADTOrderableList

待排序表的元素的關(guān)鍵字為整數(shù).用正序,逆序和不同亂序程度的不同數(shù)據(jù)做測試比較,對關(guān)鍵字的比較次數(shù)和移動次數(shù)(關(guān)鍵字交換計為3次移動)進(jìn)行測試比較.要求顯示提示信息,用戶由鍵盤輸入待排序表的表長(100-1000)和不同測試數(shù)據(jù)的組數(shù)(8-18).每次測試完畢,要求列表現(xiàn)是比較結(jié)果.

要求對結(jié)果進(jìn)行分析.

這是在我高校期間學(xué)習(xí)C語言時學(xué)到的幾種常見的內(nèi)部排序算法的。在高校期間,計算機(jī)相關(guān)專業(yè)的同學(xué),只要掌控這幾種排序算法就已經(jīng)足夠了!

具體設(shè)計

1、起泡排序

算法：核心思想是掃描數(shù)據(jù)清單，查找涌現(xiàn)亂序的兩個相鄰的項(xiàng)目。當(dāng)找到這兩個項(xiàng)目后，交換項(xiàng)目的位置然后繼續(xù)掃描。重復(fù)上面的操作直到全部的項(xiàng)目都按順次排好。

bubblesort(structrecr[],intn)

{

inti,j;

structrecw;

unsignedlongintcompare=0,move=0;

for(i=1;i=n-1;i++)

for(j=n;j=i+1;j--)

{

if(r[j].keyr[j-1].key)

{

w=r[j];

r[j]=r[j-1];

r[j-1]=w;

move=move+3;

}

compare++;

}

printf(\nBubbleSortcompare=%ld,move=%ld\n,compare,move);}

2、徑直插入排序

算法：經(jīng)過i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當(dāng)位置，使得L[1..i]又是排好序的序列。要達(dá)到這個目的，我們可以用順次比較的方法。首先比較L[i]和L[i-1]，假如L[i-1]≤L[i]，那么L[1..i]已排好序，第i遍處理就結(jié)束了；否那么交換L[i]與L[i-1]的位置，繼續(xù)比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得L[j]≤L[j+1]時為止。

insertsort(structrecr[],intn)

{

inti,j;

unsignedlongintcompare=0,move=0;

這是在我高校期間學(xué)習(xí)C語言時學(xué)到的幾種常見的內(nèi)部排序算法的。在高校期間,計算機(jī)相關(guān)專業(yè)的同學(xué),只要掌控這幾種排序算法就已經(jīng)足夠了!

for(i=2;i=n;i++)

{compare++;

r[0]=r[i];

move++;

j=i-1;

while(r[0].key{r[j+1]=r[j];

j--;

move++;

++compare;}

r[j+1]=r[0];

move++;

}

printf(\nInsertSortcompare=%ld,move=%ld\n,compare,move);}

3、簡約選擇排序

算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個數(shù)據(jù)同第一個數(shù)據(jù)交換位置；接下來找第二小的數(shù)據(jù)，再將其同第二個數(shù)據(jù)交換位置，以此類推。

selectsort(structrecr[],intn)

{

unsignedlongintcompare=0,move=0;

inti,j,k;

structrecw;

for(i=1;i=n-1;i++)

{k=i;

for(j=i+1;j=n;j++)

{if(r[j].keyr[k].key){k=j;compare++;}

w=r[i];

r[i]=r[k];

r[k]=w;

move=move+3;

}

}

printf(\nSelectSortcompare=%ld,move=%ld\n,compare,move);}

4、快速排序

這是在我高校期間學(xué)習(xí)C語言時學(xué)到的幾種常見的內(nèi)部排序算法的。在高校期間,計算機(jī)相關(guān)專業(yè)的同學(xué),只要掌控這幾種排序算法就已經(jīng)足夠了!

算法：首先檢查數(shù)據(jù)列表中的數(shù)據(jù)數(shù)，假如小于兩個，那么徑直退出程序。假如有超過兩個以上的數(shù)據(jù)，就選擇一個分割點(diǎn)將數(shù)據(jù)分成兩個部分，小于分割點(diǎn)的數(shù)據(jù)放在一組，其余的放在另一組，然后分別對兩組數(shù)據(jù)排序。通常分割點(diǎn)的數(shù)據(jù)是隨機(jī)選取的。這樣無論你的數(shù)據(jù)是否已被排列過，你所分割成的兩個字列表的大小是差不多的。而只要兩個子列表的大小差不多。

q(structrecr[],ints,intt)

{

inti=s,j=t;

if(st)

{

r[0]=r[s];++a;c++;

do{

while(jir[j].key=r[0].key)

{j--;

++a;}

if(ij)

{r[i]=r[j];

i++;

c++;}

while(ijr[i].key=r[0].key)

{i++;

++a;}

if(ij)

{r[j]=r[i];

j--;

c++;}

}while(ij);

r[i]=r[0];

c++;

q(r,s,j-1);

q(r,j+1,t);

}

}

5.堆排序

基本思想：堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順次存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇最小的元素。

(2)堆的定義:N個元素的序列K1,K2,K3,...,Kn.稱為堆，當(dāng)且僅當(dāng)該序列滿意特性：

這是在我高校期間學(xué)習(xí)C語言時學(xué)到的幾種常見的內(nèi)部排序算法的。在高校期間,計算機(jī)相關(guān)專業(yè)的同學(xué),只要掌控這幾種排序算法就已經(jīng)足夠了!

Ki≤K2iKi≤K2i+1(1≤I≤[N/2])

sift(structrecr[],intl,intm)

{

inti,j;

structrecw;

i=l;j=2*i;

w=r[i];

while(j=m)

{

if(jmr[j].keyr[j+1].key){j++;

}

if(w.keyr[j].key)

{

r[i]=r[j];

i=j;

j=2*i;

}

elsej=m+1;

}

r[i]=w;

}

heapsort(structrecr[],intn)

{

unsignedlongintcompare=-1,move=-1;

structrecw;

inti;

inta;

for(i=n/2;i=1;i--)a=sift(r,i,n);

compare++;

move++;

for(i=n;i=2;i--)

{

w=r[i];

r[i]=r[1];

r[1]=w;

a=sift(r,1,i-1);

compare+=a;

move+=a;

}

}

這是在我高校期間學(xué)習(xí)C語言時學(xué)到的幾種常見的內(nèi)部排序算法的。在高校期間,計算機(jī)相關(guān)專業(yè)的同學(xué),只要掌控這幾種排序算法就已經(jīng)足夠了!

小結(jié)：

1.學(xué)會運(yùn)用隨機(jī)函數(shù)randomize()為數(shù)組賦初值要在頭文件中添加#include。

2．在做此程序之前基本上是在理解了各種排序過程以后完成的。

3.對排序算法的總結(jié)：

(1)假設(shè)n較小(如n≤50)，可采納徑直插入或徑直選擇排序。當(dāng)記錄規(guī)模較小時，徑直插入排序較好；否那么由于徑直選擇移動的記錄數(shù)少于徑直插人，應(yīng)選徑直選擇排序?yàn)橐恕?/p>

(2)假設(shè)文件初始狀態(tài)基本有序(指正序)，那么應(yīng)選用徑直插人、冒泡或隨機(jī)的快速排序?yàn)橐耍?/p>

(3)假設(shè)n較大，那么應(yīng)采納時間繁復(fù)度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。

快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時，快速排序的平均時間最短；堆排序所需的幫助空間少于快速排序，并且不會涌現(xiàn)快速排序可能涌現(xiàn)的最壞狀況。這兩種排序都是不穩(wěn)定的。

這是在我高校期間學(xué)習(xí)C語言時學(xué)到的幾種常見的內(nèi)部排序算法的。在高校期間,計算機(jī)相關(guān)專業(yè)的同學(xué),只要掌控這幾種排序算法就已經(jīng)足夠了!

常見內(nèi)部排序算法比較

排序算法是數(shù)據(jù)結(jié)構(gòu)學(xué)科經(jīng)典的內(nèi)容，其中內(nèi)部排序現(xiàn)有的算法有許多種，到底各有什么特點(diǎn)呢？本文力圖設(shè)計實(shí)現(xiàn)常用內(nèi)部排序算法并進(jìn)行比較。分別為起泡排序，徑直插入排序，簡約選擇排序，快速排序，堆排序，針對關(guān)鍵字的比較次數(shù)和移動次數(shù)進(jìn)行測試比較。

問題分析和總體設(shè)計

ADTOrderableList

{

數(shù)據(jù)對象：D={ai|ai∈IntegerSet,i=1,2,…,n,n≥0}

數(shù)據(jù)關(guān)系：R1={〈ai-1，ai〉|ai-1,ai∈D,i=1,2,…,n}

基本操作：

InitList(n)

操作結(jié)果：構(gòu)造一個長度為n，元素值依次為1，2，…，n的有序表。Randomizel(d,isInverseOrser)

操作結(jié)果：隨機(jī)打亂

BubbleSort()

操作結(jié)果：進(jìn)行起泡排序

InserSort()

操作結(jié)果：進(jìn)行插入排序

SelectSort()

操作結(jié)果：進(jìn)行選擇排序

QuickSort()

操作結(jié)果：進(jìn)行快速排序

HeapSort()

操作結(jié)果：