1. 快速排序：
class quickSort(): def __init__(self,nums): self.nums = nums[:] def partition(self,left,right): key = self.nums[left] while left<right: while left<right and self.nums[right]>=key: #注意这里有个“=”，用来防止key被来回交换而陷入死循环。 right-=1 while left<right and self.nums[left]<key: left+=1 if left<right: #找到对应位置后交换值。 tmp = self.nums[left] self.nums[left] = self.nums[right] self.nums[right] = tmp print left return left def qs(self,left,right): if left>=right: return index = self.partition(left,right) self.qs(left,index) #每次将数组切成两段，中间没有空余的位置。 self.qs(index+1,right) if __name__ == '__main__': nums = [10,22,1,9,87,3,2,66,1,8,9,0,7,7] s = quickSort(nums) s.qs(0,len(nums)-1) print nums print s.nums 2. 堆排序： class heap: def __init__(self,arr): self.arr = arr def insert(self,value): #insert from the end of arr arr.append(value) self.up() def pop(self): #get the biggest one in array and resort the array top = self.arr[0] arr[0] = arr.pop() self.down() return top def swap(self,child_index,parent_index): arr[child_index],arr[parent_index] = arr[parent_index],arr[child_index] def up(self): child_index = len(arr)-1 while(True): parent_index = (child_index-1)/2 if(parent_index>=0 and arr[child_index]>arr[parent_index]): self.swap(child_index,parent_index) child_index = parent_index else: break def down(self): parent = 0 end = len(arr)-1 while(True): left_child = 2*parent+1 right_child = left_child+1 if(right_child<=end): #has two childern if(arr[left_child]>arr[right_child]): #find the bigger child bigger = left_child else: bigger = right_child if(arr[parent]<arr[bigger]): self.swap(parent,bigger) parent = bigger else: break elif(left_child<=end): #has one child if(arr[parent]<arr[left_child]): self.swap(left_child,parent) parent = left_child else: # bigger than left child break else: #has no children break if __name__ == "__main__": arr = [9,8,7,6,4,5] h = heap(arr) h.insert(100) print h.arr print(h.pop()) print h.arr print(h.pop()) print h.arr 3. 归并排序： def merge(left,right): tmp = [] while(left and right): if(left[0]>right[0]): #将left or right 中,较大的元素弹入tmp;只能从前往后比较，因为每个子序列都是从小到大排列的。 tmp.append(right.pop(0)) else: tmp.append(left.pop(0)) if(left): #将剩余的元素弹入tmp for i in left: tmp.append(i) else: for i in right: tmp.append(i) return tmp def merge_sort(arr): if(len(arr)<=1): return arr mid = len(arr)/2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) res = merge(left,right) return res if __name__ == "__main__": arr = [34,54,94,62,56,46,6,2] print merge_sort(arr)