排序算法常见的面试题

1. 找出前m个最大的数

   思路：取前m个数，构建一个大小为m的小顶堆；从第m+1个数开始arr[j]，跟堆顶元素比较，如果arr[j]大于堆顶元素，则将该元素跟堆顶元素做替换，调整堆，直到遍历到最后一个元素，最终的小顶堆中的元素就是结果

   def heapify(arr, i, m):
   	#调整小顶堆
       smallest = i
       l = 2*i+1
       r = 2*i+2
       if l<m and arr[l]<arr[smallest]:
           smallest = l
       if r<m and arr[r]<arr[smallest]:
           smallest = r
       if i != smallest:
           arr[smallest], arr[i] = arr[i], arr[smallest]
           heapify(arr, smallest, m)
   
   
   
   def get_top_m_items(arr, m):
   	#构建小顶堆
       sub_arr = arr[:m]
       for i in range(m-1, -1,-1):
           heapify(sub_arr, i, m)
   
       for j in range(m, len(arr)):
           if arr[j]>sub_arr[0]:
               sub_arr[0] = arr[j]
           heapify(sub_arr, 0, m)
       return sub_arr
   
   

2. 给定两个排序好的子数组，求出前m个最大的数

   思路：归并排序

   #coding:utf-8
   #给定两个排序好的数组，从中找出m个最大的数
   def get_top_k_item(arr_1, arr_2, m):
       top_m_arr = []
       i, j = 0, 0
       while i<len(arr_1) and j<len(arr_2) and m>0:
           if arr_1[i]>arr_2[j]:
               top_m_arr.append(arr_1[i])
               i+=1
               m-=1
           else:
               top_m_arr.append(arr_2[j])
               j+=1
               m-=1
       print top_m_arr, "==="
       if m==0:
           return top_m_arr
       else:
           if i<len(arr_1):
               top_m_arr.extend(arr_1[i:i+m])
           if j<len(arr_2):
               top_m_arr.extend(arr_2[j:j+m])
       return top_m_arr
   
   arr_1 = [2,4,5,8,9]
   arr_2 = [6,6,7]
   k =6
   print arr_1, arr_2, k
   res = get_top_k_item(arr_1[::-1], arr_2[::-1], k)
   print res
   

3. 找出第k大的数

   思路：快速排序

   def partition(num, low, high):
       first = low
       pivot = num[low]
       low += 1
   
       while (low <= high):
           while (low <= high and num[low] >= pivot):
               low += 1
           while (low <= high and num[high] <= pivot):
               high -= 1
           if high < low:
               break
           num[low], num[high] = num[high], num[low]
   
       num[high], num[first] = num[first], num[high]
       return high
       
   def findkth(num,low,high,k):   #找到数组里第k个最大的数
           while low<=high:
               index=partition(num,low,high)
               if index==k-1:
                   return num[index]
               elif index < k-1:
                   low = index+1
               else:
                   high = index-1