Ruby 实现各种排序查找算法

之前在微博上看到旧金山大学的David Galles教授用HTML5+js技术分别演示了6中数学排序算法的基本原理,便想用ruby分别实现这六种算法。

用HTML5实现的各种排序算法的动画比较

###冒泡排序

算法原理:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
1
2
3
4
5
6
7
8
9
10
#冒泡排序的算法复杂度为O(n^2)
def bubble_sort(list)
    list.each_index do |index|
        (list.length - index - 1).times do |e|
            if list[e] > list[e + 1]
                list[e], list[e + 1] = list[e + 1], list[e]
            end
        end
    end
end

直接插入排序

算法原理:

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

1
2
3
4
5
6
7
def straight_insertion_sort(list)
  (1...list.length).each do |i|
    temp = list[i]
    (0...i).each { |j| list[j], list[i] = list[i], list[j] if list[j] >= temp }
  end
  list
end

直接插入排序属于稳定的排序,最坏时间复杂性为O(n^2),空间复杂度为O(1)。

希尔排序

算法原理:

排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def shell_sort(list)
  d = list.length
  while d > 1
    d = d / 2
   (0...list.length).each do |i|
    (0...list.length-d).step(d) do |j|
     if list[j] >= list[j+d]
      list[j], list[j+d] = list[j+d], list[j]
     end
    end
   end
    break if d == 1
  end
  list
end

希尔排序的时间复杂度与增量序列的选取有关, 希尔排序的时间复杂度与增量序列的选取有关.

###快速排序

算法原理: 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 步骤:

  1. 从数列中挑出一个元素,称为 “基准”(pivot),
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
1
2
3
4
5
6
7
8
9
10
11
#快速排序的平均时间复杂度为O(nlogn)
def quicksort(list)
    return list if list.length <= 1
    pivot = list.pop
    less    ||= []
    greater ||= []
    (list - [pivot]).each do |element|
        element < pivot ? less << element : greater << element
    end
    quicksort(less) + [pivot] + quicksort(greater)
end

以上方法可以做进一步的简化:

1
2
3
4
5
6
7
def quicksort(list)
    return list if list.length <= 1
    pivot = list.pop
    #partition是一个迭代器,它返回两个数组,第一个数组包含了代码块中返回true的元素,第二个数组包含剩下的
    less, greater = list.partition { |e| e < pivot }
    quicksort(less) + [pivot] + quicksort(greater)
end

###直接选择排序

####算法原理

第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R[1]~R[n-1]中选取最小值,与R[1]交换,….,第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,…..,第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列

1
2
3
4
5
6
7
8
9
def straight_select_sort(array)
  return array if array.length == 0
  (0...array.length).each do |i|
    min, index = array[i], i
    (i...array.length).each { |j| min, index = array[j], j if array[j] < min }
    array[i], array[index] = array[index] , array[i]
  end
  array
end

平均时间复杂度为O(n^2)

###堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。

完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。

堆(二叉堆):二叉堆的数据结构是一个可以被看成是完全二叉树(或近似完全二叉树)的数组,二叉树的每一个节点都对应了数组中的一个元素。

大根堆和小根堆:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆,又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆,又称最大堆。

将数组转化为堆:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def make_min_heap(arr)
   (arr.length/2-1).downto(0).each do |i|
     puts i
     min_heap_fixdown(arr, i, arr.length)
   end
   arr
end

def min_heap_fixdown(arr, i, n)
   left = 2 * i + 1
   while(left < n)
     if left + 1 < n and arr[left] > arr[left + 1]
       left += 1
     end
     if arr[left] < arr[i]
      arr[left], arr[i] = arr[i], arr[left]
      i = left
      left = 2 * i + 1
     else
      break
     end
   end
end

puts make_min_heap([40, 10, 30, 15, 1]).inspect => [1, 10, 30, 15, 40]
puts make_min_heap([9,12,17,30,50,20,60,65,4,19]).inspect => [4, 9, 17, 12, 19, 20, 60, 65, 30, 50]

堆排序:

首先可以看到堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据,重复上述步骤直至堆中只有一个数据时就直接取出这个数据。由于堆也是用数组模拟的,故堆化数组后,第一次将A[0]与A[n - 1]交换,再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换,再对A[0…n - 3]重新恢复堆,重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间,故操作完成后整个数组就有序了。有点类似于直接选择排序。

1
2
3
4
5
6
7
8
9
def heap_sort(arr)
   (arr.length - 1).downto(0).each do |i|
     arr[i], arr[0] = arr[0], arr[i]
     min_heap_fixdown(arr, 0, i)
   end
   arr
end

puts heap_sort(make_min_heap([9,12,17,30,50,20,60,65,4,19])).inspect => [65, 60, 50, 30, 20, 19, 17, 12, 9, 4]

注意使用最小堆排序后是递减数组,要得到递增数组,可以使用最大堆。

堆排序的时间复杂度为O(NlogN)

###二分查找

####算法要求

  1. 必须采用顺序存储结构;
  2. 数组必须是有序的;

####算法原理

折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如 果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右 半部继续搜索x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search(list, len, key)
    left, right = 0, len - 1
    while left <= right
        mid = (left + right) >> 1
        if list[mid] == key
            return mid
        elsif list[mid] > key
            right = mid -1
        else
            left = mid + 1
        end
    end
    return -1
end
comments powered by Disqus