python 算法 排序实现快速排序
发布时间：2020-12-17 08:34:13 所属栏目：Python 来源：网络整理
导读：QUICKSORT(A,p,r)是快速排序的子程序，调用划分程序对数组进行划分，然后递归地调用QUICKSORT(A,r)，以完成快速排序的过程。快速排序的最差时间复杂度为O(n2)，平时时间复杂度为O(nlgn)。最差时间复杂度的情况为数组基本有序的时候，平均时间复杂度为数组的数
|
QUICKSORT(A,p,r)是快速排序的子程序，调用划分程序对数组进行划分，然后递归地调用QUICKSORT(A,r)，以完成快速排序的过程。快速排序的最差时间复杂度为O(n2)，平时时间复杂度为O(nlgn)。最差时间复杂度的情况为数组基本有序的时候，平均时间复杂度为数组的数值分布较为平均的时候。在平时情况下快速排序跟堆排序的时间复杂度都为O(nlgn)，但是快速排序的常数项较小，所以要优于堆排序。 PARTITION(A,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 QUICKSORT(A,r) 复制代码 代码如下: if p < r then q ← PARTITION(A,r) QUICKSORT(A,q - 1) QUICKSORT(A,q + 1,r) 实现： 复制代码 代码如下: #!/usr/bin/python import sys def partion(array,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,r): if p < r: q = partion(array,r) quick_sort(array,q - 1) quick_sort(array,r) if __name__ == "__main__": array = [1,3,5,23,64,7,6,34,98,100,9] quick_sort(array,len(array) - 1) for a in array: sys.stdout.write("%d " % a) （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |