快速排序 模板

    def sortIntegers2(self, A):
        
        self.quickSort(A, 0, len(A) - 1)
        
    def quickSort(self, A, start, end):
        if start >= end:
            return
        
        left, right = start, end
        pivot = A[(start + end) / 2];

        
        while left <= right:
            while left <= right and A[left] < pivot:
                left += 1
            
            while left <= right and A[right] > pivot:
                right -= 1
            
            if left <= right:
                A[left], A[right] = A[right], A[left]
                
                left += 1
                right -= 1
        
        self.quickSort(A, start, right)
        self.quickSort(A, left, end)

Python变量值交换

声明变量

a=50

b=10

开始交换，先把其中一个值赋给临时变量，然后才能实现交换变量。

tmp = a

a = b

b = tmp

在Python中，实现两个变量值交换非常方便

声明变量

a=50

b=10

开始交换变量

a,b = b,a

归并排序
Python一切皆对象
Python一切皆对象举例
python函数传参是传值还是传引用？

    def sortIntegers2(self, A):
      n = len(A)
      if n <= 1:
         return A
      return self.sort(A, 0, n - 1)

   def sort(self, A, low, high):
      if low > high:
         return []
      elif low == high:
         return [A[low]]
      mid = (low + high) / 2
      left = self.sort(A, low, mid)
      right = self.sort(A, mid + 1, high)
      return self.merge(left, right)

   def merge(self, left, right):
      n = len(left)
      m = len(right)

      if n == 0:
         return list(right)
      if m == 0:
         return list(left)

      i, j = 0, 0
      result = []

      while i < n and j < m:
         if left[i] <= right[j]:
            result.append(left[i])
            i += 1
         else:
            result.append(right[j])
            j += 1

      if i <= n - 1:
         for k in range(i, n):
            result.append(left[k])
      if j <= m - 1:
         for k in range(j, m):
            result.append(right[k])

      return result

堆排序
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
常见排序算法 - 堆排序 (Heap Sort)

def adjust_heap(lists, i, size):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i
    if i < size / 2:
        if lchild < size and lists[lchild] > lists[max]:
            max = lchild
        if rchild < size and lists[rchild] > lists[max]:
            max = rchild
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)
 
def build_heap(lists, size):
    for i in range(0, (size/2))[::-1]:
        adjust_heap(lists, i, size)
 
def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    for i in range(0, size)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap(lists, 0, i)