[python]实现几种O(nlogn)的排序算法

快速排序

def quicksort(A, low, high):def partition(A, low, high):i = low - 1 pivot = A[high]for j in range(low, high):if A[j] < pivot:i += 1 A[i], A[j] = A[j], A[i]A[i+1], A[high] = A[high], A[i+1]return i+1 if low < high:pi = partition(A, low, high)quicksort(A, low, pi-1)quicksort(A, pi+1, high)
quicksort(A, 0, len(A)-1)

归并排序

def mergeSort(nums): if len(nums) > 1: mid = len(nums)//2L = nums[:mid] R = nums[mid:] mergeSort(L)mergeSort(R)i = j = k = 0while i < len(L) and j < len(R): if L[i] < R[j]: nums[k] = L[i] i+=1else: nums[k] = R[j] j+=1k+=1while i < len(L): nums[k] = L[i] i+=1k+=1while j < len(R): nums[k] = R[j] j+=1k+=1

堆排序

  def heapSort(nums):def heapify(nums, n, i): largest = il = 2 * i + 1r = 2 * i + 2if l < n and nums[i] < nums[l]: largest = l if r < n and nums[largest] < nums[r]: largest = r if largest != i: nums[i], nums[largest] = nums[largest], nums[i]heapify(nums, n, largest)n = len(nums) for i in range(n, -1, -1): heapify(nums, n, i) for i in range(n-1, 0, -1): nums[i], nums[0] = nums[0], nums[i]heapify(nums, i, 0) return nums