快速排序
在各种基于关键码比较的内排序算法中，快速排序是实践中平均速度最快的算法之一。算法的基本思想是划分，即按照某种标准把考虑的记录划分为“小记录”和“大记录”，并通过递归不断划分，最终得到一个排序的序列。其基本过程是：
- 选择一种标准，把被排序序列中的记录按这种标准分为大小两组。显然，从整体的角度，这两组记录的顺序已定，较小的一组记录应该排在前面。
- 采用同样方式，递归地分别划分前面的到的这两组记录，并继续递归地划分下去。
- 划分总是得到越来越小的分组（可能越来越多），如此工作下去直到每个记录组中最多包含一个记录时，整个序列的排序完成。
快速排序算法有许多不同的实现方法，下面主要介绍一种针对顺序表的实现。
def qsort_rec(lst, l, r):
if l >= r:return
i = l
j = r
pivot = lst[l]
while i<j:
while i<j and lst[j] >= pivot:
j -= 1
if i <j:
lst[i] = lst[j]
i+=1
while i<j and lst[i] <= pivot:
i +=1
if i < j:
lst[j] = lst[i]
j -=1
lst[i] = pivot
qsort_rec(lst, l, i-1)
qsort_rec(lst, i+1, r)
def quick_sort(lst):
qsort_rec(lst, 0, len(lst)-1)
origin = [3,4,6,72,1,-1,6,9,17]
quick_sort(origin)
print(origin)
复杂度分析：
- 排序中关键码的比较次数不超过
O(nlogn) - 最差情况：待排序序列已经是升序或者降序的时候，总的比较次数是
O(n^2)
根据二叉树理论，所有n个节点的二叉树的平均高度是 O(logn)。因此，快速排序的时间复杂度是 O(nlogn)。
虽然不知道解释器每层递归花费的具体空间量，但应该认为它是常量，与递归的深度和函数调用次数无关。因此， 分析前面快速排序的空间复杂度，最重要的问题就是递归的深度，最坏情况是 O(n)。
快速排序算法不会因为原序列接近有序而更高效（适得其反），因此它不具有适应性。
另一种简单实现：
def quick_sort(lst):
def qsort(lst, begin, end):
if begin >= end:
return
pivot = lst[begin]
i = begin
for j in range(begin+1, end+1):
if lst[j] < pivot:
i+=1
lst[i], lst[j] = lst[j], lst[i]
lst[begin],lst[i] = lst[i], lst[begin]
qsort(lst, begin, i-1)
qsort(lst, i+1, end)
qsort(lst,0, len(lst)-1)
tlist = [4,2,1,7,0,9,3]
quick_sort(tlist)
print(tlist)
面试题
旋转数组的最小数字：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
运行时间：962ms, 占用内存：5724k
def minNumberInRotateArray(rotateArray):
# write code here
if not rotateArray:
return 0
ind1 = 0
ind2 = len(rotateArray) -1
indMid = ind1
while rotateArray[ind1] >= rotateArray[ind2]:
if ind2 - ind1 == 1:
indMid = ind2
break
indMid = (ind1 + ind2)//2
if rotateArray[indMid] >= rotateArray[ind1]:
ind1 = indMid
elif rotateArray[indMid] <= rotateArray[ind2]:
ind2 = indMid
return rotateArray[indMid]
tlist = [3,4,5,1,2]
res = minNumberInRotateArray(tlist)
print(res)
以上思路不够完善：[1,0,1,1,1]和[1,1,1,0,1]也是符合题目要求的数组，但是当第一个指针和第二个指针分别指向1时，有的中间指针在0 前面，有的在0后面。因此，当两个指针指向的数字和他们中间的数字三者相同的时候，无法判断中间的数字是位于前面的子数组还是位于后面的，也就无法移动两个指针来缩小查找范围。此时，不得不采用顺序查找的方法。
完善版本：
运行时间：1005ms， 占用内存：5740k
新增加函数实现顺序查找功能
class Solution:
def MinOrder(self, nums, left, right):
res = nums[left]
for i in range(left+1, right):
#print(i,nums[i])
if nums[i] < res:
res = nums[i]
return res
def minNumberInRotateArray(self, rotateArray):
# write code here
if not rotateArray:
return 0
left, right = 0, len(rotateArray)-1
mid = 0
while rotateArray[left]>=rotateArray[right]:
if right - left ==1:
mid = right
break
mid = (left + right)//2
if rotateArray[left]==rotateArray[right] \
and rotateArray:
#print(left, right, rotateArray[left:right])
return self.MinOrder(rotateArray, left, right)
if rotateArray[mid]>= rotateArray[left]:
left = mid
else:
right = mid
return rotateArray[mid]
sl = Solution()
num = [2,2,2,2,1,2]
print(sl.minNumberInRotateArray(num))
网友评论