主要分为两个子算法，PARTITION(A, p, r)以A[r]为基准对数组进行一个划分，比A[r]小的放在左边，比A[r]大的放在右边
QUICKSORT(A, p, r)是快速排序的子程序，调用划分程序对数组进行划分，然后递归地调用QUICKSORT(A, p, r)，以完成快速排序的过程。快速排序的最差时间
来源gaodai.ma#com搞#代!码网
复杂度为O(n2)，平时时间复杂度为O(nlgn)。最差时间复杂度的情况为数组基本有序的时候，平均时间复杂度为数组的数值分布较为平均的时候。在平时情况下快速排序跟堆排序的时间复杂度都为O(nlgn)，但是快速排序的常数项较小，所以要优于堆排序。
PARTITION(A, p, r)
代码如下:
x ← A[r]
i ← p – 1
for j ← p to r – 1
do if A[j] ≤ x
then i ← i + 1
swap(A[i], A[j])
swap(A[i + 1], A[r])
return i + 1
i ← p – 1
for j ← p to r – 1
do if A[j] ≤ x
then i ← i + 1
swap(A[i], A[j])
swap(A[i + 1], A[r])
return i + 1
QUICKSORT(A, p, r)
代码如下:
if p <r
then q ← PARTITION(A, p, r)
QUICKSORT(A, p, q – 1)
QUICKSORT(A, q + 1, r)
then q ← PARTITION(A, p, r)
QUICKSORT(A, p, q – 1)
QUICKSORT(A, q + 1, r)
实现：
代码如下:
#!/usr/bin/python
import sys
def partion(array, p, r):
x = array[r]
i = p – 1
for j in range(p, r):
if (array[j] <x):
i+=1
array[j], array[i] = array[i], array[j]
i+=1
array[i], array[r] = array[r], array[i]
return i
def quick_sort(array, p, r):
if p <r:
q = partion(array, p, r)
quick_sort(array, p, q – 1)
quick_sort(array, q + 1, r)
if __name__ == “__main__”:
array = [1, 3, 5, 23, 64, 7, 23, 6, 34, 98, 100, 9]
quick_sort(array, 0, len(array) – 1)
for a in array:
sys.stdout.write(“%d ” % a)
import sys
def partion(array, p, r):
x = array[r]
i = p – 1
for j in range(p, r):
if (array[j] <x):
i+=1
array[j], array[i] = array[i], array[j]
i+=1
array[i], array[r] = array[r], array[i]
return i
def quick_sort(array, p, r):
if p <r:
q = partion(array, p, r)
quick_sort(array, p, q – 1)
quick_sort(array, q + 1, r)
if __name__ == “__main__”:
array = [1, 3, 5, 23, 64, 7, 23, 6, 34, 98, 100, 9]
quick_sort(array, 0, len(array) – 1)
for a in array:
sys.stdout.write(“%d ” % a)
以上就是python 算法 排序实现快速排序的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：python 算法 排序实现快速排序
转载请注明原文链接：python 算法 排序实现快速排序
