分治技術(shù)在排序算法中的應(yīng)用

《分治技術(shù)在排序算法中的應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、分治技術(shù)在排序算法中的應(yīng)用【摘要】講述了運用分治技術(shù)的思想實現(xiàn)排序算法中的歸并排序、快速排序兩種排序算法，然后對兩種排序算法的效率進行了比較，得出了采用分治技術(shù)的排序算法是比較有效的算法。　　【關(guān)鍵詞】分治技術(shù);排序算法;歸并排序;快速排序　　　　排序是計算機科學(xué)中經(jīng)常遇到的工作，是程序設(shè)計中的一種重要運算，它的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成某個按關(guān)鍵字有序的序列。分治技術(shù)的基本思想是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題，這些子問題相互獨立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。如果在排序算法中巧妙得應(yīng)用分治技術(shù)，可以使排序算法更具藝術(shù)

2、性。本文就排序算法中的歸并排序和快速排序如何應(yīng)用分治技術(shù)做簡單的講述。　?。保畾w并排序　　歸并排序（Mergesort）是第一個計算機排序方法，它是由JohnvonNerman于1945年提出，是最能體現(xiàn)分治技術(shù)設(shè)計思路的算法之一?！　‘?dāng)待排元素N大于1時歸并排序的步驟如下：　?、艑⒋判蛄卸譃殚L度為N/2的兩個子序列。　?、七f歸地對每一個子序列進行歸并排序，直至N等于1?！　、菤w并兩個排好的有序子序列?！　≡O(shè)一初始序列：49386597761327，對該序列實行歸并排序過程如下：　　初始序列：[49][38][65][97][76][13][27]　　第一步：[3849][659

3、7][1376][27]　　第二步：[38496597][132776]　　第三步：[13273849657697]　　歸并排序用代碼描述如下：　　算法mergesort：　　template〈typenameT〉　　voidmergesort（Ta[]，intleft，intright）　　{　　T*b=neid=（left+right）/2；//取中點　　mergesort（a，left，mid）；　　mergesort（a，mid+1，right）；　　merge（a，b，left，mid，right）；//合并到數(shù)組b　　copy（a，left，right）；//復(fù)制回數(shù)組a

4、　　}　　}　　其中，算法Merge（）合并兩個排好序的數(shù)組到一個新的數(shù)組中，用代碼表示Merge（）如下：　　template〈typenameT〉　　voidmerge（Ta[]，Tb[]，int1，intm，intr）　　{　　inti=1，j=m+1,k=1；　?。ΓΓ╦m）　　{　　for(intq=j；q求解（常為遞歸）—>合并”的流程來進行設(shè)計的，是一個典型的分治算法?！　?.快速排序　　快速排序是由C.A.EHoare于1962年提出的，至今被認為是最好的排序算法?！坝嬎銠C科學(xué)與工程（prtingScience＆Engineering）”雜志將快速排序算法列為20世

5、紀(jì)在科學(xué)和工程的開發(fā)與應(yīng)用中最有影響的10個算法之一。它也是一種基于分治技術(shù)的排序算法，也是按“劃分－>求解—>合并”的思路來設(shè)計的。不過快速排序中的劃分不再是平衡的二爹媽，它是以待排序的任一元素（常為首元素，常稱為“樞軸”）為界限，分成大于該元素的部分和小于該元素的部分，然后再遞歸地解決該兩部分的一種高效算法。　　我們首先分析快速排序中的“劃分”方法。劃分的目的在于劃分后使得一個元素處于一個正確的位置（該元素前面所有元素均小于后面所有元素）。要達到這個目的，方法是多樣的，有的需要較多輔助空間，有的需要較少輔助空間。有的快一點，有的慢一點，這里給出一種所需輔助空間較小，而又較快的方法

6、：　　算法split：　　template　　intsplit(Ta[],intloplate　　voidqaort（Ta[]，intleft，intright）　　{　　if（left求解（常為遞歸）—>合并”的思路來設(shè)計的，只不過快速排序中對劃分后的子序列是直接就地排序的，未引入輔助數(shù)組，因此合并的過程較為簡單，只是棧中函數(shù)調(diào)用的簡單返回，幾乎不需要進行任何其它運算?！　【C上，歸并排序和快速排序都是分治技術(shù)在排序中的應(yīng)用。但兩者在設(shè)計過程中的側(cè)重點不同，歸并排序側(cè)重于分治中的“合并”步驟；而快速排序則側(cè)重于“劃分”步驟。但兩者都很好的體現(xiàn)了分治技術(shù)的思想?！　　　　?/p>