【面试-python】

选择排序(Selection sort)是一种简单直观的排序算法。

它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列第二个位置。以此类推，直到所有元素均排序完毕。

Python实现

def select_sort(ary):
    n = len(ary)
    for i in range(0,n):
        #最小元素下标标记
        min = i                             
        for j in range(i+1,n):
            if ary[j] < ary[min] :
                #找到最小值的下标
                min = j
        #交换两者                     
        ary[min],ary[i] = ary[i],ary[min]   
    return ary

插入排序（Insertion Sort）的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法执行步骤：
1 从第一个元素开始，该元素可以认为已经被排序
2 取出下一个元素，在已经排序的元素序列中从后向前扫描
3 如果被扫描的元素（已排序）大于新元素，则将被扫描元素后移一位
4 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5 将新元素插入到该位置后
6 重复步骤2~5



Python实现

def insert_sort(ary):
    n = len(ary)
    for i in range(1,n):
        if ary[i] < ary[i-1]:
            temp = ary[i]

            #待插入的下标
            index = i           
            #从i-1 循环到 0 (包括0)
            for j in range(i-1,-1,-1):  
                if ary[j] > temp :
                    ary[j+1] = ary[j]
                    #记录待插入下标
                    index = j   
                else :
                    break
            ary[index] = temp
    return ary

1 从数列中挑出一个元素，称为 “基准”（pivot），
2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

换言之
快速排序时基于分治模式处理的，
对一个典型子数组A[p...r]排序的分治过程为三个步骤：
1.分解：
A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得
A[p ..q-1] 

堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。

二叉堆具有以下性质：

父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。

步骤：
1 构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。

2 堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。

3 最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点。



Python实现
def heap_sort(ary) :
    n = len(ary)
    #最后一个非叶子节点
    first = int(n/2-1)       
    #构造大根堆
    for start in range(first,-1,-1) :     
        max_heapify(ary,start,n-1)

    #堆排，将大根堆转换成有序数组
    for end in range(n-1,0,-1):           
        ary[end],ary[0] = ary[0],ary[end]
        max_heapify(ary,0,end-1)
    return ary

#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
#start为当前需要调整最大堆的位置，end为调整边界
def max_heapify(ary,start,end):
    root = start
    while True :
        #调整节点的子节点
        child = root*2 +1               
        if child > end : break
        if child+1 

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

思路：快排中partition 思想：
对于某个索引j，nums[j] 经过partition 操作：
nums[left] 到nums[j - 1] 中的所有元素都不大于nums[j]；
nums[j + 1] 到nums[right] 中的所有元素都不小于nums[j]
即nums[j]元素的位置是排序好了的，我们判断索引j 是否满足条件，若满足则直接返回结果，若
不满足我只需要遍历左序列或者右序列，直至满足要求；无需对整个序列进行排序，所以减少了计算
量；
1. class Solution：
2. def findKthLargest(self, nums： List[int], k： int) -> int：
3. # 快排中分治思想
4. n = len(nums)
5. left, right, target = 0, n-1, n - k
6. while True：
7. pivote = self.getPivote(nums, left, right)
8. if pivote == target： return nums[target]
9. # 只需遍历pivote 左边或者右边减少计算量
10. elif pivote < target： left = pivote + 1
11. elif pivote > target： right = pivote - 1
12.
13. # 分治思想pivote 左边都是不大于pivote 的数，右边是不小于pivote 的数
14. def getPivote(self, nums, left, right)：
15. pivote = random.randint(left, right)
16. nums[left], nums[pivote] = nums[pivote], nums[left]
17. pivote = nums[left]
18. # 双指针法
19. while left < right：
20. while nums[right] >= pivote and left < right： right -= 1
21. nums[left] = nums[right]
22. while nums[left] <= pivote and left < right： left += 1
23. nums[right] = nums[left]
24. nums[left] = pivote
25. return left