常考排序

• 快速排序

def quickSort(iList):
      if len(iList) <= 1:
             return iList
      mid = len(iList) // 2
      left = []
      right = []
      for i in range(1,len(iList)):
            if iList[0] < iList[i]:
                   right.append(iList[i])
            else:
                   left.append(iList[i])
      return quickSort(left) + [iList[0]] + quickSort(right)

n = int(input())
nums = list(map(int,input().split()))

def quick_sort(q, l, r):
    
    if l >= r:
        return
    
    mid = (l + r) // 2
    x = q[mid]
    i = l - 1
    j = r + 1
    
    while i < j:
        while True:
            i += 1
            if q[i] >= x:
                break
        while True:
            j -= 1
            if q[j] <= x:
                break
        if i < j:
            q[i], q[j] = q[j], q[i]
    quick_sort(q, l, j)
    quick_sort(q, j + 1, r)

quick_sort(nums,0,n-1)
print(' '.join(list(map(str, nums))))

• 归并排序

def mergeSort(nums):
       if len(nums) <=1 :
              return nums
       mid = len(nums) // 2
       left = mergeSort(nums[:mid])
       right = mergeSort(nums[mid:])
       return merge(left,right)

def merge(left,right):
       i,j,temp = 0,0,[]
       while i < len(left) and j < len(right):
           if left[i] > right[j]:
               temp.append(right[j])
                j += 1
          else:
               temp.append(right[i])
               i += 1
       temp = temp + left[i:]
       temp = temp + right[j:]
       return temp

• 归并排序求逆序数对

class Solution(object):
    def reversePairs(self, nums) -> int:
        if not nums:
            return 0
        self.count = 0
        def merge(nums):
            if len(nums) == 1:
                return nums
            mid = len(nums) // 2
            left = nums[:mid]
            right = nums[mid:]
            left = merge(left)
            right = merge(right)
            return mergeSort(left, right)

        def mergeSort(left,right):
            temp = []
            i, j = 0, 0
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    temp.append(left[i])
                    i += 1
                else:
                    temp.append(right[j])
                    self.count += len(left) - i  ###!!!!!
                    j += 1
            temp += left[i:]
            temp += right[j:]
            return temp
        merge(nums)
        return self.count

• 堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：子结点的键值或索引总是小于（或者大于）它的父节点。

直接使用 from heapq import heapify 实现最小堆。

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

参考资料：
https://www.runoob.com/python3/python-heap-sort.html

https://greyireland.gitbook.io/algorithm-pattern/ji-chu-suan-fa-pian/sort

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/