Tag Archive 'sort'

Posted By Mr. Thursday 在〈二元樹在排序的應用〉裡面,我們提到了演算法就是完成一件事情的步驟,資料結構則是和演算法搭配,讓步驟有運作的東西,像是刮鬍刀的步驟,會運作在刮鬍刀或是插頭上面。「樹」(tree) 是一種資料結構,有樹根樹枝,看起來像是倒立的一棵樹。二元數則是每個節點只有兩個分支的樹。此外,我們可以用二元樹這個資料結構,完成「排序」(sorting) 的演算法。下面是一段各種排序演算法的影片:   除了排序以外,今天要和各位介紹,當我們把資料用一棵樹排序之後,要如何進行搜尋?排序或是沒有排序,對搜尋的效率有甚麼樣子的影響?我們先看看下面這兩張圖,左邊是排序過程,右邊是搜尋過程的動畫:

Read Full Post »

Posted By Mr. Thursday 在〈由樹的前序、中序、後序走法來談資料結構〉文章裡面提到了演算法就像是做事情的方法,資料結構則是對應演算法可以運作的東西,譬如說刮鬍子有步驟一、步驟二、步驟三,但是要有刮鬍刀、插頭、以及鬍鬚,那些步驟才有運作的東西,甚至不同的刮鬍刀,也會讓同樣的步驟有不同的執行效率,或是連原來的步驟都要改變,譬如說不是電動刮鬍刀,原來步驟裡面插插頭的那一步,也就可以不用作了。演算法和資料結構之間的關係也是如此,譬如說排序的演算法,可以用不同的資料結構來實現,好的資料結構,可能某一種排序演算法最適合,對其他種排序演算法,可能反而讓速度變慢。 因此,演算法和資料結構,通常會一起考慮,而演算法每一步,也就是電腦可以實現的基本步驟所組成。譬如說兩個數字相加,或是把「樹」這個資料結構裡面的節點根據某種規則移動,都是電腦運算基本步驟所可以達成的。但是如果步驟是「改善排序的品質」的敘述,電腦可能就看不懂了,這時候就是程式設計師,把這些人看的懂的需求,轉換成電腦可以實現的步驟,也就是演算法和對應的資料結構,最後再用程式 (編程) (program),變成電腦真的可以執行的語言,達到最初想要執行的功能。那麼今天想要完成的功能是甚麼呢?「排序」,排序就是把原本雜亂無章的一堆東西,按照某種順序排好,譬如說圖書館裡面的書籍,按照書籍的編號有小到大排好,譬如說醫院的病歷,按照病歷號碼有小到大排好,譬如說一堆檔案,按照字母順序或是檔案時間順序有早到晚排好,這些都是排序的應用。那麼電腦要如何完成「排序」(sort) 這件工作呢?「二元樹」 (binary tree) 怎樣子應用在排序這項工作呢?

Read Full Post »