排序算法Ruby Part2

6、Heap sort 堆排序

  # Heap sort 堆排序
  # 使用堆进行排序，每次重建堆后，将堆顶元素放到堆数组最后，
  # 堆数组长度减一
  # Time Complexity: О(nlogn) average and worst-case
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  def heapsort(container)
    return container if container.size <= 1
    
    buildheap(container)
    size = container.size
    while size > 0
      container[0], container[size-1] = container[size-1], container[0]
      size = size - 1
      heapify(container, 0, size)
    end
    
    return container
  end
  
  private
  
  # 重建堆
  # 某节点及其所有子节点，符合最大堆的特性
  def heapify(container, idx, size)
    left_idx = 2 * idx + 1
    right_idx = 2 * idx + 2
    bigger_idx = idx
    bigger_idx = left_idx if left_idx < size && container[left_idx] > container[idx]
    bigger_idx = right_idx if right_idx < size && container[right_idx] > container[bigger_idx]
    if bigger_idx != idx
      container[idx], container[bigger_idx] = container[bigger_idx], container[idx]
      heapify(container, bigger_idx, size)
    end
    return container
  end
  
  # 初始化最大堆，堆顶元素为container[0]
  # 元素i的左节点为2*i+1，元素i的右节点为2*i+2
  def buildheap(container)
    last_parent_idx = container.length / 2 - 1
    i = last_parent_idx
    while i >= 0
      heapify(container, i, container.size)
      i = i - 1
    end
  end

7、Quicksort 快速排序

  # Quicksort 快速排序
  # 用分治法进行排序，充分利用了每次比较的结果，
  # 每次排序都将排序对象分成了两组，分别进行排序
  # Time Complexity: О(n log n) average, O(n^2) worst-case
  # Space Complexity: О(n) auxiliary
  # Stable: No
  def quicksort(container)
    return container if container.size<2

    i=0
    j=container.size-1
    key=container[i]

    while(i<j) do
      while(i<j and container[j]>key) do
        j=j-1
      end
      if(i<j)
        container[i]=container[j]
        i=i+1
      end

      while(i<j and container[i]<key) do
        i=i+1
      end
      if(i<j)
        container[j]=container[i]
        j=j-1
      end
    end
    container[i]=key
    
    f= 0<=i ? quicksort(container[0,i+1]): nil
    t= i<=container.size-1 ? quicksort(container[i+1,container.size-1]): nil

    return t if(f==nil)
    return f if(t==nil)
    return f+t
  end

8、Counting Sort 计数排序

  # Counting Sort 计数排序
  # 计算最小值和最大值，利用标志位来标记元素出现次数
  # Time Complexity: О(n+k) for best, average and worst-case
  # Space Complexity: О(n+k) auxiliary
  # Stable: Yes
  def countingsort(container)
    min = container.min
    max = container.max
    counts = Array.new(max-min+1, 0)

    container.each do |n|
      counts[n-min] += 1
    end

    j=0
    for i in 0..counts.size-1 do
      if(counts[i]!=0)
        while(counts[i]>0) do
          container[j] = min+i
          counts[i]-=1
          j+=1
        end
      end

      i+=1
    end

    return container
  end

9、Radix Sort 基数排序

  # Radix Sort 基数排序
  # 从个位数进行进行排序，一直到最高位
  # Time Complexity: О(k*n) for worst-case
  # Space Complexity: О(k+n) for worst-case
  # Stable: Yes
  def radixsort(container)
    
    max = container.max
    d = Math.log10(max).floor + 1

    (1..d).each do |i|
      radix = []
      (0..9).each do |j|
        radix[j] = []
      end

      container.each do |n|
        kth = calckth(n, i)
        radix[kth] << n
      end
      
      container = radix.flatten
    end

    return container
  end

  private
  
  def calckth(n, i)
    while(i > 1)
      n = n / 10
      i = i - 1
    end
    n % 10
  end

10、Bucket sort 桶排序

  # Bucket sort 桶排序
  # 将数组分到有限数量的桶里，每个桶再进行排序
  # Time Complexity: О(n) for best, О(n+k) for average, O(n^2) for worst-case
  # Space Complexity: О(n*k) for worst-case
  # Stable: Yes
  def bucketsort(container)
    bucket = []
    (0..9).each do |j|
      bucket[j] = []
    end
      
    container.each do |n|  
      k = getfirstnumber(n)
      bucket[k] << n
    end  
    
    (0..9).each do |j|  
      bucket[j] = quicksortB(bucket[j])  
    end
    
    bucket.flatten  
  end

  private
  
  #假设都是两位正整数
  def getfirstnumber(n)  
    m = n/10
    m=0 if m<0
    m=9 if m>9
    
    return m
  end
  
  def quicksortB(container)  
    (x=container.pop) ? quicksortB(container.select{|i| i <= x}) + [x] + quicksortB(container.select{|i| i > x}) : []  
  end