常见排序算法的 Ruby 实现 Link to heading

关于排序，可以说是算法的入门问题。每个程序员都有所了解或者熟悉。常见的如冒泡排序、选择排序、快速排序等。下面我会用Ruby语言来实现几个常见的排序算法，并对算法原理，及代码实现思路做出解释。

冒泡排序 Link to heading

关于冒泡排序，多数朋友都有耳闻，这里列出维基百科对冒泡排序的解释以供了解及加深印象

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

好了，现在我们看一下冒泡排序的 Ruby 实现

# 冒泡排序 bubble sort

def bubble_sort(nums)
  loop do
    mark = 0
    (nums.length - 1).times do |i|

      if nums[i] > nums[i + 1]
        nums[i], nums[i + 1] = nums[i + 1], nums[i]
        mark = 1
      end
    end

    break if mark.zero?
  end

  nums
end

# p bubble_sort([9,8,2,7,4,6,5,3,1])
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

# 下面利用递归实现一个冒泡排序

def bubble_sort_by_recurve(nums)
   mark = 0

   (nums.length - 1).times do |i|
     if nums[i] > nums[i + 1]
       nums[i], nums[i + 1] = nums[i + 1], nums[i]
       mark = 1
     end
   end

   return nums if mark.zero?

   bubble_sort_by_recurve(nums)
end

# p bubble_sort_recurve([9,8,2,7,4,6,5,3,1])
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

选择排序 Link to heading

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序的代码实现:


# 选择排序
# 这里要先实现一个找出数组中最小值下标的函数
# 该函数实现相对简单这里不做过多解释

def find_smallest_index(nums)
  smallest_index = 0
  smallest = nums[0]
  nums.each_with_index do |num, index|
    if smallest > num
      smallest_index = index
      smallest = nums[index]
    end
  end

  puts "smallest num index : #{smallest_index}"
  smallest_index
end

def select_sort(nums)
  new_sort_nums = []

  # nums.each do |_num|
  #   puts "nums begin  : #{nums}"
  #   new_sort_nums << nums.delete_at(find_smallest(nums))
  #   puts "NUMS end: #{nums}"
  # end
  # 返回 [1, 2, 3, 4, 5], 丢掉了
  # 这里使用each 会出现提前结束的问题 后续要仔细看一下为什么

  # 这里的思路是:
  # 1. 依次找出原数组中最小值的下标
  # 2. 将原数组中最小值添加到新数组最后
  # 3. 将原数组最小值从原数组移除
  # 4. 返回新数组
  nums.length.times do |i|
    new_sort_nums << nums.delete_at(find_smallest_index(nums))
  end

  new_sort_nums
end

nums = [9,8,2,7,4,6,5,3,1]
select_sort(nums)
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

快速排序 Link to heading

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

  1. 首先设定一个分界值，通过该分界值将数组分成左右两部分.

  2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值.

  3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理.

  4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了.

# 快速排序
def quickly_sort(nums)
  return nums if nums.size < 2

  less_nums = nums.select{ |num| num if num < nums.first }
  greater_nums = nums.select{ |num| num if num > nums.first }

  quickly_sort(less_nums) + [nums.first] + quickly_sort(greater_nums)
end

nums = [2,3,5,7,6,4,9,8,1]
quickly_sort(nums)
# [1, 2, 3, 4, 5, 6, 7, 8, 9]