选择排序

第一轮：将数组的第一个值和后面的值做比较，如果后面值比第一个值小，则互换位置，然后将已经换了位置的第一位继续和剩余的数值做比较。第二轮：获取数组的第二个位置，重复第一轮的操作。复杂度大O表示法为n²。

# 选择排序
class Array
  def select_sort!
    len  = self.length
    0.upto(len - 1) do |i|
      min = i
      (i + 1).upto(len - 1) do |j|
        min = j if self[j] < self[min]
      end 
      #备注：从min=1到 min=j if self[j]<self[min]的时候已经完成了第一轮，即获取最小值，并且进行反复替换
      self[i], self[min] = self[min], self[i] if min != i
    end
    return self
  end
end


# 测试
arr = (1..10).to_a.shuffle
p arr

arr.select_sort!
p arr

插入排序

说明：将数组分为有序部分和无序部分，左边为有序部分a，右边为无序部分b，刚开始的时候可以认为有序部分为0，全都都为无序数组。第一轮，将无序部分的第一个数取出作为有序部分的值。第二轮，将无序部分的第二个值取出，和有序部分的数值进行比较排序，以此类推。复杂度大O表示法为n²

# 插入排序
class Array
  def insert_sort!
    len = self.length
    1.upto(len - 1) do |i|
      i.downto(1) do |j|
        self[j], self[j - 1] = self[j - 1], self[j] if self[j] < self[j -1]
      end
    end
  end
end


# 测试
arr = (1..10).to_a.shuffle
p arr

arr.insert_sort!
p arr

冒泡排序

说明：将数组分为有序部分和无序部分，右边为有序部分，左边为无序部分，刚开始的时候可以认为有序部分为0，全都都为无序数组。每次将有序部分的最大值移动到无序部分的左边第一个值。第一轮，从左至右两两比较数组的值，获得本数组的最大值，将这个最大的值作为有序数组的第一位排在最右边，以此类推。复杂度大O表示法为n²

#冒泡排序
class Array
  def bubble_sort!
    (self.length-2).downto(0) do |i|
      0.upto(i) do |j|
        self[j], self[j+1] = self[j+1], self[j] if self[j+1] < self[j]
      end
    end
    return self
  end
end


# 测试
arr = (1..10).to_a.shuffle
p arr

arr.bubble_sort!
p arr

#第二中写法，进行了优化，避免无意义的排序
class Array
  def bubble_sort
    n = self.length

    loop do
      swapped = false
      (n-1).times do |i|
        if self[i] > self[i+1]
          self[i], self[i+1] = self[i+1], self[i]
          swapped = true
        end
      end

      break if not swapped
    end

    self
  end
end

array = [9,8,7,6,5,4,3,2,1]
p array.bubble_sort

快速排序

说明：取得数组中一个值，将这个值和数组中的其他值进行排列，比这个值小的数排在数的左边，比这个值大的数排在这个值的右边，对右边两边的数执行同样的操作。