快速排序 模板

    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

開始交換鸠天，先把其中一個(gè)值賦給臨時(shí)變量路克，然后才能實(shí)現(xiàn)交換變量统抬。

tmp = a

a = b

b = tmp

在Python中，實(shí)現(xiàn)兩個(gè)變量值交換非常方便

聲明變量

a=50

b=10

開始交換變量

a,b = b,a

歸并排序
Python一切皆對(duì)象
Python一切皆對(duì)象舉例
python函數(shù)傳參是傳值還是傳引用主籍？

    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

堆排序
堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出门烂，將剩余的堆繼續(xù)調(diào)整為最大堆乳愉，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束屯远。在堆中定義以下幾種操作：

最大堆調(diào)整（Max-Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整蔓姚，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
創(chuàng)建最大堆（Build-Max-Heap）：將堆所有數(shù)據(jù)重新排序，使其成為最大堆
堆排序（Heap-Sort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)慨丐，并做最大堆調(diào)整的遞歸運(yùn)算
常見排序算法 - 堆排序 (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)