Human Sort

Human Sort (Luxury Sort)

http://www.sorting-algorithms.com/

因為在多數的演算法討論中(可以參考上面網站)，沒有看過我將要提到的這種實作方式。所以，我就自行實作，並且和其它的演算法比較，發現可以大幅減少執行時間。所以，在此和大家分享。

我們都知道演算法重視兩個基本要素: 空間和時間，隨著PC記憶體的容量加大，價格更便宜的趨勢之下，我們可以充份的利用空間，以提升執行效能。Human Sort(以下稱此演算法)就是基於此想法下推演出來的。

排序的過程如下:
1.配置一塊連續的陣列。
2.將要排序的數字，置入對應的陣列索引。例如: 數字5置入ordered[5]。
3.移除未配置數字的陣列索引。
4.排序完成。


以下是此演算法的Python實作:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def sort(number):
    gap = len(number)
    ordered = [None] * 100
    for k in range(gap):
        ordered[number[k]]  = number[k] ;
 
    return filter(None, ordered)
# EOF.

以下是此演算法的Scala實作:

/**
 * Human Sort Implement
 * @author Boris Lv
 * @since 2011/06/11
 */
object HumanSort {
def sort(number: List[Int]): Array[Int] = {
 val maxSize = 100
 val gap = number.length
 val all = new Array[Int](maxSize)
 val ordered = Nil
 for(i <- 0 until gap){
   all(number(i)) = number(i)
 }
 all.filter(s => s != 0)
}

    def main(args: Array[String]) {
   val ar = List(6, 2, 8, 5, 1)
   sort(ar).foreach(println)
    }
}

import org.junit._
import Assert._

class Tests {

  @Test def sample() {
    val result = HumanSort.sort( List(6, 2, 8, 5, 1) )
    result.foreach(println)
    assertArrayEquals(Array(1, 2, 5, 6, 8), result )
  }
}


此演算法具備的特點和先決條件有:
1.知道最大數，或者必須假設一個最大數。例如: 1,6,96此三個數排序，因為最大數為96，所以，我們會預先配置0-96的陣列空間。若完全不知道將要排序的數字(也許是動態產生的)，則必須假設一個最大數，例如所有數都定在3位數以下，則必須配置0-999的陣列空間。
2.數字不可重複，因為一個陣列放置一個對應的數，但可以加上一些前製或後製作業來改善此點。
3.記憶體要夠大，雖然使用完就可以回收(GC)，但排序的瞬間必須有足夠的空間。
4.大量數字排序時效果最顯著。
5.僅適用於正數和零。負數也要另外處理。

但這些先決條件都很容易實作，也不會影響效能太多。

我用 log 的方式，簡單的計算了執行的時間，發現用這種方式可以比所有教科書中的演算法，節省2倍以上的時間。