從古至今的難題
在IT屆有一道百算不厭其煩的題幽歼，俗稱排序。不管是你參加BAT等高端筆試捞高，亦或是藏匿于街頭小巷的草根筆試氯材，都會經(jīng)常見到這樣一道百年難得一解的問題。
今天有幸與各位分享一下算法屆的草根明星硝岗，排序?qū)玫念I(lǐng)銜大神——插入排序以及歸并排序氢哮。最后，在頭腦風暴下型檀，又有幸認識了一位新朋友冗尤，名叫并行歸并排序。接下來胀溺，咱們就一一認識一下裂七，并且在最后來一次“算林大會”吧。
插入排序簡介
插入排序仓坞，算林稱最親民的排序算法背零，插入排序采用最簡單的插入方式對一個整數(shù)數(shù)組進行排序。它循環(huán)數(shù)組中從第二個開始的所有元素无埃，并且將每一個循環(huán)到的元素插入到相應(yīng)的位置徙瓶，從而實現(xiàn)排序的目的蝎困。
插入排序的代碼展示
使用Java代碼描述插入排序，可以用以下的代碼倍啥。
package algorithm;
/**
* @author zuoxiaolong
*
*/
public abstract class InsertSort {
public static void sort(int[] numbers){
for (int i = 1; i < numbers.length; i++) {
int currentNumber = numbers[i];
int j = i - 1;
while (j >= 0 && numbers[j] > currentNumber) {
numbers[j + 1] = numbers[j];
j--;
}
numbers[j + 1] = currentNumber;
}
}
}
這個算法從數(shù)組的第二個元素開始循環(huán)禾乘，將選中的元素與之前的元素一一比較，如果選中的元素小于之前的元素虽缕，則將之前的元素后移始藕，最后再將選中的元素放在合適的位置。在這個算法執(zhí)行的過程中氮趋，總是保持著索引i之前的數(shù)組是升序排列的伍派。
插入排序理解起來比較簡單，因此就不過多的解釋它的實現(xiàn)原理了剩胁，尚未理解的猿友可以自行研究诉植。
插入排序的性能分析
接下來，咱們來簡單分析一下插入排序的性能昵观。首先晾腔，插入排序當中有兩個循環(huán)，假設(shè)數(shù)組的大小為n啊犬，則第一個循環(huán)是n－1次灼擂，第二個while循環(huán)在最壞的情況下是1到n－1次。因此插入排序的時間復(fù)雜度大約為如下形式觉至。
1+2+3+4+...＋n－1 ＝ n（n－1）/ 2 ＝ O（n2）
時間復(fù)雜度為輸入規(guī)模的2次函數(shù)剔应，可見插入排序的時間復(fù)雜度是比較高的。這是原理上的簡單分析语御，最后在“算林大會”中峻贮，各位可以清楚的看到插入排序隨著輸入規(guī)模的增長，時間會指數(shù)倍的上升应闯。
歸并排序簡介
歸并排序纤控，算林屆的新秀，引領(lǐng)著分治法的潮流孽锥。歸并排序?qū)⑴判騿栴}拆分嚼黔，比如分成兩個較小的數(shù)組细层，然后對拆分后的數(shù)組分別進行排序惜辑，最后再將排序后的較小數(shù)組進行合并。
這種思想是一種算法設(shè)計的思想疫赎，很多問題都可以采用這種方式解決盛撑。映射到編程領(lǐng)域，其實就是遞歸的思想捧搞。因此在歸并排序的算法中抵卫，將會出現(xiàn)遞歸調(diào)用狮荔。
歸并排序的代碼展示
歸并排序主要由兩個方法組成，一個是用于合并兩個已經(jīng)排序的數(shù)組的方法介粘，一個則是遞歸方法殖氏，用于將問題無限拆分。接下來咱們一起看看歸并排序的Java代碼展示姻采，如下所示雅采。
package algorithm;
/**
* @author zuoxiaolong
*
*/
public abstract class MergeSort {
public static void sort(int[] numbers){
sort(numbers, 0, numbers.length);
}
public static void sort(int[] numbers,int pos,int end){
if ((end - pos) > 1) {
int offset = (end + pos) / 2;
sort(numbers, pos, offset);
sort(numbers, offset, end);
merge(numbers, pos, offset, end);
}
}
public static void merge(int[] numbers,int pos,int offset,int end){
int[] array1 = new int[offset - pos];
int[] array2 = new int[end - offset];
System.arraycopy(numbers, pos, array1, 0, array1.length);
System.arraycopy(numbers, offset, array2, 0, array2.length);
for (int i = pos,j=0,k=0; i < end ; i++) {
if (j == array1.length) {
System.arraycopy(array2, k, numbers, i, array2.length - k);
break;
}
if (k == array2.length) {
System.arraycopy(array1, j, numbers, i, array1.length - j);
break;
}
if (array1[j] <= array2[k]) {
numbers[i] = array1[j++];
} else {
numbers[i] = array2[k++];
}
}
}
}
可以看到，歸并排序?qū)⒁粋€長度為n的數(shù)組平均分為兩個n/2的數(shù)組分別進行處理慨亲，因此婚瓜，在sort方法中又調(diào)用了兩次sort方法自身。當數(shù)組大小為1時刑棵，則認為該數(shù)組為已經(jīng)為排好序的數(shù)組巴刻。因此在sort方法中，需要end與pos相差大于2時蛉签，才需要進一步拆分胡陪，這也是遞歸的終止條件。
此外碍舍，在代碼中督弓，使用了Java提供的arraycory函數(shù)進行數(shù)組復(fù)制，這種直接復(fù)制內(nèi)存區(qū)域的方式乒验，將會比循環(huán)賦值的方式速度更快愚隧。有些算法實現(xiàn)會給merge方法中的兩個臨時數(shù)組設(shè)置哨兵，目的是為了防止merge中for循環(huán)的前兩個if判斷锻全。為了方便理解狂塘，這里沒有設(shè)置哨兵，當某一個數(shù)組的元素消耗完時鳄厌，將直接使用arraycopy方法把另外一個數(shù)組copy到numbers當中荞胡。
歸并排序的性能分析
與插入排序一樣，咱們來簡單分析一下歸并排序的時間復(fù)雜度了嚎。咱們假設(shè)數(shù)組的大小為n泪漂，sort方法的時間復(fù)雜度為f（end－pos）。簡單的分析merge方法的復(fù)雜度歪泳，不難發(fā)現(xiàn)為（end－pos）＊2萝勤，這個結(jié)果的前提是咱們認為arraycopy方法的復(fù)雜度為length參數(shù)。
基于以上的假設(shè)呐伞，由于end－pos的初始值為n敌卓，因此歸并排序的復(fù)雜度大約為如下形式。
2＊f（n/2） ＋ 2＊n ＝ 2＊（2＊f（n/4）＋2＊（n/2）） ＋ 2＊n＝4＊f（n/4） ＋ 2＊n ＋ 2＊n ＝ n ＊f（1） ＋ 2＊n ＋...＋2＊n
其中f（1）的時間復(fù)雜度為常量伶氢，假設(shè)f（1）＝c趟径，而2＊n將有l(wèi)og2n個瘪吏。因此咱們得到歸并排序的最終時間復(fù)雜度為如下形式。
cn ＋ 2n＊log2n ＝ O（n＊log2n）
歸并排序的時間復(fù)雜度與插入排序相比蜗巧，已經(jīng)降低了很多掌眠，這一點在數(shù)組的輸入規(guī)模較大時將會非常明顯，因為log函數(shù)的增加速度將遠遠低于n的增加速度幕屹。
并行歸并排序簡介
并行歸并排序是在學(xué)習(xí)歸并排序時意淫出來的扇救，最近正在研究Java的并發(fā)編程，恰好歸并排序的子問題有一定的并行度與獨立性香嗓，因此版的并發(fā)歸并排序就這樣誕生了迅腔。事后，并行歸并排序這個家伙靠娱，發(fā)現(xiàn)早已眾所周知沧烈，不過在不知道的情況下自己能夠想到是不是也應(yīng)該竊喜一下呢。
并行歸并排序與普通的歸并排序沒有多大區(qū)別像云，只是利用現(xiàn)在計算機多核的優(yōu)勢锌雀，在有可能的情況下，讓兩個或多個子問題的處理一起進行迅诬。這樣一來腋逆，在效率上，并行歸并排序?qū)葰w并排序更勝一籌侈贷。
并行歸并排序的代碼展示
并行歸并排序主要對sort方法進行了修改惩歉，基礎(chǔ)的merge方法與普通的歸并排序是一樣的。因此在進行并行歸并排序時俏蛮，引用了歸并排序的一些方法撑蚌，具體的代碼如下所示。
package algorithm;
import java.util.concurrent.CountDownLatch;
/**
* @author zuoxiaolong
*
*/
public abstract class MergeParallelSort {
private static final int maxAsynDepth = (int)(Math.log(Runtime.getRuntime().availableProcessors())/Math.log(2));
public static void sort(int[] numbers) {
sort(numbers, maxAsynDepth);
}
public static void sort(int[] numbers,Integer asynDepth) {
sortParallel(numbers, 0, numbers.length, asynDepth > maxAsynDepth ? maxAsynDepth : asynDepth, 1);
}
public static void sortParallel(final int[] numbers,final int pos,final int end,final int asynDepth,final int depth){
if ((end - pos) > 1) {
final CountDownLatch mergeSignal = new CountDownLatch(2);
final int offset = (end + pos) / 2;
Thread thread1 = new SortThread(depth, asynDepth, numbers, mergeSignal, pos, offset);
Thread thread2 = new SortThread(depth, asynDepth, numbers, mergeSignal, offset, end);
thread1.start();
thread2.start();
try {
mergeSignal.await();
} catch (InterruptedException e) {}
MergeSort.merge(numbers, pos, offset, end);
}
}
static class SortThread extends Thread {
private int depth;
private int asynDepth;
private int[] numbers;
private CountDownLatch mergeSignal;
private int pos;
private int end;
/**
* @param depth
* @param asynDepth
* @param numbers
* @param mergeSignal
* @param pos
* @param end
*/
public SortThread(int depth, int asynDepth, int[] numbers, CountDownLatch mergeSignal, int pos, int end) {
super();
this.depth = depth;
this.asynDepth = asynDepth;
this.numbers = numbers;
this.mergeSignal = mergeSignal;
this.pos = pos;
this.end = end;
}
@Override
public void run() {
if (depth < asynDepth) {
sortParallel(numbers,pos,end,asynDepth,(depth + 1));
} else {
MergeSort.sort(numbers, pos, end);
}
mergeSignal.countDown();
}
}
}
在這段代碼中搏屑，有幾點是比較特殊的争涌，簡單的說明一下。
1辣恋，分解后的問題采用了并行的方式處理亮垫，并且咱們設(shè)定了一個參數(shù)asynDepth去控制并行的深度，通常情況下伟骨，深度為(log2CPU核數(shù))即可饮潦。
2，當子問題不進行并行處理時底靠，并行歸并排序調(diào)用了普通歸并排序的方法害晦，比如MergeSort.sort和MergeSort.merge特铝。
3暑中，因為合并操作依賴于兩個子問題的完成壹瘟，因此咱們設(shè)定了一個合并信號（mergeSignal），當信號發(fā)出時鳄逾，才進行合并操作稻轨。
并行歸并排序在原理上與普通的歸并排序是一樣的，只是對于子問題的處理采用了一定程度上的并行雕凹，因此如果猿友們理解歸并排序殴俱，那么并行歸并排序并不難理解。
并行歸并排序的性能分析
并行歸并排序只是將普通歸并排序中一些可并行的操作進行了并行處理枚抵，因此在總體的時間復(fù)雜度上并沒有質(zhì)的變化线欲，都是O（n＊log2n）。
由于并行歸并排序?qū)⒛承┡判虿僮鞑⑿胁僮髌。虼嗽谛阅苌弦欢ㄊ强煊谄胀w并排序算法的李丰。不過這也不是一定的，當數(shù)組規(guī)模太小時逼泣，并行帶來的性能提高可能會小于線程創(chuàng)建和銷毀的開銷趴泌，此時并行歸并排序的性能可能會低于普通歸并排序。
算林大會
接下來拉庶，就是一周一度的算林大會了嗜憔，本次算林大會主要由以上三種算法參加，勝者將會成為本周度最受歡迎算法氏仗。接下來是算林大會的代碼吉捶，請各位猿友過目。
package algorithm;
import java.io.File;
import java.lang.reflect.Method;
import java.util.Random;
/**
* @author zuoxiaolong
*
*/
public class SortTests {
public static void main(String[] args) {
testAllSortIsCorrect();
testComputeTime("MergeParallelSort", 40000, 5);
testComputeTime("MergeSort", 40000, 5);
testComputeTime("InsertSort", 400, 5);
}
public static void testAllSortIsCorrect() {
File classpath = new File(SortTests.class.getResource("").getFile());
File[] classesFiles = classpath.listFiles();
for (int i = 0; i < classesFiles.length; i++) {
if (classesFiles[i].getName().endsWith("Sort.class")) {
System.out.println("---測試" + classesFiles[i].getName() + "是否有效---");
testSortIsCorrect(classesFiles[i].getName().split("\\.")[0]);
}
}
}
public static void testSortIsCorrect(String className){
for (int i = 1; i < 50; i++) {
int[] numbers = getRandomIntegerArray(1000 * i);
invoke(numbers, className);
for (int j = 1; j < numbers.length; j++) {
if (numbers[j] < numbers[j-1]) {
throw new RuntimeException(className + " sort is error because " + numbers[j] + "<" + numbers[j-1]);
}
}
}
System.out.println("---" + className + "經(jīng)測試有效---");
}
public static void testComputeTime(String className,int initNumber,int times,Object... arguments) {
long[] timeArray = new long[times];
for (int i = initNumber,j = 0; j < times; i = i * 10,j++) {
timeArray[j] = computeTime(i, className, arguments);
}
System.out.print(className + "時間增加比例：");
for (int i = 1; i < timeArray.length ; i++) {
System.out.print((float)timeArray[i]/timeArray[i - 1]);
if (i < timeArray.length - 1) {
System.out.print(",");
}
}
System.out.println();
}
public static long computeTime(int length,String className,Object... arguments){
int[] numbers = getRandomIntegerArray(length);
long start = System.currentTimeMillis();
System.out.print("開始計算長度為"+numbers.length+"方法為"+className+"參數(shù)為[");
for (int i = 0; i < arguments.length; i++) {
System.out.print(arguments[i]);
if (i < arguments.length - 1) {
System.out.print(",");
}
}
System.out.print("]皆尔，時間為");
invoke(numbers, className, arguments);
long time = System.currentTimeMillis()-start;
System.out.println(time + "ms");
return time;
}
public static int[] getRandomIntegerArray(int length){
int[] numbers = new int[length];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = new Random().nextInt(length);
}
return numbers;
}
public static void invoke(int[] numbers,String className,Object... arguments){
try {
Class clazz = Class.forName("algorithm." + className);
Class[] parameterTypes = new Class[arguments.length + 1];
parameterTypes[0] = int[].class;
for (int i = 0; i < arguments.length; i++) {
parameterTypes[i + 1] = arguments[i].getClass();
}
Method method = clazz.getDeclaredMethod("sort", parameterTypes);
Object[] parameters = new Object[parameterTypes.length];
parameters[0] = numbers;
for (int i = 0; i < arguments.length; i++) {
parameters[i + 1] = arguments[i];
}
method.invoke(null, parameters);
} catch (Exception e) {
throw new RuntimeException(e);
}
}
}
以上代碼testAllSortIsCorrect方法首先驗證了三種算法的正確性帚稠，也就是說經(jīng)過sort方法后，數(shù)組是否已經(jīng)升序排列床佳。需要一提的是滋早，由于插入排序的性能太低，因此插入排序測試的最大規(guī)模為400萬砌们，而歸并排序測試的最大規(guī)模為4億杆麸。
接下來，大家就一起看看運行結(jié)果吧浪感。以下是在LZ的mac pro上的運行結(jié)果昔头，硬件配置為16G內(nèi)存，4核i7影兽。這種配置下揭斧，異步深度（asynDepth）默認為log24=2。
---測試InsertSort.class是否有效---
---InsertSort經(jīng)測試有效---
---測試MergeParallelSort.class是否有效---
---MergeParallelSort經(jīng)測試有效---
---測試MergeSort.class是否有效---
---MergeSort經(jīng)測試有效---
開始計算長度為40000方法為MergeParallelSort參數(shù)為[]，時間為6ms
開始計算長度為400000方法為MergeParallelSort參數(shù)為[]讹开，時間為44ms
開始計算長度為4000000方法為MergeParallelSort參數(shù)為[]盅视，時間為390ms
開始計算長度為40000000方法為MergeParallelSort參數(shù)為[]，時間為3872ms
開始計算長度為400000000方法為MergeParallelSort參數(shù)為[]旦万，時間為47168ms
MergeParallelSort時間增加比例：7.3333335,8.863636,9.9282055,12.181818
開始計算長度為40000方法為MergeSort參數(shù)為[]闹击，時間為7ms
開始計算長度為400000方法為MergeSort參數(shù)為[]，時間為81ms
開始計算長度為4000000方法為MergeSort參數(shù)為[]成艘，時間為839ms
開始計算長度為40000000方法為MergeSort參數(shù)為[]赏半，時間為9517ms
開始計算長度為400000000方法為MergeSort參數(shù)為[]，時間為104760ms
MergeSort時間增加比例：11.571428,10.358025,11.343266,11.00767
開始計算長度為400方法為InsertSort參數(shù)為[]淆两，時間為0ms
開始計算長度為4000方法為InsertSort參數(shù)為[]断箫，時間為3ms
開始計算長度為40000方法為InsertSort參數(shù)為[]，時間為245ms
開始計算長度為400000方法為InsertSort參數(shù)為[]秋冰，時間為23509ms
開始計算長度為4000000方法為InsertSort參數(shù)為[]瑰枫，時間為3309180ms
InsertSort時間增加比例：Infinity,81.666664,95.9551,140.76227
首先可以看到，三種算法都是運行正確的丹莲。接下來光坝，咱們可以對比一下三種算法的性能。
根據(jù)輸出結(jié)果甥材，規(guī)模為400萬時的區(qū)別是最明顯與直觀的盯另。并行歸并排序僅需要390ms就完成了400萬規(guī)模的排序，而普通的歸并排序則需要839ms才可以洲赵，至于插入排序鸳惯，簡直是不可理喻，竟然需要300多萬ms叠萍，大約50分鐘芝发。
咱們再來看三者的時間增長趨勢。兩種歸并排序基本上與規(guī)模的增長趨勢相似苛谷，每當規(guī)模增加10倍時辅鲸，時間也基本上增加10倍，而插入排序則幾乎是以100倍的速度在增加腹殿，剛好是數(shù)組規(guī)模增長速度的平方独悴。其中的Infinity是因為當數(shù)組規(guī)模為400時，毫秒級別的計時為0ms锣尉，因此當除數(shù)為0時刻炒，結(jié)果就為Infinity。
當然了自沧，這一次結(jié)果具有一定的隨機性坟奥，猿友們可以在自己的電腦上多實驗幾次觀察一下，不過插入排序的時間實在讓人等的蛋疼。
強烈推薦《數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)典問題解析》（PDF文檔）
由于細節(jié)內(nèi)容實在太多啦爱谁，所以只把部分知識點截圖出來粗略的介紹晒喷，每個小節(jié)點里面都有更細化的內(nèi)容！
整理了一份Java數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)典問題解析核心知識點管行。覆蓋遞歸和回溯厨埋、鏈表邪媳、棧捐顷、隊列、樹雨效、優(yōu)先隊列和堆迅涮、隊列、優(yōu)先隊列和堆徽龟、并查集ADT叮姑、排序、選擇算法(中位數(shù))据悔、散列传透、算法設(shè)計技術(shù)、分治算法极颓、動態(tài)規(guī)劃算法朱盐、雜談等大量知識點。
如果需要獲取到這個【核心知識點整理】https://shimo.im/docs/k6xtWVdqw3tyh36p/?《Java學(xué)習(xí)菠隆、面試兵琳；文檔、視頻資源免費獲取》點擊即可獲取
