[重修] 計算機程式-6 Arrays

陣列(array) 應該是蠻簡單的一節, 教授還是細心的把範例一個一個跟同學過了. 心想難怪 台大同學的程式能力都蠻強的. 老師教的時候觀念清楚 完全不會混淆 聽一次就夠了.

基礎奠定的時候 就好! 上課也很認真 會不斷的問問題, "這樣寫 OK嗎?" 不斷的讓同學產生好奇心, 並且幾乎課本上的重點都講過一遍了. 聽完課 課本稍微看一下(每章幾天吧) 對重點就可以達到舉一反三的效果囉.

繼續整理,

1) 假設 a[6]; 那 a[9] = ?

答案是不確定, complie 也不會出錯. 因為memory本來就是連續的 只是答案應該不會是程式設計者想要的.

2) a[5] = {0,1,2,3,4}; 是ok的.

但是a[5] = {0,1,2,3,4,5}; 是會報 ERROR的喔!!

另外 a[]; 也是會報 ERROR 的, 值得一提的是 a[] = {0,1,2}; 就沒關係, 因為Complier會知道需要分配幾個memory block 就行了.

3) const int // 初始化後 不能再改. 常用來跟 arraySize 一起宣告, 增加程式可讀性.

4) 傳 array 到function 時, 一定是傳 pass-by-reference 所以可以在function 寫const 防止array 被複寫

void f( const int b[] , int sizeOfArray ){
....
}

5) 課本 P 312 insertion sort 改成 descending

很簡單, line_28 data[moveItem -1] > insert 改成小於 "<" 就搞定啦

Insertion sort,

https://en.wikipedia.org/wiki/Insertion_sort

時間複雜度	${\displaystyle O(n^{2})}$

空間複雜度	總共${\displaystyle O(n)}$ ，需要輔助空間${\displaystyle O(1)}$