利用python实现4中插入类排序算法，希尔排序，直接插入排序，二路插入排序，折半插入排序

Sort Algorithms

#!/usr/bin/python

class SortAlgorithms: 
  #direct insertion sort
  def insertion_sort(self,data):
    for index in range(1,len(data)):
      for inner_index in range(0,index):
        if data[inner_index] >= data[index]:
          data.insert(inner_index,data[index])
          del(data[index+1])
    return data
  
  #shell sort
  def shell_sort(self,data,increment):
    len_data = len(data)
    len_increment = len(increment)

    for k in range(0,len_increment):
      for i in range(increment[k],len_data):
        tmp = data[i]
        j = i
        while j >= increment[k]:
          if tmp >= data[j - increment[k]]:
            break
          else:
            data[j] = data[j - increment[k]]
          j -=increment[k]

        data[j] = tmp

    return data

  #binary sort
  def binary_sort(self,data):
     for i in range(1,len(data)):
      tmp = data[i]
      low = 0
      high = i -1
       
      while low<=high:
        mid = (low + high) >> 1
        if tmp < data[mid]:
          high = mid - 1
        else:
          low = mid + 1

      j = i -1
      while j>=low:
        data[j+1] = data[j]
        j -=1
       
      data[low] = tmp
     return data
   
  #two way sort
  def two_way_sort(self,data):
    first,final = 0,0
    temp = [0,0,0,0,0,0,0,0,0,0,0]
    temp[0] = data[0]
    result = [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]
    length = len(data)

    for i in range(1,length):
      if data[i]>=temp[final]:
        final +=1
        temp[final] = data[i]
      elif data[i]<= temp[first]:
        first = (first -1 + length)%length
        temp[first] = data[i]
      else:
        if data[i]<temp[0]:
          low = first
          high = length -1
          
          while low <=high:
            m = (low + high)>>1
            if data[i]>temp[m]:
              low = m + 1
            else:
              high = m -1

          j = first - 1
          first -=1
          while j < high:
            temp[j] = temp[j+1]
            j +=1
  
          temp[high] = data[i]

        else:
          low =0
          high = final

          while low <=high:
            m =(low + high)>>1

            if data[i]>=temp[m]:
              low = m + 1
            else:
              high = m - 1

          j = final + 1
          final +=1

          while j > low:
            temp[j] = temp[j-1]
            j -=1

          temp[low] = data[i]

    i = 0
    for j in range(first,length):
      result[i] = temp[j]
      i +=1

    for j in range(0,final + 1):
      if i>=length - 1:
        break
      result[i] = temp[j]
      i +=1

    return result


data = [4,23,1,54,94,2,15,0,11,345,322]
print "Before sort is: ",data
sort = SortAlgorithms()
insertionSortResult = sort.insertion_sort(data)
print "Insertion Sort: ",insertionSortResult
binarySort = sort.binary_sort(data)
print "Binary Sort: ",binarySort
two_way_sort = sort.two_way_sort(data)
print "Tow way Sort: ",two_way_sort
increment = [5,3,1]
shell_sort = sort.shell_sort(data,increment)
print "Shell Sort: ", shell_sort