Author Archives: neohope

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

1、Bubble sort 冒泡排序

  # Bubble sort 冒泡排序
  # 每次扫描，比较和交换相邻元素，保证一次扫描后，最大元素在最后一个
  # 每次扫描后，扫描队列长度减一
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  def bubble_sort(container)
    swap=true
    while(swap)
      swap=false
      for i in 0..(container.size-1) do
        for j in 0..i do
          if(container[i]<container[j])
            r=container[j]
            container[j]=container[i]
            container[i]=r
            swap=true
          end
        end
      end
    end

    return container
  end

2、Selection sort 选择排序

  # Selection sort 选择排序
  # 从头扫描到尾，每次将最小元素放到第一个
  # 每次扫描后，队列长度减一
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  def selection_sort(container)
    for i in 0..container.size-1 do
      min = i
      for j in i..container.size-1 do
        if(container[min]>container[j])
          min=j
        end
      end

      r=container[i]
      container[i]=container[min]
      container[min]=r

    end

    return container

  end

3、Insertion sort 插入排序

  # Insertion sort 插入排序
  # 起始队列长度为1，每次向队列增加1个数字
  # 通过元素移动，将队列调整为有序状态
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  def insertion_sort(container)
    if container.size <2
      return container
    end

    for i in 1..container.size-1 do
      val = container[i]
      j=i-1
      while(j>=0 and container[j]>val) do
        container[j+1]=container[j]
        j=j-1
      end

      container[j+1] = val
    end

    return container
  end

4、Shell Sort 希尔排序

  # Shell Sort 希尔排序
  # 指定一个步长，将需要排序的数字，按序号%步长分组
  # 对每组进行插入排序，然后减小步长，再次分组，排序
  # 直到步长为1结束
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  def shell_sort(container)
    step = container.size/2
    while step>0 do
      for i in step..container.size-1 do
        val= container[i]
        j=i-step
        while(j>=0 and container[j]>val) do
          container[j+step] = container[j]
          j=j-step
        end
        container[j+step]=val
      end

      #puts(">>")
      #puts(container)

      step = step/2
    end

    return container
  end

5、Merge sort 归并排序

  # Merge sort 归并排序
  # 二路归并首先将归并长度定为2，在归并集内进行排序
  # 然后归并长度×2，将有序集合进行归并
  # Time Complexity: О(nlogn) average and worst-case
  # Space Complexity: О(n) auxiliary
  # Stable: Yes
  def mergesort(container)
    return container if container.size <= 1

    mid = container.size / 2
    left = container[0...mid]
    right = container[mid...container.size]

    merge(mergesort(left), mergesort(right))
  end

  private

  def merge(left, right)
    sorted = []
    until left.empty? or right.empty?
      left.first <= right.first ? sorted << left.shift : sorted << right.shift
    end
    sorted + left + right
  end