Python版插入排序和归并排序
jopen
12年前
由于写算法实验,用C++写的,最近学Python正好用Python实现熟练一下,发现简洁很多,用着太方便了
下面贴代码,这俩个排序比较简单,不加注释了。
#_*_coding:utf_8_ class Sort(): def __int__(self): self.array = [] self.size = 0 def InitArray(self): n = raw_input() self.size = int(n) for i in range(self.size): data = raw_input() data = int(data) self.array.append(data) def PrintArray(self): for i in range(self.size): print self.array[i] , print '\n' class MyInsertSort(Sort): def __init__(self): self.size = 0 self.array = [] #InitArray def insertSort(self): for i in range(1, self.size): key = self.array[i] j = i - 1 while j >= 0 and self.array[j] > key: self.array[j + 1] = self.array[j] j = j - 1 self.array[j + 1] = key #PrintArray def ExcuteInsertSort(self): self.InitArray() self.insertSort() self.PrintArray() #obj = MyInsertSort() #obj.ExcuteInsertSort() class MergeSort(Sort): def __init__(self): self.size = 0 self.array = [] self.B = [] def MergeSort(self, low, high): if low < high: mid = low + (high - low)/2 self.MergeSort(low, mid) self.MergeSort(mid+1, high) self.Merge(low, mid, high) def Merge(self, low, mid, high): i = low j = mid + 1 self.B = [] while i <= mid and j <= high: if self.array[i] <= self.array[j]: self.B.append(self.array[i]) i += 1 else: self.B.append(self.array[j]) j += 1 while i <= mid: self.B.append(self.array[i]) i += 1 while j <= high: self.B.append(self.array[j]) #???bug j += 1 index = 0 for i in range(low, high+1): self.array[i] = self.B[index] index += 1 def ExcuteMergeSort(self): self.InitArray() self.MergeSort(0, self.size-1) self.PrintArray() obj = MergeSort() obj.ExcuteMergeSort()