演算法——選擇排序
基本的數據結構有數組和鏈表，本文主要闡述一下數組和鏈表的優缺點。以及理解選擇排序。
數組和鏈表
內存就像是是一個一個的抽屜，每一格抽屜有一個地址。需要存儲空間時，計算機會給一個存儲地址，就相當於將數據存在一個抽屜中。
數組和鏈表是基本的存儲方式，它們有各自的優缺點。
使用數組意味著所有的數據在內存中是相連的。而鏈表的元素可以存儲在內存沒有被佔有的任何空間內，鏈表的每個元素都存儲了下一個元素的地址，從而使得一系列的隨機的內存地址串在了一起。
只要有足夠的內存空間，就能為鏈表分配內存。
當同時讀取所有元素時，鏈表的效率很高。但當你需要跳躍讀取，也就是查詢時，鏈表的效率就很低了。
數組，則很方便讀取每一個元素的內容。因為知道第一個，就知道了所有的地址。它們是連在一起的。
插入多，讀取少，用鏈表；插入少，讀取多，用數組。
插入數據時：鏈表更方便，只需要修改它前面的那個元素指向的地址就可以了。而使用數組時，必須將後面的元素都向後移動。如果空間不足，還要重新複製新的空間。
刪除數據時：鏈表更好一些。只需要將前一個元素指向的地址更改即可。使用數組，則必須將後面的元素都向前移動。
不過因為數組支持隨機訪問，所以在很多情況下為了能獲得更快的讀取速度，還是使用數組。
選擇排序
選擇排序的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。
O(n)意味著查看列表中每個元素一次的話，選擇排序的時間複雜度為O(n*n)，也就是O(n2)
選擇排序的代碼為：
小結
計算機內存猶如一大堆抽屜。
需要存儲多個元素時，可使用數組或鏈表。
數組的元素都在一起。
鏈表的元素是分開的，其中每個元素都存儲了下一個元素的地址。
數組的讀取速度很快。
鏈表的插入和刪除速度很快。
在同一個數組中，所有元素的類型都必須相同（都為int、double等）。
TAG:代碼綜合征 |