算法设计与分析 课件 4.6-分治法 - 典型应用 - 快速排序.pptx

算法设计与分析

分治—快速排序;基本思想：

在数组中任选一个元素作为基准元素，用它和其他每

个元素比较，小于基准的放在它左边，大于等于基准

的放在它右边。

分别对基准的左右两个无序区进行快速排序，直到无

序区只有一个元素。;代码4-5：快速排序的一次划分过程

defPartition(a,p,r):

i=p#左端的哨兵

j=r+1#右端的哨兵

x=a[p]#选择最左端元素为基准元素

whileTrue:

i+=1

whilea[i]xandi=r:

i+=1

j-=1

whilea[j]x:

j-=1

ifi=j:

break

a[i],a[j]=a[j],a[i]

?

a[p]=a[j]

a[j]=x

returnj;代码4-5：快速排序的一次划分过程

defPartition(a,p,r):

i=p#左端的哨兵

j=r+1#右端的哨兵

x=a[p]#选择最左端元素为基准元素

whileTrue:

i+=1

whilea[i]xandi=r:

i+=1

j-=1

whilea[j]x:

j-=1

ifi=j:

break

a[i],a[j]=a[j],a[i]

?

a[p]=a[j]

a[j]=x

returnj;时间复杂度分析;时间复杂度分析;时间复杂度分析;以比较操作为基本操作的算法类中，求解排序问题。

快速排序算法在平均情况下是最优算法。;测试