#!/usr/bin/python 
import sys 
 
def merge(nums, first, middle, last): 
  ''''' merge ''' 
  # 切片邊界,左閉右開并且是了0為開始 
  lnums = nums[first:middle+1] 
  rnums = nums[middle+1:last+1] 
  lnums.append(sys.maxint) 
  rnums.append(sys.maxint) 
  l = 0 
  r = 0 
  for i in range(first, last+1): 
    if lnums[l] < rnums[r]: 
      nums[i] = lnums[l] 
      l+=1 
    else: 
      nums[i] = rnums[r] 
      r+=1 
def merge_sort(nums, first, last): 
  ''''' merge sort
  merge_sort函數(shù)中傳遞的是下標(biāo)，不是元素個數(shù)
  ''' 
  if first < last: 
    middle = (first + last)/2 
    merge_sort(nums, first, middle) 
    merge_sort(nums, middle+1, last) 
    merge(nums, first, middle,last) 
 
if __name__ == '__main__': 
  nums = [10,8,4,-1,2,6,7,3] 
  print 'nums is:', nums 
  merge_sort(nums, 0, 7) 
  print 'merge sort:', nums

#!/usr/bin/python 
importsys 
 
definsert_sort(a): 
  ''''' 插入排序
  有一個已經(jīng)有序的數(shù)據(jù)序列，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)，
  但要求插入后此數(shù)據(jù)序列仍然有序。剛開始 一個元素顯然有序，然后插入一
  個元素到適當(dāng)位置，然后再插入第三個元素，依次類推
  ''' 
  a_len = len(a) 
  if a_len = 0 and a[j] > key: 
      a[j+1] = a[j] 
      j-=1 
    a[j+1] = key 
  return a 
 
if __name__ == '__main__': 
  nums = [10,8,4,-1,2,6,7,3] 
  print 'nums is:', nums 
  insert_sort(nums) 
  print 'insert sort:', nums

import sys 
def select_sort(a): 
  ''''' 選擇排序 
  每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，
  順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。
  選擇排序是不穩(wěn)定的排序方法。
  ''' 
  a_len=len(a) 
  for i in range(a_len):#在0-n-1上依次選擇相應(yīng)大小的元素 
    min_index = i#記錄最小元素的下標(biāo) 
    for j in range(i+1, a_len):#查找最小值 
      if(a[j]<a[min_index]): 
        min_index=j 
    if min_index != i:#找到最小元素進(jìn)行交換 
      a[i],a[min_index] = a[min_index],a[i] 
 
if __name__ == '__main__': 
  A = [10, -3, 5, 7, 1, 3, 7]  
  print 'Before sort:',A  
  select_sort(A)  
  print 'After sort:',A

import sys 
def shell_sort(a): 
  ''''' shell排序 
  ''' 
  a_len=len(a) 
  gap=a_len/2#增量 
  while gap>0: 
    for i in range(a_len):#對同一個組進(jìn)行選擇排序 
      m=i 
      j=i+1 
      while j<a_len: 
        if a[j]<a[m]: 
          m=j 
        j+=gap#j增加gap 
      if m!=i: 
        a[m],a[i]=a[i],a[m] 
    gap/=2 
 
if __name__ == '__main__': 
  A = [10, -3, 5, 7, 1, 3, 7]  
  print 'Before sort:',A  
  shell_sort(A)  
  print 'After sort:',A

#!/usr/bin env python 
 
# 數(shù)組編號從 0開始 
def left(i): 
  return 2*i +1 
def right(i): 
  return 2*i+2 
 
#保持最大堆性質(zhì) 使以i為根的子樹成為最大堆 
def max_heapify(A, i, heap_size): 
  if heap_size <= 0: 
    return 
  l = left(i) 
  r = right(i) 
  largest = i # 選出子節(jié)點(diǎn)中較大的節(jié)點(diǎn) 
  if l A[largest]: 
    largest = l 
  if r A[largest]: 
    largest = r 
  if i != largest :#說明當(dāng)前節(jié)點(diǎn)不是最大的，下移 
    A[i], A[largest] = A[largest], A[i] #交換 
    max_heapify(A, largest, heap_size)#繼續(xù)追蹤下移的點(diǎn) 
  #print A 
# 建堆  
def bulid_max_heap(A): 
  heap_size = len(A) 
  if heap_size >1: 
    node = heap_size/2 -1 
    while node >= 0: 
     max_heapify(A, node, heap_size) 
     node -=1 
 
# 堆排序 下標(biāo)從0開始 
def heap_sort(A): 
  bulid_max_heap(A) 
  heap_size = len(A) 
  i = heap_size - 1 
  while i > 0 : 
    A[0],A[i] = A[i], A[0] # 堆中的最大值存入數(shù)組適當(dāng)?shù)奈恢茫⑶疫M(jìn)行交換 
    heap_size -=1 # heap 大小 遞減 1 
    i -= 1 # 存放堆中最大值的下標(biāo)遞減 1 
    max_heapify(A, 0, heap_size) 
 
if __name__ == '__main__' : 
 
  A = [10, -3, 5, 7, 1, 3, 7] 
  print 'Before sort:',A 
  heap_sort(A) 
  print 'After sort:',A

#!/usr/bin/env python 
# 快速排序 
'''''
劃分 使?jié)M足 以A[r]為基準(zhǔn)對數(shù)組進(jìn)行一個劃分，比A[r]小的放在左邊，
  比A[r]大的放在右邊
快速排序的分治partition過程有兩種方法，
一種是上面所述的兩個指針?biāo)饕磺耙缓笾鸩较蚝髵呙璧姆椒?
另一種方法是兩個指針從首位向中間掃描的方法。
''' 
#p,r 是數(shù)組A的下標(biāo) 
def partition1(A, p ,r): 
  '''''
   方法一，兩個指針?biāo)饕磺耙缓笾鸩较蚝髵呙璧姆椒?
  ''' 
  x = A[r] 
  i = p-1 
  j = p 
  while j < r: 
    if A[j] < x: 
      i +=1 
      A[i], A[j] = A[j], A[i] 
    j += 1 
  A[i+1], A[r] = A[r], A[i+1] 
  return i+1 
 
def partition2(A, p, r): 
  '''''
  兩個指針從首尾向中間掃描的方法
  ''' 
  i = p 
  j = r 
  x = A[p] 
  while i = x and i < j: 
      j -=1 
    A[i] = A[j] 
    while A[i]<=x and i < j: 
      i +=1 
    A[j] = A[i] 
  A[i] = x 
  return i 
 
# quick sort 
def quick_sort(A, p, r): 
  '''''
    快速排序的最差時間復(fù)雜度為O(n2)，平時時間復(fù)雜度為O(nlgn)
  ''' 
  if p < r: 
    q = partition2(A, p, r) 
    quick_sort(A, p, q-1) 
    quick_sort(A, q+1, r) 
 
if __name__ == '__main__': 
 
  A = [5,-4,6,3,7,11,1,2] 
  print 'Before sort:',A 
  quick_sort(A, 0, 7) 
  print 'After sort:',A