HWH

Concentrate on computer science,academic research

快速排序(python版)

1.算法描述

快速排序(Quick-sort)采用分治法,对于数组A[p~r],选定主元A[r],将数组划分为子数组A[p~q-1]A[q+1~r],使得A[p~q-1]中的每个元素均小于等于A[q]A[q+1~r]中的元素均大于等于A[q]。然后对子数组A[p~q-1]A[q+1~r]递归调用快速排序。以数组[8,5,6,3,2,9,7,1,4]的一次划分为例:


8

5

6

3

2

9

7

1

4

3

5

6

8

2

9

7

1

4

3

2

6

8

5

9

7

1

4

3

2

1

8

5

9

7

6

4

3

2

1

4

5

9

7

6

8


选定主元为4,i的初值为p-1,j从p开始向右循环,若A[j]小于等于主元,A[j]与A[i+1]交换,同时i加1。最后主元与A[i+1]交换,这样就完成了一次划分,显然,主元左侧的元素均小于等于主元,右侧的元素均大于等于主元。

快速排序的python代码如下:

def quick_sort(array, l, r):
     if l < r:
         q = partition(array, l, r)
         quick_sort(array, l, q -1)
         quick_sort(array, q + 1, r)
         
 def partition(array, l, r):
     x = array[r]
     i = l - 1
     for j in range(l, r):
         if array[j] <= x:
             i += 1
             array[i], array[j] = array[j], array[i]
     array[i + 1], array[r] = array[r], array[i + 1]
     return i + 1
 
 array  = [8,5,6,3,2,9,7,1,4]
 quick_sort(array,0,8)
 print(array)

2.算法分析

 最坏情况:当输入的数组为逆向有序时,为该算法的最坏情况,即时间复杂度最大的情况,由于划分操作的时间复杂度为θ(n);当对一个长度为0的数组进行递归操作时,会直接返回,时间为T(0) = θ(1)。于是算法总运行时间的递归式为:T(n) = T(n-1) + T(0) + θ(n) = T(n-1) + θ(n)可以解得,T(n) = θ(n²)这就是说,快速排序算法的最坏情况的运行时间是θ(n²)

最好情况:当每次划分都是最平均的时候(即问题规模被划分为[n/2][n/2]-1时),快速排序性能最好,总运行时间的递归式为:T(n) = 2T(n/2) + θ(n),可以解得,T(n) = θ(nlg n)

以上的讨论其实都做了一个前提的声明,输入数据的所有排列都是等概率的。但是事实上这个条件并不一定总是成立。有时候我们再在算法中引入随机性,可以使得算法对所以的输入都有较好的期望性能。很多人都选择随机化版本的快速排序作为大数据输入情况下的排序算法,就是在A[p~r]中随机选择一个元素作为主元,其他过程不变。

发表评论

电子邮件地址不会被公开。 必填项已用*标注