3.27《算法圖解》筆記——Chapter 2 Choose Sorting

算法圖解筆記——Chapter 2 Sorting

Author: Seven Zou

Email: [email protected]

Language: Python2.7

2 排序算法

• 學習兩種最基本的資料結構——數組和連結清單，它們無處不在。第一章使用了數組，其他章也幾乎都将用到數組。數組是個重要的主題，但在有些情況下，使用連結清單比使用數組更合适。
• 學習排序算法、快速排序算法。排序算法包含冒泡排序，選擇排序，快速排序，歸并排序，堆排序等。選擇排序是包括快速排序的基石。快速排序是一種重要的算法。

2.1數組和連結清單

數組：元素是在一起的。可以了解為将資料按照固定順序排列好，且同一數組内所有元素都必須相同(都為int、double等)。

連結清單：元素是分開的。可以了解為每個元素都存儲了下一個元素的位址，進而使得一系列随機的位址串在一起。

e.g.如果想在位址中插入一個元素，那麼連結清單不需要移動元素而将位址存儲到前一個元素中即可，而數組則需要移動。 在數組中的元素，是帶編号的且從0開始。元素的位置(編号)被稱為 索引。

數組元素	1	2	3	4	5	6
索引編号	1	2	3	4	5

運作時間	數組	連結清單
讀取	O ( 1 ) {O(1)} O(1)	O ( n ) {O(n)} O(n)
插入	O ( n ) {O(n)} O(n)	O ( 1 ) {O(1)} O(1)
删除	O ( n ) {O(n)} O(n)	O ( 1 ) {O(1)} O(1)

Remark: O ( 1 ) {O(1)} O(1)表示常量時間； O ( n ) {O(n)} O(n)表示線性時間。

2.2選擇排序

假如要對一個清單中(1-n)數從小到大排列則共有n次，是以需要的總時間為 O ( n × n ) O(n \times n) O(n×n)，即 O ( n 2 ) O(n^2) O(n2)。

98	1	1
76	…	98	…	…
47	==>	76	==>	…
…	…	…	…	…
19	…	…	n
O ( n ) O(n) O(n)	O ( n ) O(n) O(n)	O ( n ) O(n) O(n)

Remark: 對于 O ( n × n ) O(n \times n) O(n×n)，第一次檢查 n n n個元素，但之後依次遞減， n − 1 、 n − 2 、 . . . 、 2 、 1 n-1、n-2、...、2、1 n−1、n−2、...、2、1。則平均每次檢查 1 / 2 × n 1/2 \times n 1/2×n，則運作時間實際為 O ( n × 1 / 2 × n ) O(n \times 1/2 \times n) O(n×1/2×n)，在大O表示法中省略 1/2 這樣的常數，故寫作 O ( n × n ) O(n \times n) O(n×n)( O ( n 2 ) O(n^2) O(n2))。

附Case的Code：

# -*- coding: utf-8 -*-
# 用來找出數組中最小元素的函數 
def findSmallest(arr):     
	smallest = arr[0]   # 存儲最小的值     
	smallest_index = 0  # 存儲最小元素的索引     
	for i in range(1, len(arr)):         
		if arr[i] < smallest:             
			smallest = arr[i]             
			smallest_index = i     
	return smallest_index 
# 選擇排序算法 
def selectionSort(arr): # 對數組進行排序     
	newArr = []     
	for i in range(len(arr)):         
		smallest = findSmallest(arr)    # 找出數組中最小的元素，并将其加入到新數組中         
		newArr.append(arr.pop(smallest))    
	return newArr  
# 測試
print selectionSort([5,3,6,2,10])
           

2.3快速排序

快速排序是一種更快的排序算法，其運作時間為 O ( n l o g n ) O(nlog^n) O(nlogn)。

在學習快速排序算法之前，需了解 遞歸 概念，則明天再進行補充學習，待更。

Reference

[美]Aditya Bhargava/袁國忠, 算法圖解, 北京：人民郵電出版社, 2017.3.

Note: 開始學習使用Github來管理自己的Code了。

附Github位址: https://github.com/shiqi0404/Algorithm_Diagram，其中包括筆記、Code還有書本pdf版。