贵州安顺做公司网站/sem技术培训

最小的k个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路：可以先利用排序算法进行排序，然后取出k个最小的数。排序算法有冒泡、选择、堆排序、归并、快排等，为了练习这种排序算法，我们用这些算法一一求解本题。

class Solution:def GetLeastNumbers_Solution(self, tinput, k):# write code hereif k > len(tinput) or k < 0:return []#堆排序#建立最大堆def max_heap(tinput,start,end):root = startwhile True:child = root * 2 + 1if child > end:breakif child + 1 <= end and tinput[child] <= tinput[child+1]:child = child + 1if tinput[child] > tinput[root]:tinput[child],tinput[root] = tinput[root],tinput[child]root = childelse:break#堆调整def adjust_heap(tinput):n = len(tinput)//2 - 1for start in range(n,-1,-1):max_heap(tinput,start,len(tinput)-1)for end in range(len(tinput)-1,0,-1):tinput[end],tinput[0] = tinput[0],tinput[end]max_heap(tinput,0,end-1)return tinputnums = adjust_heap(tinput)return nums[:k]

        #冒泡排序'''if k > len(tinput) or k < 0:return []for i in range(len(tinput)-1):for j in range(len(tinput)-i-1):if tinput[j]>tinput[j+1]:tinput[j],tinput[j+1] = tinput[j+1],tinput[j]return tinput[:k]'''

 		# 选择排序"""if k > len(tinput) or k < 0:return []for i in range(len(tinput)):min = ifor j in range(i+1,len(tinput)):  #寻找最小元素的下表if tinput[j] < tinput[min]:min = jtinput[min],tinput[i] = tinput[i],tinput[min] #交换return tinput[:k]"""

# 快排序，利用双指针从左右两个方向进行滑动，把小于基准值的元素放在左边，大于的放在右边，记录中间元素的值，然后再和基准值进行调换位置class Solution:def GetLeastNumbers_Solution(self, tinput, k):# write code hereif k > len(tinput) or k < 0:return []#快排序def patition(A,low,high):i = lowj = highx = A[low]while i < j:while(i<j and A[j]>=x):j -= 1while(i<j and A[i]<=x):i += 1if i != j:A[i],A[j] = A[j],A[i]A[low],A[i] = A[i],A[low]return idef quicksort(A,low,high):if low < high:i = patition(A,low,high)quicksort(A,low,i-1)quicksort(A,i+1,high)return AA = quicksort(tinput,0,len(tinput)-1)return A[:k]

#归并排序：不断划分数组，直到每个数组只有一个元素，然后进行合并。
class Solution:def GetLeastNumbers_Solution(self, tinput, k):# write code hereif k > len(tinput) or k < 0:return []#归并排序def merge(left,right):result = []i,j = 0,0while i<len(left) and j<len(right):if left[i]<right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1while i != len(left):result.append(left[i])i += 1while j != len(right):result.append(right[j])j += 1return resultdef mergeSort(nums):if len(nums) < 2:return numselse:middle = len(nums)//2left = mergeSort(nums[:middle])right = mergeSort(nums[middle:])return merge(left,right)A = mergeSort(tinput)return A[:k]