快速排序課件

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

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

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

4、后位置一定是中心元素可以申請一個變量保存中心元素，以避免交換目錄快速排序講解i=left;j=right;int temp=aleft;do/從右向左找第1個不小于中心元素的位置jwhile( aj temp & ij) j-;if(ij)a I = a j ;i+;ai=temp;left,right用于限定要排序數(shù)列的范圍,temp即為中心元素程序填空當前元素小于中心元素結(jié)束循環(huán)時，應當在中心元素的左邊移至左邊目錄快速排序講解/從左向右找第1個不大于中心元素的位置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;遞歸地對剩余段作快速排序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);快速排序完整代碼目錄算法分析思考：當數(shù)據(jù)有序的情況下，快速排序的效率如何？快速排序的最壞時間復雜度為O(n2)06 16 21 25 25 49例快速排序的最好時間復雜度為O(nlog2n)快速排序的平均時間復雜度為O(nlog2n)快速排序是不穩(wěn)定的排序方法目錄練習題1）在快速排序方法中，進行每次劃分時，是從當前待排序區(qū)間 的_ 向_依次查找出處于逆序的元素并交換之，最后將 中心元素交換到一個確定位置，從而以該位置把當前區(qū)間劃分為前后 兩端中間2）假定一組記錄的關(guān)鍵字為 (46,79,56,38,40,80)，對其進行快速 排序的一次劃分的結(jié)果為_。38 40 46 56 79 843）快速排序在_情況下效率最低，在_情況下最易發(fā)揮其長