注：
lgN在這里為1og2N簡寫
為了方便描述,本文默認用int類型比較纸肉，從小到大排序
本文排序算法以java語言實現(xiàn)
本文的排序都是比較排序
比較次數(shù)和賦值和交換次數(shù)有的排序不好分析端逼，可能不準確
一.插入排序
對于未排序數(shù)據(jù)颜矿，在已排序序列中從后向前掃描洗贰，找到相應位置并插入
從第一個元素開始找岖，該元素認為已經(jīng)被排序；
取出下一個元素敛滋，在已排序的元素序列中從后向前掃描许布；
如果已排序元素大于新元素，新元素繼續(xù)比較前一個元素绎晃，直到找到已排序的元素小于或者等于新元素的位置蜜唾；
將新元素插入到該位置后帖旨；
重復步驟2~4。
java實現(xiàn)
插入排序為兩層循環(huán)嵌套灵妨，時間復雜度O(N2),插入排序的while循環(huán)是先比較解阅，移動待插入的位置，循環(huán)結束才真正交換數(shù)據(jù)位置泌霍。這里需要注意货抄，常用的for循環(huán)嵌套進行插入排序會每次比較都和前面元素交換直到插入到待插入位置，上面的內(nèi)循環(huán)用while尋找待插入位置朱转，把其他元素后移的算法更合理蟹地，每次插入只一次進行一次交換。
因插入排序每次只比較相鄰一位數(shù)據(jù)藤为，對于逆序較多的數(shù)組效率低怪与，衍生算法希爾排序，會大幅加快逆序交換缅疟，后面詳細介紹分别。
二.選擇排序
在未排序序列中找到最小元素，放到排序序列的起始位置存淫，然后耘斩，再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到已排序序列的末尾桅咆，循環(huán)直到所有元素均排序完畢括授。
初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空岩饼；
第i趟排序(i=1,2,3…n-1)開始時荚虚，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R[i..n]。該趟排序從當前無序區(qū)中選出最小的記錄 R[k]籍茧，將它與無序區(qū)的第1個記錄R[i]交換版述，使R[1..i]和R[i+1..n]分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)；
循環(huán)n-1次硕糊，排序完成院水。
java實現(xiàn)
選擇排序為兩層for循環(huán)嵌套，內(nèi)層循環(huán)始終去找最小值简十，放到最前面檬某。交換次數(shù)比冒泡排序少很多，所以實際執(zhí)行效率比冒泡排序快螟蝙。
衍生算法恢恼，雙向選擇排序（每次循環(huán)，同時選出最大值放在末尾胰默，最小值放在前方）场斑，可以提高選擇效率漓踢。
三.冒泡排序
重復地走訪過要排序的數(shù)列，一次比較兩個元素漏隐，如果它們的順序錯誤就把它們交換過來喧半。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換
初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空青责；
第i趟排序(i=0,1,2…n-1)開始時挺据，當前無序區(qū)和有序區(qū)分別為R[0..n-i]和R[n-i+1..n]。對每一對相鄰元素進行比較脖隶，從開始第一對到結尾的最后一對扁耐，如果第一個比第二個大，就交換它們兩個产阱，這樣在最后的元素應該會是最大的數(shù)婉称，使R[1..n-i-1]和R[n-i..n]分別變?yōu)橛涗泜€數(shù)減少1個的新無序區(qū)和記錄個數(shù)增加1個的新有序區(qū)；
循環(huán)n-1次构蹬，直到排序完成王暗。
java實現(xiàn)
冒泡排序在代碼實現(xiàn)上是最簡單的，不需要什么思考怎燥，兩層for循環(huán)嵌套瘫筐，比大小交換。因為冒泡通常的例子都是讓大的往后移铐姚，對于剛接觸排序的人來說看來上面可能認為冒泡排序與選擇排序是反向操作，其實冒泡排序也可以把小數(shù)向前移肛捍，這樣能明顯的看出冒泡排序和選擇的排序的不同隐绵，針對無序區(qū)的元素，冒泡排序總是不斷地交換拙毫，而選擇排序是先找出最小的元素再做一次交換依许。
衍生算法，雞尾酒排序缀蹄，該排序從左往右找出最大值后峭跳，再從右往左，找出最小值缺前，類似雞尾酒攪拌左右循環(huán),在某些情況下蛀醉，優(yōu)于冒泡排序。
四.希爾排序
插入排序的改進版衅码，優(yōu)先比較距離遠的元素拯刁，減少交換次數(shù)
選擇一個增量序列t1，t2逝段，…垛玻，tk割捅，其中ti>tj，tk=1帚桩；
按增量序列個數(shù)k亿驾，對序列進行k 趟排序；
每趟排序账嚎，根據(jù)對應的增量ti颊乘，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序醉锄。僅增量因子為1 時乏悄，整個序列作為一個表來處理，表長度即為整個序列的長度恳不。
java實現(xiàn)
上面是常用的寫法檩小，每次比較，如果前面的更大都會交換烟勋，可以優(yōu)化一下,直接把上面插入算法嵌入內(nèi)循環(huán)规求，比較的間隔由1改為h,比較的時候只移動插入位置，比較完只需交換一次
java實現(xiàn)
希爾排序的時間復雜度與增量序列的選取有關卵惦，例如希爾增量時間復雜度為O(N2)阻肿，而Hibbard增量的希爾排序的時間復雜度為O(N1.5)，希爾排序時間復雜度的下界是Nlg2N沮尿。希爾排序沒有快速排序算法快 O(N(lgN))丛塌，因此中等大小規(guī)模表現(xiàn)良好，對規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇畜疾。但是比O(N2)復雜度的算法快得多赴邻。并且希爾排序非常容易實現(xiàn)，算法代碼短而簡單啡捶。此外姥敛，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時快速排序在最壞的情況下執(zhí)行的效率會非常差瞎暑。
五.堆排序
堆就是完全二叉樹彤敛，分為最大堆和最小堆，最大堆要求節(jié)點的元素都要不小于其孩子（最小堆要求節(jié)點元素都不大于其孩子）了赌，對左右孩子的大小關系不做要求墨榄，所以處于最大堆的根節(jié)點的元素一定是這個堆中的最大值。堆排序算法就是抓住了堆的這一特點揍拆，每次都取堆頂?shù)脑厍牛瑢⑵浞旁谛蛄凶詈竺妫缓髮⑹Ｓ嗟脑刂匦抡{(diào)整為最大堆，依此類推播揪，最終得到排序的序列贮喧。
將初始待排序關鍵字序列(R1,R2….Rn)構造成最大堆，此堆為初始的無序區(qū)猪狈；
將堆頂元素R[1]與最后一個元素R[n]交換箱沦，此時得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；
由于交換后新的堆頂R[1]可能違反堆的性質雇庙，因此需要對當前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆谓形，然后再次將R[1]與無序區(qū)最后一個元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)疆前。不斷重復此過程直到有序區(qū)的元素個數(shù)為n-1寒跳，則整個排序過程完成。
java實現(xiàn)
因為堆的父節(jié)點k的子節(jié)點為2k和2k+1竹椒，下標為0會導致父節(jié)點和左子節(jié)點都是0童太，所以上述排序的數(shù)組從下標從1開始比較方便。堆排序只需要NlgN的時間胸完，而且算法穩(wěn)定书释，只需要少量輔助空間，是最優(yōu)的利用時間和空間的方法赊窥，但因為它的緩存命中率低爆惧，應用很少用它，多用于嵌入式锨能。
六.歸并排序
遞歸的把已有序列均分為兩個子序列扯再，使子序列有序，合并子序列
把長度為n的輸入序列分成兩個長度為n/2的子序列腹侣；
對這兩個子序列分別采用歸并排序叔收；
將兩個排序好的子序列合并成一個最終的排序序列。
java實現(xiàn)
歸并排序是分治法的典型應用傲隶，高效穩(wěn)定，但是歸并排序需要一個數(shù)組長度的輔助空間窃页，在空間成本高的時候不適合使用跺株。
七.快速排序
通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小脖卖，則可分別對這兩部分記錄繼續(xù)進行排序乒省，以達到整個序列有序。
從數(shù)列中挑出一個元素畦木，稱為 “基準”（pivot）袖扛；
重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）蛆封。在這個分區(qū)退出之后唇礁，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作惨篱；
遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序盏筐。
java實現(xiàn)
快速排序是通常情況下的最優(yōu)選擇，高效只需要lgN級別的輔助空間砸讳，但是快速排序不穩(wěn)定琢融，受切分點的影響很大
七種排序總結
上面詳細介紹了七種排序的實現(xiàn)細節(jié)和特點，下面的表格總結了七種排序的各種特征簿寂。
其中插入排序漾抬，選擇排序，冒泡排序都是簡單排序常遂，時間復雜度是O(N2),其中插入排序和冒泡排序適合原始序列有序的數(shù)組纳令，選擇排序的交換和賦值次數(shù)會比較少，可以根據(jù)不同環(huán)境和數(shù)據(jù)的實際情況和長度選擇具體的排序烈钞。整體插入排序優(yōu)于選擇排序優(yōu)于冒泡排序泊碑。希爾排序是插入排序的優(yōu)化，突破了前三個排序O(N2)的時間復雜度毯欣，但是本質還是插入排序馒过，突破比較相鄰元素的慣性思維，直接比較一定間隔的元素酗钞，大幅度減少了逆序調(diào)整的比較次數(shù)和交換次數(shù)腹忽，從而達到比較理想的算法復雜度，適合對中等規(guī)模數(shù)組進行排序砚作。堆排序是利用了最大堆的特點窘奏，始終把堆頂元素（最大元素）和最后一個元素替換，再重新構造最大堆葫录，重復執(zhí)行達到排序的效果着裹。堆結構的特性讓算法的復雜度降低到NlgN級別，但是有不方便索引元素的確定米同，緩存命中率較低骇扇。而歸并排序則是充分運用了分治原理，把大問題不斷的拆分成小問題面粮，進行排序少孝，再合并小數(shù)組達到整體排序的目標，歸并排序即高效又可靠熬苍，唯一的缺點是需要數(shù)組長度的輔助空間稍走，在空間成本低的時候適合使用。快速排序則解決了歸并排序占用空間的問題婿脸，在數(shù)組內(nèi)部用很小的輔助棧粱胜，即可完成對元素的分離，再去解決分離后的更小的數(shù)組盖淡，正常情況下?lián)碛泻蜌w并相同級別的時間復雜度年柠，但是得注意選取好切分元素。 實際上一個復雜的序列可能用不止一種排序褪迟，例如分治和快速排序在分割到很小的序列時再進行分割反而效率不如插入排序等簡單排序冗恨，可以設置一定的閾值，先用分治或者快速排序的方式分割數(shù)組味赃，再轉換成插入等簡單排序完成最終的排序掀抹。
希望本文能加深大家對排序的理解。我的微信公眾號：程序之路心俗，會持續(xù)發(fā)布技術成長文章架忌，歡迎長按或者掃描二維碼關注
