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()