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

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

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

2、性。本文就排序算法中的歸并排序和快速排序如何應(yīng)用分治技術(shù)做簡(jiǎn)單的講述?！　。保畾w并排序　　歸并排序（Mergesort）是第一個(gè)計(jì)算機(jī)排序方法，它是由JohnvonNerman于1945年提出，是最能體現(xiàn)分治技術(shù)設(shè)計(jì)思路的算法之一?！　‘?dāng)待排元素N大于1時(shí)歸并排序的步驟如下：　　⑴將待排序列二分為長(zhǎng)度為N/2的兩個(gè)子序列。　?、七f歸地對(duì)每一個(gè)子序列進(jìn)行歸并排序，直至N等于1。　?、菤w并兩個(gè)排好的有序子序列?！　≡O(shè)一初始序列：49386597761327，對(duì)該序列實(shí)行歸并排序過程如下：　　初始序列：[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；//取中點(diǎn)　　mergesort（a，left，mid）；　　mergesort（a，mid+1，right）；　　merge（a，b，left，mid，right）；//合并到數(shù)組b　　copy（a，left，right）；//復(fù)制回?cái)?shù)組a

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

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

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