List

Java 基本介紹 (6)

教學目標

初步了解 Java 程式語言中集合框架之演算法的基本概念與應用。

重點概念

在 Java 平台中提供以 Collections 框架為基礎的演算法功能,所謂 Collections 框架又稱為容器是指多個元素組合成單一物件,主要應用於儲存、檢索、操作和溝通聚合資料。一般來說在 Java 平台中清單元素皆會搭配 Collections 框架進行演算法的實作,其中演算法可以分為六大類:

  1. 排序
  2. 洗牌
  3. 搜尋
  4. 組成
  5. 例行性資料操作
  6. 尋找最大最小值

首先排序演算法主要是重新排列清單,使得清單中的元素根據排序關係按遞增排序,排序操作,主要是使用 Collections 框架中的 sort 方法,其中排序方式為優化之後的合併排序演算法 (TimSort),具有快速且穩定的特性,所謂快速是指保證在 nlog(n) 的時間內執行完成。所謂穩定是指不重新排列相等的元素,相等的元素排序之後會維持原先的先後順序。接著與排序相反的操作則是洗牌,洗牌演算法主要是破壞清單中可能存在的任何追蹤軌跡,一般來說其是基於隨機來源的輸入元素重新排列清單,主要是使用 Collections 框架中的 shuffle 方法應用於產生測試範例。

演算法 時間複雜度(最佳) 時間複雜度(平均) 時間複雜度(最差) 空間複雜度
Selection Sort Ω(n^2) Θ(n^2) O(n^2) O(1)
Bubble Sort Ω(n) Θ(n^2) O(n^2) O(1)
Insertion Sort Ω(n) Θ(n^2) O(n^2) O(1)
Tree Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(n)
Quick Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(log(n))
Merge Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n)
Heap Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1)
Tim Sort Ω(n) Θ(n log(n)) O(n log(n)) O(n)

再來搜尋演算法主要在已排序的清單中搜尋指定的元素,主要是使用 Collections 框架中的 binarySearch 方法,其中搜尋方式為以二元搜尋演算法。若清單中包含該搜尋的值,則返回其索引,若不存在,則返回值為 (-1 × 插入點-1),其中插入點是指值將新增至清單中的位置。

此外 Collections 框架中提供 frequency 方法了解清單組成的元素頻率,更進一步針對例行性資料操作提供演算法實作的方法,主要可以分為五種類型資料操作的方法,分別為:

  1. 反向(reverse): 反轉清單中所有元素的順序。
  2. 填充(fill): 覆蓋清單中具有指定值的每個元素。
  3. 複製(copy): 將來源清單複製至目的清單。
  4. 交換(swap): 交換清單中指定的元素位置。
  5. 加入全部(addAll): 將所有指定的元素新增至清單中。

最後 Collections 框架針對尋找最大最小值則提供最小值和最大值的演算法,以利取得最大和最小的元素,此外我們亦可以透過實作 Comparator 介面解決特殊情境應用的排序方式。

範例程式碼

檔案名稱

ATM.java

情境說明

在現實生活中我們透過 ATM 進行轉帳作業時會需要點選轉帳帳戶所屬的銀行代碼,此時畫面就需要顯示銀行代碼清單,並且為了讓使用者方便點選,將會進行排序處理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;
public class ATM {
public static void main(String[] args) {
String[] banks = {"004臺灣銀行"
,"008華南銀行"
,"005土地銀行"
,"006合庫商銀"
,"021花旗銀行"
,"009彰化銀行"
,"011上海銀行"
,"012台北富邦"
,"007第一銀行"
,"013國泰世華"
,"017兆豐商銀"};
List<String> list = Arrays.asList(banks);
Collections.sort(list);
System.out.println("自動提款機畫面上顯示銀行代碼:\n" + list );
}
}

執行結果

1
2
自動提款機畫面上顯示銀行代碼:
[004臺灣銀行, 005土地銀行, 006合庫商銀, 007第一銀行, 008華南銀行, 009彰化銀行, 011上海銀行, 012台北富邦, 013國泰世華, 017兆豐商銀, 021花旗銀行]

相關資源

Java 基本介紹 (4)

教學目標

初步了解 Java 程式語言中集合框架的基本概念。

重點概念

我們都曾聽過資料結構和演算法是程式語言的基礎,但是在 Java 程式語言是否有針對資料結構和演算法優化的框架能夠針對不同情境進行解決方案的應用呢? 事實上在 Java 程式語言中有提供 Collections 框架應用於表示和操作集合的架構,透過 Collections 框架就能夠讓程式設計師根據不同情境應用適當的資料結構和演算法之解決方案,Collections 框架主要包括三個部分,分別為:

  1. 介面: 主要是表示集合的抽像資料類型,透過介面能夠使得集合獨立於不同表示集合的細節而被進行資料操作的應用。
  2. 實作: 主要是專注於集合介面的實作,實作之後皆是可重用的資料結構
  3. 演算法: 主要是針對實作集合介面的物件進行實用的演算法

首先 Collections 框架中核心的集合介面主要分為兩大類,第一類是以 Collection 類別為基礎的介面,第二類是以 Map 類別為基礎的介面,其中第一類主要有四種介面,分別為:

  1. List: 可包含重複元素,並且有順序的集合。
  2. Set: 不包含重複元素的集合。
  3. Queue: 被使用於之前保存多個元素,會以先進先出 (FIFO) 的方式排序元素的集合。
  4. Deque: 被使用於之前保存多個元素,會以先進先出 (FIFO) 或後進先出 (LIFO) 的方式排序元素的集合。

第二類則主要是以 Map 介面為主,主要是將索引值 (Key) 對應至值 (Value) 的集合,其中索引值不能重複,此外 Sort 和 Map 介面的集合是不進行排序,因此 Java 程式語言針對 Sort 和 Map 介面的集合提供 SortedSet 和 SortedMap 的介面進行元素和索引值的排序應用。

總結採用 Collections 框架主要有二大優點,分別為:

  1. 減少程式開發的負擔,同時增加程式品質和效能: 透過 Collections 框架所提供實用的資料結構和演算法,同時實用的資料結構和演算法皆是以高品質與高效能的方式進行實作,同時每個介面的各種資料結構和演算法實作是可以互相切換。因此我們可以針對不同情境的問題立即轉換程式中的資料結構與演算法以利程式設計師更進一步改進程式的品質和效能。
  2. 減少學習與設計新 API 的負擔,同時允許不相關的 API 之間進行協同合作: 透過 Collections 框架所提供標準介面的集合操作,就能夠減少程式設計師學習與設計新 API 所造成的負擔,同時集合所提供的資料結構與演算法是可以重複使用。

相關資源