【程式】排序及搜尋－

排序(Sort)及搜尋(Search)大概是每個人學習程式設計的必修課程，像是排序演算法有Bubble Sort、Quick Sort、Merge Sort及Heap Sort等等，而搜尋最著名的方法就是二元搜尋(Binary Search)演算法，我們都知道基本原理，但真正在撰寫程式遇到時，還真的是懶得翻出以前的教課書把他們實做出來。

幸好，JAVA以及C++皆提供了現成的Sort以及Search函數或物件以供使用，JAVA的程式碼較為精簡，因此先以JAVA進行說明：

‧JAVA版

假設Foo物件定義如下：

class Foo {
    public final String name;
    public final int age;

    public Foo(String name,int age) {
       this.name = name;
       this.age = age;
    }

    public String toString() {
      return name + " " + age;
    }
}

有一個陣列foo：

Foo[] foo = new Foo[3];
foo[0] = new Foo("A",10);
foo[1] = new Foo("B",30);
foo[2] = new Foo("C",5);

欲將陣列foo以age由小到大排序，需先定義Foo物件的大小關係，如下所示：

class FooComparator implements Comparator {

public int compare(Object o1, Object o2) {
    int res = 0;
    if(o1 instanceof Foo && o2 instanceof Foo) //check if o1 and o2 is type of Foo
      res = ((Foo) o1).age - ((Foo) o2).age;

    return res;
}
}

FooComparator物件實做了介面Comparator ，Comparator 中預設的函式compare將會傳回兩物件o1及o2的比較結果，若傳回值為負，則代表o1 < 02，而正則帶表o1 > 02，0是o1 = 02，以FooComparator來說，若：

((Foo) o1).age - ((Foo) o2).age < 0 意即 o1 < o2
((Foo) o1).age - ((Foo) o2).age > 0 意即 o1 > o2
((Foo) o1).age - ((Foo) o2).age = 0 意即 o1 = o2

我們將Foo物件的大小關係定義完成後，即可使用java.util中的Arrays物件進行排序，Array.sort需傳入兩個參數，第一個為欲排序的陣列，第二個為陣列中物件的比較方式：

Arrays.sort(foo,new FooComparator());

for(int i = 0;i < foo.length;i++) //print results
   System.out.println(foo[i]);

會依序印出

C 5
A 10
B 30

將foo排序之後，若希望找出age為10的物件：

int fooindex = Arrays.binarySearch(foo,new Foo(null,30),new FooComparator());

if(fooindex >= 0)
    System.out.println(foo[fooindex]);

會印出

B 30

Array.binarySearch需傳入三個參數，第一個為欲搜尋的陣列，此陣列必須已被由小到大排序過，第二個為欲尋找的Key，在此例中因欲尋找age為30，所以起始一個新物件new Foo(null,30)當作Key，而第三個參數是物件的比較方法。

一般來說，若有找到符合key的物件，會傳回此物件在欲搜尋陣列中的位置(index)，若未找到則會傳回負值，以本例來說，會傳回fooindex = 2，代表age為30的物件是foo[2]，

‧C++版

C++也提供了搜尋及排序的函數，以C++將資料進行排序之前，需以標準樣本函式庫(Standard Template Library, STL)將資料儲存為Iterator，C++定義Foo物件如下：

class Foo {

private:
    char* name;
    int age;

public:
    Foo(char* name,int age) {
        int len = strlen(name) + 1;
        this->name = new char[len];
        strncpy(this->name,name,len);

        this->age = age;
    };

    ~Foo(void) {
        delete [] name;
    };

    char* getName(void) const {return name;}
    int getAge(void) const {return age;}

    void print(void) {
        printf("%s %d\n",name,age);
    }

};

進行搜尋之前，如JAVA中的搜尋一樣，需先定義物件之間的大小關係，若我們希望將age由小到大排序，定義函數compareAge如下：

bool compareAge(Foo* foo1,Foo* foo2) {

return foo1->getAge() < foo2->getAge();
}

在C++中僅以bool傳回值來代表比較結果，若傳回true則代表foo1 < foo2，false則代表foo1 >= foo2，定義Foo物件的大小關係之後，以三個Foo物件進行排序：

Foo foo1("A",10);
Foo foo2("B",30);
Foo foo3("C",5);
vector foo_v;

foo_v.insert(foo_v.end(),&foo1);
foo_v.insert(foo_v.end(),&foo2);
foo_v.insert(foo_v.end(),&foo3);

sort(foo_v.begin(),foo_v.end(),compareAge);

for(int i = 0;i < foo_v.size();i++)
foo_v[i]->print();

會印出

C 5
A 10
B 30

在此以vector儲存foo1、foo2及foo3，vector為STL中的一種儲存資料物件，使用方法請詳見STL的參考資料。宣告foo1、foo2及foo3之後，我們將foo_v的泛型類別設定為Foo*，以Foo的指標形式存入vector。

其中sort函數將foo_v中的所有物件進行排序，sort需傳入三個參數，第一個為Iterator中欲開始排序的位置，第二個為Iterator中欲結束排序的位置，第三個變數為物件之間比較的方法，為一函數指標。

將foo_v由小到大排序之後，若希望找出foo_v中age為30的物件，先定義Foo物件的比較方式equalFoo：

bool equalFoo(Foo* foo1,Foo* foo2) {
    return foo1->getAge() == foo2->getAge();
}

無論foo1和foo2的變數name內容為何，只要兩者age一致時傳回true，意即foo1 == foo2，則找出找出foo_v中age為30的物件程式碼如下：

Foo targe(NULL,30);
vector targe_v;
vector::iterator result;

targe_v.insert(targe_v.end(),&targe);

result = search(foo_v.begin(),foo_v.end(),targe_v.begin(),targe_v.end(),equalFoo);

if(result != foo_v.end())
    result[0]->print();

會印出

B 30

首先宣告欲搜尋的目標為targe(NULL,30)，並將此物件加入target_v中，接著使用二元搜尋函數search，需傳入五個參數，前兩個為欲被搜尋Iterator的開頭及結尾，分別foo_v.begin()及foo_v.end()，第三和第四個參數為欲搜尋的目標Iterator的頭和尾，也就是target_v.begin()和target_v().end()，第五個參數則是物間之間比較的方法，為一函數指標。

搜尋結果將會存回一個vector中的iterator，在這裡target_v中只有一個搜尋目標，所以上述程式碼僅列印第一個物件的結果（也就是result[0]->print()），值得注意的是，若target_v中包含多個目標，則search會試圖在foo_v中找出符合target_v的連續目標，並回存在result，而且search函數的使用時，欲被搜尋的Iterator可以是未被排序的，以增加使用上的方便性。

參考：
[1] J2Sdk API Spec：
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Arrays.html

[2] MSDN Library Oct 2005：
→ms-help://MS.MSDNQTR.2005OCT.1033/vcstdlib/html/vclrfAlgorithmSearch.htm
→http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang98/html/ALGORITH_SEARCH.asp