數(shù)據(jù)結(jié)構(gòu)常見問題:12單元16 經(jīng)典排序算法_第1頁
數(shù)據(jù)結(jié)構(gòu)常見問題:12單元16 經(jīng)典排序算法_第2頁
數(shù)據(jù)結(jié)構(gòu)常見問題:12單元16 經(jīng)典排序算法_第3頁
數(shù)據(jù)結(jié)構(gòu)常見問題:12單元16 經(jīng)典排序算法_第4頁
數(shù)據(jù)結(jié)構(gòu)常見問題:12單元16 經(jīng)典排序算法_第5頁
已閱讀5頁,還剩2頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、數(shù)據(jù)結(jié)構(gòu)課程常見問題 -單元16 排序算法1經(jīng)典排序算法解析:希爾排序二分插入法直接插入法帶哨兵的直接排序法冒泡排序選擇排序快速排序堆排序2希爾排序希爾(Shell)排序法(又稱宿小增量排序,是1959年由D.L.Shell提出來的)/* Shell 排序法 */#include void sort(int v,int n) int gap,i,j,temp; for(gap=n/2;gap0;gap /= 2) /* 設(shè)置排序的步長,步長gap每次減半,直到減到1 */ for(i=gap;i= 0) & (vj vj+gap);j -= gap ) /* 比較相距gap遠的兩個元素的大小,

2、根據(jù)排序方向決定如何調(diào)換 */ temp=vj; vj=vj+gap; vj+gap=temp; 3二分插入法/* 二分插入法 */void HalfInsertSort(int a, int len) int i, j,temp; int low, high, mid; for (i=1; ilen; i+) temp = ai;/* 保存但前元素 */ low = 0; high = i-1; while (low temp) /* 如果中間元素比但前元素大,當(dāng)前元素要插入到中間元素的左側(cè) */ high = mid-1; else /* 如果中間元素比當(dāng)前元素小,但前元素要插入到中間元素

3、的右側(cè) */ low = mid+1; /* 找到當(dāng)前元素的位置,在low和high之間 */ for (j=i-1; jhigh; j-)/* 元素后移 */ aj+1 = aj; ahigh+1 = temp; /* 插入 */ 3直接插入法/*直接插入法*/void InsertionSort(int input,int len) int i,j,temp; for (i = 1; i -1&inputj temp ; j-) /* 從當(dāng)前元素的上一個元素開始查找合適的位置 */ inputj + 1 = inputj; /* 一邊找一邊移動元素 */ inputj = temp; 4帶

4、哨兵的直接排序法/* * 帶哨兵的直接插入排序,數(shù)組的第一個元素不用于存儲有效數(shù)據(jù) * 將input0作為哨兵,可以避免判定inputj中,數(shù)組是否越界 * 因為在j-的過程中,當(dāng)j減小到0時,變成了input0與input0 * 自身進行比較,很明顯這個時候說明位置i之前的數(shù)字都比inputi小 * 位置i上的數(shù)字不需要移動,直接進入下一輪的插入比較。 * */void InsertionSortWithPiquet(int input,int len) int i,j; for (i = 2; i input0 ; j-) inputj + 1 = inputj; inputj = inp

5、ut0; /* inputj一直都是排序的元素中最大的那一個 */ 5冒泡排序/* 冒泡排序法 */void Bublesort(int a,int n) int i,j,k; for(j=0;jn;j+) /* 氣泡法要排序n次*/ for(i=0;iai+1) /* 把值比較大的元素沉到底 */ k=ai; ai=ai+1; ai+1=k; 6選擇排序/*算法原理:首先以一個元素為基準(zhǔn),從一個方向開始掃描, * 比如從左至右掃描,以A0為基準(zhǔn)。接下來從A0.A9 * 中找出最小的元素,將其與A0交換。然后將基準(zhǔn)位置右 * 移一位,重復(fù)上面的動作,比如,以A1為基準(zhǔn),找出 * A1A9中最小

6、的,將其與A1交換。一直進行到基準(zhǔn)位 * 置移到數(shù)組最后一個元素時排序結(jié)束(此時基準(zhǔn)左邊所有元素 * 均遞增有序,而基準(zhǔn)為最后一個元素,故完成排序)。 */void Selectsort(int A,int n) int i,j,min,temp; for(i=0;in;i+) min=i; for(j=i+1;jAj) /* 把剩下元素中最小的那個放到Ai中 */ temp=Ai; Ai=Aj; Aj=temp; 7快速排序/* 快速排序(quick sort)。在這種方法中, * n 個元素被分成三段(組):左段left, * 右段right和中段middle。中段 * 僅包含一個元素。左

7、段中各元素都小于等 * 于中段元素,右段中各元素都大于等于中 * 段元素。因此left和right中的元 * 素可以獨立排序,并且不必對left和 * right的排序結(jié)果進行合并。 * 使用快速排序方法對a0:n-1排序 * 從a0:n-1中選擇一個元素作為middle, * 該元素為支點把余下的元素分割為兩段left * 和right,使得left中的元素都小于 * 等于支點,而right 中的元素都大于等于支點 * 遞歸地使用快速排序方法對left 進行排序 * 遞歸地使用快速排序方法對right 進行排序 * 所得結(jié)果為left+middle+right */void Quick_so

8、rt(int data,int low,int high) int mid; if(lowhigh) mid=Partition(data,low,high); Quick_sort(data,low,mid-1); /* 遞歸調(diào)用 */ Quick_sort(data,mid+1,high); /* 要注意看清楚下面的數(shù)據(jù)之間是如何替換的, * 首先選一個中間值,就是第一個元素datalow, * 然后從該元素的最右側(cè)開始找到比它小的元素,把 * 該元素復(fù)制到它中間值原來的位置(datalow=datahigh), * 然后從該元素的最左側(cè)開始找到比它大的元素,把 * 該元素復(fù)制到上邊剛剛找

9、到的那個元素的位置(datahigh=datalow), * 最后將這個剛空出來的位置裝入中間值(datalow=data0), * 這樣一來比mid大的都會跑到mid的右側(cè),小于mid的會在左側(cè), * 最后一行,返回的low是中間元素的位置,左右分別遞歸就可以排好序了。 */int Partition(int data,int low,int high) int mid; data0=datalow; mid=datalow; while(low high) while(low = mid) -high; datalow=datahigh; /* 從high的位置開始往low的方向找,找到比

10、datalow小的元素,存到datalow中 */ while(low high) & (datalow mid) /* 新得到的datalow肯定小于原來的datalow即mid */ +low; datahigh=datalow; /* 從low的位置開始往high的方向找,找到比datahigh大的元素,存在datahigh中 */ datalow=data0; /* 把low的新位置存上原來的datalow的數(shù)據(jù) */ return low; /* 遞歸時,把它做為右側(cè)元素的low */8堆排序/* * 堆的定義 n 個元素的序列 k1,k2,.,kn當(dāng)且僅當(dāng)滿足下列關(guān)系時, * 稱為

11、堆: * ki=k2i ki=k2i ki=k2i+1 (i=1,2,.,n/2) * 堆排序思路: * 建立在樹形選擇排序基礎(chǔ)上; * 將待排序列建成堆(初始堆生成)后,序列的第一個元素(堆頂元素)就一定是序列中的最大元素; * 將其與序列的最后一個元素交換,將序列長度減一; * 再將序列建成堆(堆調(diào)整)后,堆頂元素仍是序列中的最大元素,再次將其與序列最后一個元素交換并縮短序列長度; * 反復(fù)此過程,直至序列長度為一,所得序列即為排序后結(jié)果。 */void HeapAdjust(int data,int s,int m) /* 排列成堆的形式 */ int j,rc; rc=datas; /* 保存處理元素 */ for(j=2*s;j=m;j*=2) /* 處理父親元素 */ if(jm & datajdataj) break; datas=dataj; /* 父節(jié)點比較大的孩子節(jié)點大則互換 ,保證父節(jié)點比所有子節(jié)點都大(父節(jié)點存儲在前面)*/ s=j; datas=rc; /* 相當(dāng)于dataj=rc */void Heap_sort(int data,int long_n) /* 堆排序函數(shù) */ int i,temp; for(i=long_n/2;i0;-i) /* 還沒有讀懂這樣處理的原因,希望大

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論