选择排序
第一轮:将数组的第一个值和后面的值做比较,如果后面值比第一个值小,则互换位置,然后将已经换了位置的第一位继续和剩余的数值做比较。第二轮:获取数组的第二个位置,重复第一轮的操作。复杂度大O表示法为n2。
# 选择排序
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表示法为n2
# 插入排序
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表示法为n2
#冒泡排序
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
快速排序
说明:取得数组中一个值,将这个值和数组中的其他值进行排列,比这个值小的数排在数的左边,比这个值大的数排在这个值的右边,对右边两边的数执行同样的操作。