本篇內(nèi)容介紹了“Java算法和排序的介紹及使用”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),訥河企業(yè)網(wǎng)站建設(shè),訥河品牌網(wǎng)站建設(shè),網(wǎng)站定制,訥河網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷(xiāo),網(wǎng)絡(luò)優(yōu)化,訥河網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專(zhuān)業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

一、前言

什么是算法?算法是某種集合，是簡(jiǎn)單指令的集合，是被指定的簡(jiǎn)單指令集合。確定該算法重要的指標(biāo)：

• 第一是否能解決問(wèn)題；

• 第二算法運(yùn)行時(shí)間，即解決問(wèn)題出結(jié)果需要多少時(shí)間；

• 還有所需的空間資源，比如內(nèi)存等。

很多時(shí)候，寫(xiě)一個(gè)工作程序并不夠。因?yàn)橛龅酱髷?shù)據(jù)下，運(yùn)行時(shí)間就是一個(gè)重要的問(wèn)題。

算法性能用大 O 標(biāo)記法表示。大 O 標(biāo)記法是標(biāo)記相對(duì)增長(zhǎng)率，精度是粗糙的。比如 2N 和 3N + 2 ，都是  O(N)。也就是常說(shuō)的線性增長(zhǎng)，還有常說(shuō)的指數(shù)增長(zhǎng)等。

典型的增長(zhǎng)率

典型的提供性能做法是分治法，即分支 divide and conquer 策略：

1. 將問(wèn)題分成兩個(gè)大致相等的子問(wèn)題，遞歸地對(duì)它們求解，這是分的部分；

2. 治階段將兩個(gè)子問(wèn)題的解修補(bǔ)到一起，并可能再做些少量的附加工作，最后得到整個(gè)問(wèn)題的解。 

二、排序

排序問(wèn)題，是古老，但一直流行的問(wèn)題。從 ACM 接觸到現(xiàn)在工作，每次涉及算法，或品讀 JDK 源碼中一些算法，經(jīng)常會(huì)有排序的算法出現(xiàn)。

排序算法是為了將一組數(shù)組(或序列)重新排列，排列后數(shù)據(jù)符合從大到小(或從小到大)的次序。這樣數(shù)據(jù)從無(wú)序到有序，會(huì)有什么好處?

• 應(yīng)用層面：解決問(wèn)題

• 最簡(jiǎn)單的是可以找到最大值或者最小值

• 解決"一起性"問(wèn)題，即相同標(biāo)志元素連在一起

• 匹配在兩個(gè)或者更多個(gè)文件中的項(xiàng)目

• 通過(guò)鍵碼值查找信息

• 系統(tǒng)層面：減少系統(tǒng)的熵值，增加系統(tǒng)的有序度 (Donald Knuth 的經(jīng)典之作《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》(The Art of Computer  Programming)的第三卷)

通過(guò)維基百科查閱資料得到：在主內(nèi)存中完成的排序叫做，內(nèi)部排序。那需要在磁盤(pán)等其他存儲(chǔ)完成的排序，叫做外部排序 external sorting。

接口是一個(gè)抽象類(lèi)型，是抽象方法(compareTo)的集合，用 interface 來(lái)聲明。因此被排序的對(duì)象屬于 Comparable 類(lèi)型，即實(shí)現(xiàn)  Comparable 接口，然后調(diào)用對(duì)象實(shí)現(xiàn)的 compareTo 方法進(jìn)行比較后排序。

在這些條件下的排序，叫作基于比較的排序(comparison-based sorting)

三、插入排序

白話文：熊大(一)、熊二、熊三... 按照身高從低到高排隊(duì)(排序)。這時(shí)候熊 N  加入隊(duì)伍，它從隊(duì)伍尾巴開(kāi)始比較。如果它比前面的熊身高低，則與被比較的交換位置，依次從尾巴到頭部進(jìn)行比較 & 交換位置。最終換到了應(yīng)該熊 N  所在的位置。這就是插入排序的原理。

插入排序(insertion sort)

最簡(jiǎn)單的排序之一。ps: 冒泡排序看看就好，不推薦學(xué)習(xí)。

由 N - 1 次排序過(guò)程組成。

如果被排序的這樣一個(gè)元素，就不需要排序。即 N =1 (1 - 1 = 0)

每一次排序保證，從第一個(gè)位置到當(dāng)前位置的元素為已排序狀態(tài)。

如圖：每個(gè)元素往前進(jìn)行比較，并終止于自己所在的位置。

代碼解析如下：

• 從數(shù)組的第二個(gè)元素，向前開(kāi)始比較。比第一個(gè)元素小，則交換位置

• 如果第二個(gè)元素比較完畢，那就第三個(gè)，第四個(gè)... 以此類(lèi)推

• 比較到最后一個(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)的異曲同工。這邊就不一行一行解釋了。

“Java算法和排序的介紹及使用”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！