分治法實現(xiàn)快速排序Word版

1、實驗一實驗名稱： 利用分治法實現(xiàn)快速排序 實驗時間: 2012年12月 成績： 一、實驗?zāi)康?分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。 本實驗的目的是利用分治策略實現(xiàn)快速排序算法。二、實驗內(nèi)容快速排序算法是基于分治策略的排序算法。其基本思想是，對于輸入的子數(shù)組ap:r,按以下三個步驟進行排序。（1）分解：以ap為基準元素將ap:r劃分成3段ap:q-1,aq和aq+1:r，使ap:q-1中任何一個元素小于等于aq，而aq+1:r中任何一個元素大于等于aq。下標q在劃分過程中確

2、定。（2）遞歸求解：通過遞歸調(diào)用快速排序算法分別對ap:q-1和aq+1:r進行排序。（3）合并：由于對ap:q-1和aq+1:r的排序是就地進行的，所以在ap:q-1和aq+1:r都已排好的序后，不需要執(zhí)行任何計算，ap:r就已排好序?；谶@個思想，可實現(xiàn)的快速排序算法如下：void QuickSort(int a,int p,int r) if(p<r)int q=Partition(a,p,r); QuickSort(a,p,q-1);QuickSort(a,q+1,r);對含有n個元素的數(shù)組a0;n-1進行快速排序只要調(diào)用QuickSort(a,0,n-1)即可。上述算法中的函數(shù)

3、Partition，以確定的一個基準元素ap對子數(shù)組ap:r進行劃分，它是快速排序算法的關(guān)鍵。int Partition(int a,int p,int r) int i=p,j=r+1;int x=ap;while(true)while(a+i<x&&i<r);while(a-j>x);if(i>=j) break;Swap(ai,aj); ap=aj;aj=x;return j; Partition對ap:r進行劃分時，以元素x=ap作為劃分的基準，分別從左、右兩端開始，擴展兩個區(qū)域ap:i和aj:r,使ap:i中元素小于或等于x，而aj:r中元素大

4、于或等于x。初始時，i=p,且j=r+1。在while循環(huán)體中，下標j逐漸減小，i逐漸增大，直到ai>=x>=aj。此時若i<j，就應(yīng)該交換ai與aj的位置，擴展左右兩個區(qū)域。while循環(huán)重復(fù)至i>=j時結(jié)束。這時ap:r已被劃分成ap:q-1,aq和aq+1:r,且滿足ap:q-1中元素不大于aq+1：r中元素。在Partition結(jié)束時返回劃分點q=j。三、實驗過程#include<iostream>using namespace std;inline void Swap(int &x,int &y) /交換x,yint temp=x;

5、x=y;y=temp;int Partition(int a,int p,int r) /Partition 以確定一個基準元素aq對子數(shù)組ap:r進行劃分int i=p,j=r+1;int x=ap;/將<x的元素交換到左邊區(qū)域/將>x得元素交換到右邊區(qū)域while(true)while(a+i<x&&i<r);while(a-j>x);if(i>=j) break;Swap(ai,aj); /交換ai,ajap=aj;aj=x;return j; /返回劃分點void QuickSort(int a,int p,int r) /利用遞歸進

6、行快速排序if(p<r)int q=Partition(a,p,r); /Partition返回劃分點j，此處使q=jQuickSort(a,p,q-1);QuickSort(a,q+1,r);int main() int len;cout<<"請輸入數(shù)組長度: "cin>>len;int *a=new intlen; /動態(tài)生成一個長度為len的數(shù)組cout<<"請輸入一個數(shù)組: " for(int i=0;i<len;i+) /輸入數(shù)組cin>>ai;QuickSort(a,0,len-1); /對數(shù)組進行快排cout<<"排序后的數(shù)組是:"for(int j=0;j<len;j+)cout<<aj<<" " /輸出數(shù)組cout<<endl;delete a; retu