快速排序課件

1、江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)快速排序作者：楊勁松內(nèi)容提要快速排序?qū)肟焖倥判蛩枷肟焖倥判蛑v解快速排序算法分析練習(xí)題退出快速排序?qū)胝?qǐng)同學(xué)們使用冒泡排序的方法將下列數(shù)據(jù)排序：（從小到大）21 25 49 16 25 06 目錄初始狀態(tài)第一次交換結(jié)束快速排序?qū)?冒泡排序過程目錄第二次交換第二次交換結(jié)束快速排序?qū)?冒泡排序過程目錄第三次交換結(jié)束第二次交換結(jié)束第四次交換結(jié)束快速排序?qū)?冒泡排序過程目錄第六次交換結(jié)束第五次交換結(jié)束請(qǐng)同學(xué)們說說冒泡排序是如何工作的快速排序?qū)肽夸?對(duì)所有記錄從左到右每相鄰的元素進(jìn)行比較 ，不符合要求則交換快速排序?qū)?冒泡排序分析冒泡排序的基本做法：思考

2、：在數(shù)據(jù)為以下排列時(shí)，冒泡的排序效果好不好？49 25 25 21 16 06 快速排序?qū)?冒泡排序分析初始狀態(tài)是反序的，則需要進(jìn)行n-1趟掃描目錄快速排序?qū)?冒泡排序分析從直觀上49移動(dòng)到最終的位置經(jīng)過了n-1次比較和交換49 25 25 21 16 0606 16 21 25 25 49能不能不經(jīng)過n-1次比較和交換呢？不能？這是由于冒泡排序中需要相鄰的元素兩兩比較、交換目錄快速排序思想基本思想：1）尋找一個(gè)中心元素（通常為第一個(gè)數(shù)）2）將小于中心點(diǎn)的元素移動(dòng)至中心點(diǎn)之前，大于中心點(diǎn)的元素移動(dòng)至中心點(diǎn)之后。3）對(duì)上步分成的兩個(gè)無序數(shù)組段重復(fù)1）、2）操作直到段長(zhǎng)為1。t=t目錄快速排序

3、思想以21為中心元素劃分可得：以06、49為中心元素劃分可得：目錄快速排序講解選取中心元素的問題選取第一個(gè)數(shù)為中心元素如何劃分問題如何重復(fù)步驟將所有數(shù)據(jù)排序使用遞歸目錄當(dāng)已知中心元素的前提下，怎樣將其他元素劃分好？（即：大于中心點(diǎn)在之后，小于中心點(diǎn)在之前）需要解決的問題快速排序講解i012345i=0i=1j=5j=5ji=1j=3i=1j=4i=2j=3i=2j=2算法終止目錄快速排序講解請(qǐng)同學(xué)們思考該算法有沒有可以改進(jìn)的地方目錄快速排序講解i012345i=0i=1j=5j=5ji=1j=3i=1j=4i=2j=3i=2j=2算法終止通過動(dòng)畫，可以看出每次中心元素都要交換。根據(jù)劃分的思想最

4、后位置一定是中心元素可以申請(qǐng)一個(gè)變量保存中心元素，以避免交換目錄快速排序講解i=left;j=right;int temp=aleft;do/從右向左找第1個(gè)不小于中心元素的位置jwhile( aj temp & ij) j-;if(ij)a I = a j ;i+;ai=temp;left,right用于限定要排序數(shù)列的范圍,temp即為中心元素程序填空當(dāng)前元素小于中心元素結(jié)束循環(huán)時(shí)，應(yīng)當(dāng)在中心元素的左邊移至左邊目錄快速排序講解/從左向右找第1個(gè)不大于中心元素的位置iwhile(aitemp & ij ) i+;if(ij)aj=ai;j-;while(ij);ai=temp; /將中心元素

5、t填入最終位置程序填空目錄快速排序講解函數(shù)頭：quicksort(int a,int left,int right)初始化：i=left;j=right;int temp=aleft;劃分：do一次劃分 while(ij);中心元素填入：ai=temp;遞歸地對(duì)剩余段作快速排序quicksort(a,left,i-1);quicksort(a,i+1,right);目錄快速排序完整代碼void quicksort(int a,int left,int right)int i,j;if(lefttemp & ij)j-;if(ij)ai=aj;i+;目錄while(aitemp & ij)i+;

6、if(ij)aj=ai;j-;while(ij);ai=temp;quicksort(a,left,i-1);quicksort(a,i+1,right);快速排序完整代碼目錄算法分析思考：當(dāng)數(shù)據(jù)有序的情況下，快速排序的效率如何？快速排序的最壞時(shí)間復(fù)雜度為O(n2)06 16 21 25 25 49例快速排序的最好時(shí)間復(fù)雜度為O(nlog2n)快速排序的平均時(shí)間復(fù)雜度為O(nlog2n)快速排序是不穩(wěn)定的排序方法目錄練習(xí)題1）在快速排序方法中，進(jìn)行每次劃分時(shí)，是從當(dāng)前待排序區(qū)間 的_ 向_依次查找出處于逆序的元素并交換之，最后將 中心元素交換到一個(gè)確定位置，從而以該位置把當(dāng)前區(qū)間劃分為前后 兩端中間2）假定一組記錄的關(guān)鍵字為 (46,79,56,38,40,80)，對(duì)其進(jìn)行快速 排序的一次劃分的結(jié)果為_。38 40 46 56 79 843）快速排序在_情況下效率最低，在_情況下最易發(fā)揮其長(zhǎng)