按字母顺序排列数组而不使用排序方法

Question

我一直在研究Chris Pine的Ruby教程，目前正在研究一种不使用sort来排序名称数组的方法。

我的代码如下。它完美的工作，但是比我想象的还要进一步！

puts "Please enter some names:" 

name = gets.chomp 

names = [] 

while name != '' 

    names.push name 

    name = gets.chomp 

end 

names.each_index do |first| 
    names.each_index do |second| 
     if names[first] < names[second] 
      names[first], names[second] = names[second], names[first] 
     end 

    end 
end 

puts "The names you have entered in alphabetical order are: " + names.join(', ') 

这是排序，我有麻烦得到我的头。

我的理解是，each_index会查看数组中每个项目的位置。然后if语句获取每个项目，如果该数字大于下一个项目，则将其交换到数组中，继续执行此操作，直到最大数字处于起始位置。我会认为这只是颠倒了我的数组，但它按字母顺序排序。

有人能够跟我说说这个算法是如何按字母顺序工作的，以及它在什么时候看着什么开始的字母？

在此先感谢您的帮助。我相信这是非常简单的事情，但经过多次搜索，我无法弄清楚它！

Answer 1

我认为快速排序算法是比较容易的人的一个认识：

def qsort arr 
    return [] if arr.length == 0 
    pivot = arr.shift 
    less, more = arr.partition {|e| e < pivot } 
    qsort(less) + [pivot] + qsort(more) 
end 

puts qsort(["George","Adam","Michael","Susan","Abigail"]) 

的想法是，你挑一个元素（通常称为支点），然后将阵列划分为小于元素枢轴和那些大于或等于枢轴的枢轴。然后递归地对每个组进行排序并与枢轴结合。

Answer 2

你的理解只是一点点。

你说：

然后if语句需要的每一项，如果数量大于下一个较大的它交换它的阵列

在但这不是if语句是什么这样做。

首先，包含它的两个块只是简单地设置迭代器first和second，它们每次都从该数组的第一个元素到最后一个元素进行计数。 （这效率很低，但我们稍后会讨论高效排序问题，或者只是看Brian Adkins的答案）。

当您到达if语句时，它不会比较索引本身，而是names它们在这些指数。

通过在if之前插入此行，您可以看到发生了什么。虽然这会让你的程序变得非常冗长：

puts "Comparing names[#{first}] which is #{names[first]} to names[#{second}] which is #{names[second]}..." 

Answer 3

我明白你为什么会感到困惑 - 我也是。看看算法在每次交换中的作用。我使用的是数字，而不是名称，使顺序清晰，但它适用于字符串以同样的方式：

names = [1, 2, 3, 4] 

names.each_index do |first| 
    names.each_index do |second| 
    if names[first] < names[second] 
     names[first], names[second] = names[second], names[first] 
     puts "[#{names.join(', ')}]" 
    end 
    end 
end 

=> 

[2, 1, 3, 4] 
[3, 1, 2, 4] 
[4, 1, 2, 3] 
[1, 4, 2, 3] 
[1, 2, 4, 3] 
[1, 2, 3, 4] 

在这种情况下，它开始与排序列表，然后做了一堆互换，然后把事情回来了。如果你只看看第一对互换，你可能会被愚弄到认为它会下降。并且比较（交换if names[first] < names[second]）当然似乎意味着降序排序。

诀窍是first和second之间的关系没有排序;有时候first在左边，有时候在右边。这使得整个算法很难推理。

这种算法，我想，一个奇怪的实现冒泡排序的，这是我常看到这样实现的：

names.each_index do |first| 
    (first + 1...names.length).each do |second| 
    if names[first] > names[second] 
     names[first], names[second] = names[second], names[first] 
     puts "[#{names.join(', ')}]" 
    end 
    end 
end 

如果您运行的排序数相同的阵列上运行此代码，它什么都不做：数组已经排序，所以它不交换任何东西。在此版本中，需要小心保持second始终在first的右侧，并且仅在first的值为时的值大于的值时才进行交换，而不是在second的值。因此，在第一阶段（其中first为0），最小数字在位置0处结束，在下一个阶段中，下一个最小数字处于下一个位置处，等等。

如果您在数组上运行它反向排序，你可以看到它正在做什么：

[3, 4, 2, 1] 
[2, 4, 3, 1] 
[1, 4, 3, 2] 
[1, 3, 4, 2] 
[1, 2, 4, 3] 
[1, 2, 3, 4] 

最后，这里的可视化正在发生的事情的两种算法的一种方式。首先修改版本：

0 1 2 3 
0 X X X 
1  X X 
2   X 
3 

沿着纵轴的数字代表first的值。水平方向的数字代表second的值。 X表示算法比较和潜在交换的点。请注意，它只是对角线上方的部分。

下面是你在你的问题中提供的算法相同的可视化：

0 1 2 3 
0 X X X X 
1 X X X X 
2 X X X X 
3 X X X X 

这个算法比较所有可能的位置（无意义包括沿对角线，其中first和second相等的值）。但要注意的重要一点是，发生在对角线下方和左侧的交换表示second位于first左侧的情况 - 反向情况。并且还要注意，这些案件在之后发生转发情况。

所以基本上，这个算法所做的是对数组进行反向排序（如您所怀疑的那样），然后然后然后将其排序。可能不是真正意图的，但代码确实很简单。

Answer 4

或者，您可以创建一个新数组并使用while循环来按字母顺序追加名称。删除循环中添加的元素，直到旧数组中没有元素。

sorted_names = [] 

while names.length!=0 
    sorted_names << names.min 
    names.delete(names.min) 
end 

puts sorted_names 

Answer 5

这是这种情况下

def my_sort(list, new_array = nil) 

    return new_array if list.size <= 0 
    if new_array == nil 
    new_array = [] 
    end 
    min = list.min 
    new_array << min 
    list.delete(min) 

    my_sort(list, new_array) 

end 

puts my_sort(["George","Adam","Michael","Susan","Abigail"]) 

Answer 6

这里递归溶液是我的代码不使用排序或分钟方法在阵列中的项目进行排序，并考虑到各种形式的每一个项（例如字符串，整数，零）：

def sort(objects) 
    index = 0 
    sorted_objects = [] 
    while index < objects.length 
     sorted_item = objects.reduce do |min, item| 
     min.to_s > item.to_s ? item : min 
     end 
     sorted_objects << sorted_item 
     objects.delete_at(objects.find_index(sorted_item)) 
    end 
    index += 1 
    sorted_objects 
end 



words_2 = %w{all i can say is that my life is pretty plain} 
p sort(words_2) 
=> ["all", "can", "i", "is", "is", "life", "my", "plain", "pretty", "say", "that"] 

mixed_array_1 = ["2", 1, "5", 4, "3"] 
p sort(mixed_array_1) 
=> [1, "2", "3", 4, "5"] 

mixed_array_2 = ["George","Adam","Michael","Susan","Abigail", "", nil, 4, "5", 100] 
p sort(mixed_array_2) 
=> ["", nil, 100, 4, "5", "Abigail", "Adam", "George", "Michael", "Susan"]