《剑指Offer》查找和排序

快速排序

在各种基于关键码比较的内排序算法中，快速排序是实践中平均速度最快的算法之一。算法的基本思想是划分，即按照某种标准把考虑的记录划分为“小记录”和“大记录”，并通过递归不断划分，最终得到一个排序的序列。其基本过程是：

• 选择一种标准，把被排序序列中的记录按这种标准分为大小两组。显然，从整体的角度，这两组记录的顺序已定，较小的一组记录应该排在前面。
• 采用同样方式，递归地分别划分前面的到的这两组记录，并继续递归地划分下去。
• 划分总是得到越来越小的分组（可能越来越多），如此工作下去直到每个记录组中最多包含一个记录时，整个序列的排序完成。

快速排序算法有许多不同的实现方法，下面主要介绍一种针对顺序表的实现。

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))