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

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

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

3、Partition，以確定的一個(gè)基準(zhǔn)元素ap對(duì)子數(shù)組ap:r進(jìn)行劃分，它是快速排序算法的關(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對(duì)ap:r進(jìn)行劃分時(shí)，以元素x=ap作為劃分的基準(zhǔn)，分別從左、右兩端開始，擴(kuò)展兩個(gè)區(qū)域ap:i和aj:r,使ap:i中元素小于或等于x，而aj:r中元素大

4、于或等于x。初始時(shí)，i=p,且j=r+1。在while循環(huán)體中，下標(biāo)j逐漸減小，i逐漸增大，直到ai>=x>=aj。此時(shí)若i<j，就應(yīng)該交換ai與aj的位置，擴(kuò)展左右兩個(gè)區(qū)域。while循環(huán)重復(fù)至i>=j時(shí)結(jié)束。這時(shí)ap:r已被劃分成ap:q-1,aq和aq+1:r,且滿足ap:q-1中元素不大于aq+1：r中元素。在Partition結(jié)束時(shí)返回劃分點(diǎn)q=j。三、實(shí)驗(yàn)過程#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 以確定一個(gè)基準(zhǔn)元素aq對(duì)子數(shù)組ap:r進(jìn)行劃分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; /返回劃分點(diǎn)void QuickSort(int a,int p,int r) /利用遞歸進(jìn)

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