[数据结构与算法]【数据结构】python 排序算法

python实现一些排序算法

class Solution(object):
#插入排序
  def InsertSort(self, nums):
    for i in range(1, len(nums)):
      for j in range(i):
        if nums[j]>nums[i]:
          nums[j], nums[i] = nums[i], nums[j]
    return nums
# 选择排序
  def ChooseSort(self, nums):
    for i in range(len(nums)):
      cur = i
      for j in range(i+1, len(nums)):
        if nums[j]<nums[cur]:
          cur = j
      nums[cur], nums[i] = nums[i], nums[cur]
    return nums
# 快排
  def QuickSort(self, nums):
    def partition(nums, p, q):
      while p<q:
        while p<q and nums[q]>=nums[p]:
          q =q - 1
        nums[p], nums[q] = nums[q], nums[p]
        while p<q and nums[p]<=nums[q]:
          p =p+1
        nums[p], nums[q] = nums[q], nums[p]
      return p

    def quick(nums, p, q):
      if p>=q:
        return
      idx = partition(nums, p, q)
      quick(nums, p, idx-1)
      quick(nums, idx+1, q)
      return nums
    
    quick(nums, 0, len(nums)-1)
    return nums
# 归并排序
  def mergeSort(self, nums):
    def merge(left, right):
      l = 0
      r = 0
      res = []
      if len(left)==0 or len(right)==0:
        return 

      while l<len(left) and r<len(right):
        if left[l] <= right[r]:
          res.append(left[l])
          l = l+1
        else:
          res.append(right[r])
          r = r+1
      if l<len(left):
        res = res + left[l:]
      elif r< len(right):
        res = res + right[r:]
      return res

    if len(nums)<= 1:
      return nums
    pre = self.mergeSort(nums[0:len(nums)//2])
    last = self.mergeSort(nums[len(nums)//2:])
    res = merge(pre, last)
    return res