Ruby实现merge_sort算法离开输入数组中的元素

我想实现合并排序功能到我的应用程序。它将一个数组作为输入，对它进行排序并输出排序后的数组。Ruby实现merge_sort算法离开输入数组中的元素

def sort(list) 
    swapped = true 
    sorted_list = [] 

    slice_count = list.size.to_i 
    chunked_list = list.each_slice(slice_count).to_a.each{ |element| element.fill nil, slice_count, 0 }.transpose.map(&:compact) 

    while swapped do 
    swapped = false 

    (slice_count-1).times do |i| 
     if chunked_list[i][0] > chunked_list[i+1][0] 
     chunked_list[i], chunked_list[i+1] = chunked_list[i+1], chunked_list[i] 
     swapped = true 
     end 
    end 
    break if !swapped 
    end 

    (slice_count-1).times do |i| 
    sorted_list.push(chunked_list[i][0]) 
    end 

    puts "Sorted list (merge): #{sorted_list}" 
end

我的问题来自获取输入数组。运行merge.sort（[0，3,8，5,4，9，22]）输出排序后的数组，而不0和22：Sorted list (merge): [3, 4, 5, 8, 9]

调试并返回在撬的 '列表' 变量给我[3, 4, 5, 8, 9, 22] ，其中包括最终输出中不存在的22个，但仍然不包括输入数组中的0元素。为什么它没有采取完整阵列？

来源

2017-03-16 Sam Lim

我有一个问题上是，如果这个功能真的认为合并排序？在while循环之后，它将数组分解为[[0]，[3]，[4]，[5]，[8]，[9]，[22]]。不应该将它分解为2个数组[[0,3,4]，[5,8,9,22]]，以被视为合并排序？ –

合并排序有两个问题：1）它是一种冒泡排序，而不是合并排序; 2）一个错误的错误。 –

正确，但不合并排序分成2，然后3，依此类推，直到每个元素都在它自己的数组中？一旦它们都被分解成单个的块，你会比较吗？ @JörgWMittag –

您需要删除 - 上（slice_count）.times 1做

def sort(list) 
    swapped = true 
    sorted_list = [] 

    slice_count = list.size.to_i 
    chunked_list = list.each_slice(slice_count).to_a.each{ |element| element.fill nil, slice_count, 0 }.transpose.map(&:compact) 

    while swapped do 
    swapped = false 

    (slice_count-1).times do |i| 
     if chunked_list[i][0] > chunked_list[i+1][0] 
     chunked_list[i], chunked_list[i+1] = chunked_list[i+1], chunked_list[i] 
     swapped = true 
     end 
    end 
    break if !swapped 
    end 

    (slice_count).times do |i| 
    sorted_list.push(chunked_list[i][0]) 
    end 

    puts "Sorted list (merge): #{sorted_list}" 
end 

Sorted list (merge): [0, 3, 4, 5, 8, 9, 22]

来源

2017-03-16 19:12:31

这看起来很像泡泡排序，你确定它是合并排序吗？ –

Ruby实现merge_sort算法离开输入数组中的元素

回答

相关问题