數(shù)據(jù)結(jié)構(gòu)之排序算法詳解(含代碼).doc

《數(shù)據(jù)結(jié)構(gòu)之排序算法詳解(含代碼).doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、C/C++版數(shù)據(jù)結(jié)構(gòu)之排序算法??????今天討論下數(shù)據(jù)結(jié)構(gòu)中的排序算法。排序算法的相關(guān)知識：（1）排序的概念：所謂排序就是要整理文件中的記錄，使之按關(guān)鍵字遞增（或遞減）次序排列起來。（2）穩(wěn)定的排序方法：在待排序的文件中，若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的。相反，如果發(fā)生改變，這種排序方法不穩(wěn)定。（3）排序算法的分類（分為5類）：插入排序、選擇排序、交換排序、歸并排序和分配排序。（4）排序算法兩個基本操作：<1>比較關(guān)鍵字的大小。???????

2、??????????????????????????????<2>改變指向記錄的指針或移動記錄本身。具體的排序方法：插入排序<1>插入排序（InsertionSort）的思想：每次將一個待排序的記錄按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子記錄中的適當(dāng)位置，直到全部記錄插入完成為止。<2>常用的插入排序方法有直接插入排序和希爾排序。（1）直接插入排序<1>算法思路：把一個記錄集（如一個數(shù)組）分成兩部分，前半部分是有序區(qū)，后半部分是無序區(qū)；有序區(qū)一開始有一個元素r[0],無序區(qū)一開始是從r[1]到之后的所有元素；然后每次

3、從無序區(qū)按順序取一個元素r[i],拿到有序區(qū)中由后往前進(jìn)行比較，每次比較時，有序區(qū)中比r[i]大的元素就往后移動一位，直到找到小于r[i]的元素，這時r[i]插到小元素的后面，則完成一趟直接插入排序。如此反復(fù)，從無序區(qū)不斷取元素插入到有序區(qū)，直到無序區(qū)為空，則插入算法結(jié)束。<2>算法演示：//直接插入排序：#includeusingnamespacestd;voidInsertSort(intr[],intn);intmain(){intr[]={24,1,56,2,14,58,15,89};I

4、nsertSort(r,8);for(inti=0;i<8;i++){cout<=0;j--){r[j+1]=r[j];}r[j+1]=s;}}復(fù)制代碼（2）折半插入排序<1>算法思路：我們看到在直接插入排序算法中，需要在有序區(qū)查找比r[i]的小的元素，然后插入到這個元素后面，但這里要注意這個元素

5、是從無序區(qū)算第一個比r[i]小的元素。折半插入排序就是在有序區(qū)折半查找這個元素。<2>算法演示：?//折半插入排序#includeusingnamespacestd;voidBinInsertSort(intr[],intn);intmain(){intr[]={53,34,76,23,55,28,63,88,34,66};BinInsertSort(r,10);for(inti=0;i<10;i++){cout<

6、nsertSort(intr[],intn){for(inti=1;i=high+1;j--){r[j+1]=r[j];}r[high+1]=s;//r[high]是要找的元素}}復(fù)制代碼（3）希爾排序（ShellSort）<1>算法思路：把整個記錄近一

7、個步長step(一般取記錄長度的1/2)，分成step個組，再分別對每個級進(jìn)行直接插入排序；然后再把整個記錄近一個新的步長（一般取step/2）分成step/2個組，再分別對每個組進(jìn)行直接插入排序；如此不斷的縮小步長，反復(fù)分組排序，直到步長等于1為此（步長為1則不可能再分組，1是元素之間距離的最小值）。可以看出，希爾排序?qū)嵸|(zhì)是一種分組插入方法。<2>算法演示：?//希爾排序：#includeusingnamespacestd;voidShellSort(intr[],intn);intmain(

8、){intr[]={24,1,56,2,14,58,15,89};ShellSort(r,8);for(inti=0;i<8;i++){cout<=1){for(inti=step;i