建站
咨詢
售后
建站咨詢
新聞中心
一、前言
成都創(chuàng)新互聯(lián)公司是一家業(yè)務(wù)范圍包括IDC托管業(yè)務(wù),虛擬主機(jī)、主機(jī)租用、主機(jī)托管，四川、重慶、廣東電信服務(wù)器租用,成都西云數(shù)據(jù)中心，成都網(wǎng)通服務(wù)器托管,成都服務(wù)器租用,業(yè)務(wù)范圍遍及中國(guó)大陸、港澳臺(tái)以及歐美等多個(gè)國(guó)家及地區(qū)的互聯(lián)網(wǎng)數(shù)據(jù)服務(wù)公司。
什么是算法?算法是某種集合，是簡(jiǎn)單指令的集合，是被指定的簡(jiǎn)單指令集合。確定該算法重要的指標(biāo)：
- 第一是否能解決問題；
- 第二算法運(yùn)行時(shí)間，即解決問題出結(jié)果需要多少時(shí)間；
- 還有所需的空間資源，比如內(nèi)存等。
很多時(shí)候，寫一個(gè)工作程序并不夠。因?yàn)橛龅酱髷?shù)據(jù)下，運(yùn)行時(shí)間就是一個(gè)重要的問題。
算法性能用大 O 標(biāo)記法表示。大 O 標(biāo)記法是標(biāo)記相對(duì)增長(zhǎng)率，精度是粗糙的。比如 2N 和 3N + 2 ，都是 O(N)。也就是常說的線性增長(zhǎng)，還有常說的指數(shù)增長(zhǎng)等。
典型的增長(zhǎng)率
典型的提供性能做法是分治法，即分支 divide and conquer 策略：
- 將問題分成兩個(gè)大致相等的子問題，遞歸地對(duì)它們求解，這是分的部分；
- 治階段將兩個(gè)子問題的解修補(bǔ)到一起，并可能再做些少量的附加工作，最后得到整個(gè)問題的解。
二、排序
排序問題，是古老，但一直流行的問題。從 ACM 接觸到現(xiàn)在工作，每次涉及算法，或品讀 JDK 源碼中一些算法，經(jīng)常會(huì)有排序的算法出現(xiàn)。
排序算法是為了將一組數(shù)組(或序列)重新排列，排列后數(shù)據(jù)符合從大到小(或從小到大)的次序。這樣數(shù)據(jù)從無序到有序，會(huì)有什么好處?
- 應(yīng)用層面：解決問題
- 最簡(jiǎn)單的是可以找到最大值或者最小值
- 解決"一起性"問題，即相同標(biāo)志元素連在一起
- 匹配在兩個(gè)或者更多個(gè)文件中的項(xiàng)目
- 通過鍵碼值查找信息
- 系統(tǒng)層面：減少系統(tǒng)的熵值，增加系統(tǒng)的有序度 (Donald Knuth 的經(jīng)典之作《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》(The Art of Computer Programming)的第三卷)
通過維基百科查閱資料得到：在主內(nèi)存中完成的排序叫做，內(nèi)部排序。那需要在磁盤等其他存儲(chǔ)完成的排序，叫做外部排序 external sorting。
接口是一個(gè)抽象類型，是抽象方法(compareTo)的集合，用 interface 來聲明。因此被排序的對(duì)象屬于 Comparable 類型，即實(shí)現(xiàn) Comparable 接口，然后調(diào)用對(duì)象實(shí)現(xiàn)的 compareTo 方法進(jìn)行比較后排序。
在這些條件下的排序，叫作基于比較的排序(comparison-based sorting)
三、插入排序
白話文：熊大(一)、熊二、熊三... 按照身高從低到高排隊(duì)(排序)。這時(shí)候熊 N 加入隊(duì)伍，它從隊(duì)伍尾巴開始比較。如果它比前面的熊身高低，則與被比較的交換位置，依次從尾巴到頭部進(jìn)行比較 & 交換位置。最終換到了應(yīng)該熊 N 所在的位置。這就是插入排序的原理。
插入排序(insertion sort)
最簡(jiǎn)單的排序之一。ps: 冒泡排序看看就好，不推薦學(xué)習(xí)。
由 N - 1 次排序過程組成。
如果被排序的這樣一個(gè)元素，就不需要排序。即 N =1 (1 - 1 = 0)
每一次排序保證，從第一個(gè)位置到當(dāng)前位置的元素為已排序狀態(tài)。
如圖：每個(gè)元素往前進(jìn)行比較，并終止于自己所在的位置。
代碼解析如下：
- 從數(shù)組的第二個(gè)元素，向前開始比較。比第一個(gè)元素小，則交換位置
- 如果第二個(gè)元素比較完畢，那就第三個(gè)，第四個(gè)... 以此類推
- 比較到最后一個(gè)元素時(shí)，完成排序
時(shí)間復(fù)雜度是 O(N^2)，最好情景的是排序已經(jīng)排好的，那就是 O(N)，因?yàn)闈M足不了循環(huán)的判斷條件;最極端的是反序的數(shù)組，那就是 O(N^2)。所以該算法的時(shí)間復(fù)雜度為 O(N^2)
運(yùn)行 main 方法，結(jié)果如下：
- [2, 3, 1, 4, 3]
- [1, 2, 3, 3, 4]
再考慮考慮優(yōu)化，會(huì)怎么優(yōu)化呢?插入排序優(yōu)化版 不是往前比較 。往前的一半比較，二分比較會(huì)更好。具體代碼，可以自行試試
四、Array.sort 源碼中的插入排序
上面用自己實(shí)現(xiàn)的插入算法進(jìn)行排序，其實(shí) JDK 提供了 Array.sort 方法，方便排序。案例代碼如下：
運(yùn)行 main 方法，結(jié)果如下：
- [2, 3, 1, 4, 3]
- [1, 2, 3, 3, 4]
那 Arrays.sort 是如何實(shí)現(xiàn)的呢?JDK 1.2 的時(shí)候有了 Arrays ，JDK 1.8 時(shí)優(yōu)化了一版 sort 算法。大致如下：
如果元素?cái)?shù)量小于 47，使用插入排序
如果元素?cái)?shù)量小于 286，使用快速排序
Timsort 算法整合了歸并排序和插入排序
源碼中我們看到了 mergeSort 里面整合了插入排序算法，跟上面實(shí)現(xiàn)的異曲同工。這邊就不一行一行解釋了。
五、小結(jié)
算法是解決問題的。所以不一定一個(gè)算法解決一個(gè)問題，可能多個(gè)算法一起解決一個(gè)問題。達(dá)到問題的最優(yōu)解。插入排序，就這么簡(jiǎn)單。
網(wǎng)站名稱：Java靜態(tài)內(nèi)部類、匿名內(nèi)部類、成員式內(nèi)部類和局部?jī)?nèi)部類
本文路徑：http://www.dlmjj.cn/article/cdohodh.html
