归并排序算法分析

     今天上班没有什么事情需要处理，昨天刚好看在本书上看到归并排序就试着将其代码写了出来。尝试着进行一下分析！感觉从算法的描述到具体的代码，中间有不少细节需要注意。不如到底是小于还是小于等于，是该加一还是减一等等。怪不得有些公司面试时要求进行机试，其实这也是为了考察一个人的动手能了和对细节的处理能力！其实我也不喜欢机试，更别说是有些变态的让直接在纸上写代码的了。。。。

 

   归并排序算法的概念：

 

       归并排序其实是算法里边用的比较多的算法，是“分而治之思想 ”的典型应用。其基本思想是，将一些已排序的子文件进行合并得到一个完整的有序文件。归并是只要比较各子文件记录的关键码，其最小者就是全局最小者（相对于参与比较的字文件）；取出它后继续比较各子文件的第一个记录....如此下去就能完成排序任务。

 

 

   实现代码（经过测试）：

 

 

 
class MergeSorter

 public  #public methods
    #Appling Top-To-Down method to sort  array：
   def merger_sort_for_array(source_array,start_index,end_index)
         middle=0    
         if start_index< end_index
            middle=(start_index+end_index)/2           
            merger_sort_for_array(source_array,start_index,middle)
            merger_sort_for_array(source_array,middle+1,end_index)
            
            merge_sort(source_array,start_index,middle,end_index)
         end  
    end
 
   #Apping Down-To-Top method to sort array:
  def merger_sort_for_array2(source_array,end_index)
      length=1
     while length<end_index do
      merge_array(source_array,length,end_index)
      length *=2
     end
  end  

 
 private #Priavate methods
  def merge_sort(source_array, start_index, middle_index,end_index)
    first_begin=start_index
    second_begin=middle_index+1
    target_begin=0
    target_array=Array.new(end_index-start_index+1)
  
  #Based on the value copy the elements to temprary in sorted order.
  while first_begin<=middle_index  and  second_begin<=end_index 
          if source_array[first_begin] > source_array[second_begin] 
             target_array[target_begin]=source_array[second_begin]
             target_begin  =target_begin + 1
             second_begin  =second_begin + 1
          else 
             target_array[target_begin]=source_array[first_begin]
             target_begin  =target_begin + 1
             first_begin  =first_begin + 1           
          end    
   end
   
    #Copy the left part to temprary array if there are element left.   
    while first_begin<=middle_index do
           target_array[target_begin]=source_array[first_begin]
           first_begin =first_begin + 1
           target_begin +=1
    end  
        
    #Copy the right part elemnnts to temprary if there are element left.    
    while second_begin<= end_index do
        target_array[target_begin]=source_array[second_begin]
        second_begin =second_begin + 1
        target_begin +=1
      end
    
    #Copy the result back to the source array 
    i=start_index
    p=0
    while   i<=end_index do
       source_array[i]=target_array[p]
       p +=1
       i +=1
    end
  end


#Do a single trip sorting
def merge_array(source_array,length,end_index)
  start_index=0 
  while( start_index+2*length-1<=end_index) do
    merge_sort(source_array,start_index,start_index+length-1,start_index+2*length-1)
    start_index +=2*length
  end
   
  #There are tow data parts left ,and the last parts' length is less than length.
  if (start_index+length-1)<end_index  
     merge_sort(source_array,start_index,start_index+length-1,end_index)
  end
 end  

end 
 
 
 #Test code:
 sorter=MergeSorter.new() 
 source_array=[1,3,2,5,7,6,2,8,4,-6,12]
 source_array2=[1,3,2,5,7,6,2,8,4,-6,12]

 sorter.merger_sort_for_array2(source_array,10)
 puts source_array
  
 sorter.merger_sort_for_array(source_array2 , 0 , 10)  
 puts source_array2
  

 

 

   使用预定义数组的实现：

 

   该实现的时间开销为n*log(n) ,空间开销为O（n）既辅助数组的大小。

 

#Merge Sort
class Sorter
def  do_merge_sort(source_array,start_index,middle,end_index,target_array)
     
     first_index=start_index
     second_index=middle+1
     position=start_index
     while first_index<=middle and second_index<=end_index do
     
             if source_array[first_index] <source_array[second_index]
                target_array[position]=source_array[first_index]
                first_index  =first_index+1
             else
                target_array[position]=source_array[second_index]
                second_index  =second_index+1
              end 
             position  =position+1
    end
           
     while first_index<=middle do
        target_array[position]=source_array[first_index]
        position  +=1
        first_index  +=1
      end
      
    while second_index<=end_index do
        target_array[position] =source_array[second_index]
        position  +=1
        second_index  +=1
    end
  end  
  
def   merge_sort(source_array,start_index,end_index,target_array)
  
    if start_index==end_index
      target_array[start_index]=source_array[end_index]
    else        
      middle=(start_index+end_index)/2
      merge_sort(source_array,start_index,middle,target_array)
      merge_sort(source_array,middle+1,end_index,target_array)
     
     #First sort the target_array
      do_merge_sort(source_array,start_index,middle,end_index,target_array)
      #Then copy the sorted target_array to source_array
      do_merge_sort(target_array,start_index,middle,end_index,source_array)
      
    end
end 
end

source=[1,3,2,4,7,2,0,-2]
target=Array.new(8,0)

sorter=Sorter.new()
sorter.merge_sort(source,0,7,target)

print source
puts ""
print target

 

 

   算法分析和讨论：

         本实现使用了同一种思想的两种不同的实现，一个是自顶而下，一个是自底而上的。两种算法的时间复杂度都是n*Log(n).空间复杂度也是n*Log(n)，因为每一趟的排序过程中要建立临时的数组，其空间大小基本上和待排序数组一致。

         还有另外其他的一些实现方式，比如可以预先创建一个辅助数组，大小和待排序的数组一样大。通过该辅助数组可以降低算法的空间复杂度，既O(n).但是这会使的算法的可理解性下降。所以在实际应用时，根据具体的需要选择不同的算法实现。一般情况下对算法的可理解行要求不该，可以使用预创建的辅助数组降低空间开销，但是如果程序对空间开销要求不高，建议使用可理解行高的算法实现。

 

   总结：

          一种算法思想可以有不同的实现，实现之间的空间开销和时间开销个不相同。因此我们要根据需要仔细选择算法实现。