一.排序
1.什么是穩(wěn)定性
2.分類
二.插入排序
1.直接插入排序
原理：當(dāng)插入第i個(gè)數(shù)時(shí)，前面i-1個(gè)數(shù)據(jù)已經(jīng)排好序了。只要用第i個(gè)數(shù)據(jù)和第i-1，i-2，i-3個(gè)數(shù)據(jù)依次進(jìn)行比較，找到合適的位置插入，后面的數(shù)據(jù)一次后移即可
例如1，3，2，24，35，11 從大到小排，從第二個(gè)數(shù)開始定義一個(gè)臨時(shí)變量tmp存放要排的數(shù)據(jù)3，此時(shí)1下標(biāo)就是空的，定義一個(gè)i表示要進(jìn)行比較的數(shù)的下標(biāo)，此時(shí)i=0，3和1比，3大，所以把1放到1下標(biāo)，i向前走發(fā)現(xiàn)i<0了，所以i就不向前走了，把tmp的值就放到i下標(biāo)；假設(shè)11以前都排好了，即35，24，3，2，1，11，現(xiàn)在排11，tmp=11，初始i=4，tmp與4下標(biāo)的數(shù)比較，11比1大，所以1放到5下標(biāo)，i再向前走，11比2大，所以2放到4下標(biāo)（即i-1下標(biāo)），i再向前走，11比3大，所以3放到3下標(biāo)（即i-1下標(biāo)），i再向前走，24比11小，所以把11也就是tmp的值放到2下標(biāo)（即i-1下標(biāo)）。
代碼如下
總結(jié)
1.時(shí)間復(fù)雜度：O(N^2);因?yàn)楸容^次數(shù)是依次遞增，即1+2+3+4+……+(n-1).
2.空間復(fù)雜度：O(1);因?yàn)樵摯a使用的變量是常數(shù)個(gè)。
3.穩(wěn)定性：穩(wěn)定的
4.元素集合越接近有序，需要比較的次數(shù)就越少，時(shí)間效率就越高。比如從小到大排序1，2，3，4，5，已經(jīng)有序了，只需遍歷到每個(gè)元素即可，不需要回退，此時(shí)時(shí)間復(fù)雜度為O(N)。
5.適用于待排序序列已經(jīng)基本接近有序
2.希爾排序（直接插入排序的優(yōu)化）
希爾排序法又稱為縮小增量排序法，把一組數(shù)分為若干組，每組進(jìn)行直接插入排序
例如下圖：
總結(jié)
1.時(shí)間復(fù)雜度：尚未有明確的規(guī)定，可以是n^1.3~n^1.6，也可以是n^1.25~1.6*n^1.25。
2.空間復(fù)雜度：O(1)。因?yàn)橐恢笔窃谠瓟?shù)組上進(jìn)行操作，沒(méi)有額外開辟空間
3.穩(wěn)定性：不穩(wěn)定，原因是存在不相鄰記錄的交換。比如1，5，3，3，4，6，分成倆組進(jìn)行從小到大排序，第一組是1，3，4，不用交換，第二組是5，3，6，需要交換變成3，5，6，這就導(dǎo)致第二個(gè)3跑到了第一個(gè)3的前面
三.選擇排序
1.直接選擇排序
定義一個(gè)i，從0下標(biāo)開始遍歷數(shù)組；再定義一個(gè)minindex，初始值為i，從i+1下標(biāo)開始到n-1，每次將該下標(biāo)的值與minindex下標(biāo)的值進(jìn)行比較，如果小于minindex下標(biāo)的值，就將minindex更新為當(dāng)前下標(biāo)，最后將minindex與i下標(biāo)的值進(jìn)行交換，i++，到最后，該數(shù)組就是從小到大排序。代碼如下：
總結(jié)
1.時(shí)間復(fù)雜度：O(N^2)
2.空間復(fù)雜度：O(1)
3.穩(wěn)定性：不穩(wěn)定，比如5，8，5，1，7要從小到大排序，我們知道，第一趟結(jié)束，5會(huì)和1進(jìn)行交換，這是第一個(gè)5就到了第二個(gè)5之后，所以不穩(wěn)定。
4.缺點(diǎn)：對(duì)于已經(jīng)有序的數(shù)組，它還是會(huì)無(wú)腦的遍歷從i到n-1的每一個(gè)數(shù)據(jù)，導(dǎo)致無(wú)論是最好情況下還是最壞情況下，都是O(N^2)。
2.雙向選擇排序
定義maxindex和minindex，定義left=0，right=arr.length-1，初始maxindex和minindex都等于left，然后遍歷left到right下標(biāo)的值，更新maxindex和minindex，最后將left下標(biāo)與minindex下標(biāo)的值進(jìn)行交換，將right下標(biāo)與maxindex下標(biāo)的值進(jìn)行交換，然后left++，right--。
代碼如下：
但注意，這段代碼有問(wèn)題，如果maxindex就是left，那么mindex與left交換之后，maxindex指向的就是最小值了，直接讓maxindex與right交換就會(huì)出問(wèn)題，所以進(jìn)行如下改進(jìn)：
總結(jié)
1.時(shí)間復(fù)雜度：O(N^2)
2.空間復(fù)雜度：O(1)
3.穩(wěn)定性：不穩(wěn)定
3.堆排序
排升序建立大堆，排降序建立小堆。以升序?yàn)槔憾x一個(gè)end，初始指向arr.length-1，將大根堆的0下標(biāo)元素與end指向的元素交換，此時(shí)end下標(biāo)的元素就是有序的，再將0下標(biāo)元素進(jìn)行向下調(diào)整（范圍是0~end）；然后end--，再與0下標(biāo)的值進(jìn)行交換，再向下調(diào)整……
代碼如下：
總結(jié)
1.時(shí)間復(fù)雜度：O(N*log2N)。因?yàn)橄蛳陆ǘ训臅r(shí)間復(fù)雜度為O(N),而從0到end進(jìn)行向下調(diào)整的全過(guò)程的時(shí)間復(fù)雜度為O(N*log2N)，所以O(shè)(N)可以忽略不記，只記O(N*log2N)
2.空間復(fù)雜度：O(1)。
3.穩(wěn)定性：不穩(wěn)定。
四.交換排序
1.冒泡排序
代碼如下：
優(yōu)化：
總結(jié)
1.時(shí)間復(fù)雜度：O(N^2)。
2.空間復(fù)雜度：O(1)。
3.穩(wěn)定性：穩(wěn)定。
2.快速排序
(1).Hoare版
以0下標(biāo)的數(shù)為基準(zhǔn)值，初始化left=1，right=arr.length-1，right先向左移動(dòng)，找到比0下標(biāo)小的數(shù)就停止，然后left向右移動(dòng)，找到比0下標(biāo)的值大的數(shù)就停止，之后left和right下標(biāo)的值進(jìn)行交換，然后再讓right移動(dòng)，left移動(dòng)，重復(fù)上述過(guò)程，直到left和right相遇時(shí)，設(shè)相遇時(shí)的下標(biāo)為flag，就將0下標(biāo)的值與flag下標(biāo)的值進(jìn)行交換；然后進(jìn)行遞歸，就是讓flag的左邊和右邊都進(jìn)行Hoare版的快速排序。代碼如下：
注意：必須先讓right找小的，因?yàn)樽罱K是left與right相遇的地方即flag和0下標(biāo)交換，此時(shí)原來(lái)0下標(biāo)的值就在原來(lái)flag下標(biāo)的值的右邊，如果先讓left找大數(shù)，就可能會(huì)導(dǎo)致把比基準(zhǔn)值大的數(shù)放到了基準(zhǔn)值的左邊，而先讓right找就沒(méi)問(wèn)題
(2).挖坑法
先將第一個(gè)數(shù)據(jù)存放在臨時(shí)變量key中，形成一個(gè)坑位，然后right向左走，找到比key小的數(shù)，拿起來(lái)放到0下標(biāo)處，此時(shí)的坑位轉(zhuǎn)移到了right下標(biāo)，然后讓left向右走，找到比key大的數(shù)，將它拿起來(lái)放到right下標(biāo)，此時(shí)坑位轉(zhuǎn)移到了left處，依此類推，直到left與right相遇后將key的值放到相遇處，并以相遇處為分割線進(jìn)行左右遞歸，代碼如下：
注意，必須是arr[right]>=key,等號(hào)不可以忽略，否則就會(huì)死循環(huán)。比如6，1，3，4，7，6，left=0，right=5，6大于6嗎？不大于，所以第一個(gè)while進(jìn)不去，所以將right的值給到left下標(biāo)，即6和6進(jìn)行交換，然后進(jìn)行第二個(gè)while的判斷，又進(jìn)不去，所以又交換……一直這樣死循環(huán)。
(3).前后指針?lè)?/h4>
定義key指向0下標(biāo)，初始化prev指向0，初始化cur指向0，cur往后走找到一共比key指向的數(shù)據(jù)小的值時(shí)停止，然后prev先++，如果prev和cur指向的不是同一個(gè)數(shù)，就讓prev指向的數(shù)與cur指向的數(shù)交換，然后cur再去找下一個(gè)比key小的數(shù)，直到cur走到頭后，讓key下標(biāo)的值與prev下標(biāo)的值進(jìn)行交換，返回prev，再以prev為基準(zhǔn)，左右向這樣去遞歸。代碼如下：
總結(jié)
1.時(shí)間復(fù)雜度：O(N*log2N)。這可以說(shuō)是最好情況下是O(N*log2N)，即每一次找到的flag都是在這組數(shù)據(jù)的中央，第一層是一整組，共n個(gè)數(shù)據(jù)，都要遍歷到；第二層是從中央的flag分開成倆組，每組n/2個(gè)數(shù)據(jù)，都要遍歷到……一共有l(wèi)og2n層，每層都是遍歷到n個(gè)數(shù)據(jù)，所以是O(N*log2N)
而最壞情況下是O(N^2)，即每次找到的flag都是第一個(gè)數(shù)據(jù)，導(dǎo)致沒(méi)有左邊，只有右邊，所以這種情況下是：第一層遍歷n個(gè)數(shù)據(jù)進(jìn)行比較，第二層是n-1個(gè)數(shù)據(jù)，第三層是n-2個(gè)數(shù)據(jù)……一共是n層。
2.空間復(fù)雜度：O(log2N)。這主要與函數(shù)的遞歸調(diào)用有關(guān)。實(shí)際上，O(log2N)是最好情況下，也就是每次找到的基準(zhǔn)值的下標(biāo)都是中間值，所以先對(duì)基準(zhǔn)值的左邊進(jìn)行遞推，一共log2n層，所以在棧上開辟了log2n個(gè)空間，然后回退，直到把左邊遞歸完，再此同時(shí)把這log2n個(gè)空間回收，然后對(duì)右邊進(jìn)行遞歸，又是開辟log2n個(gè)空間……總的來(lái)說(shuō)就是O(log2N)
最壞情況下就是基準(zhǔn)值一直是第一個(gè)，導(dǎo)致一共要開辟n個(gè)空間，所以是O(N)。
3.穩(wěn)定性：不穩(wěn)定，比如6，7，3，4，5，10，3，第一次就是7和最后一個(gè)3進(jìn)行交換，導(dǎo)致倆個(gè)3的位置發(fā)生了改變
4.缺點(diǎn)：當(dāng)數(shù)組數(shù)據(jù)過(guò)多，遞歸次數(shù)過(guò)大時(shí)，可能會(huì)造成棧溢出
3.快速排序的優(yōu)化
出發(fā)點(diǎn)：減少遞歸的次數(shù)，也就是盡量讓數(shù)組變成一棵完全二叉樹，讓基準(zhǔn)值盡量為中間值
(1).三數(shù)取中法選基準(zhǔn)
定義left，right，再定義mid=(left+right)/2，選取三個(gè)下標(biāo)對(duì)應(yīng)的數(shù)中的中位數(shù)，將其與left下標(biāo)的數(shù)進(jìn)行交換，然后再用上面的三個(gè)方法返回flag下標(biāo)，再去遞歸，這樣可以減少基準(zhǔn)值總是在頭或尾的情況。代碼如下：
(2).遞歸到小的子區(qū)間時(shí)，可以用直接插入排序
就是說(shuō)，越往下遞歸，數(shù)據(jù)越有序，選擇直接插入排序的時(shí)間效率就會(huì)越高，所以可以在三數(shù)取中法的基礎(chǔ)上再如下優(yōu)化：
(3).非遞歸的快速排序
用到了棧。首先定義start和end，先找到基準(zhǔn)值的下標(biāo)，然后將基準(zhǔn)值左半部分的開頭和結(jié)尾的下標(biāo)存到棧中，再將基準(zhǔn)值右半部分的開頭和結(jié)尾的下標(biāo)存到棧中，注意，如果基準(zhǔn)值左側(cè)不夠倆個(gè)元素，就不能將左側(cè)的開頭和結(jié)尾的下標(biāo)存到棧中，右邊也同理（如果flag-1>start,就說(shuō)明左邊夠倆個(gè)元素，如果flag+1小于end，就說(shuō)明右邊夠倆個(gè)元素）。然后彈出一個(gè)數(shù)給到end，再?gòu)棾鲆还矓?shù)給到start，再去找基準(zhǔn)值，以此進(jìn)行循環(huán)，而不是遞歸，直到棧為空。
五.歸并排序
1.遞歸實(shí)現(xiàn)歸并排序
對(duì)于一個(gè)數(shù)組1，6，5，2，3，7，4，9，先將它分裂，分成左右倆半，再將左邊分成左右倆半，再將右邊分成左右倆半，直到每組只有一個(gè)數(shù)據(jù)，然后讓每組先在內(nèi)部進(jìn)行排序，然后左右倆組再進(jìn)行排序(此時(shí)就是倆個(gè)有序數(shù)組的排序，叫做二路歸并)。
代碼如下：
起初start=0，end=arr.length-1，然后進(jìn)行分裂，最后回歸后進(jìn)行二路歸并。二路歸并代碼如下：
對(duì)于已經(jīng)有序的倆個(gè)數(shù)組，比如：1，4，6，7和2，3，5，9，定義s1,e1,s2,e2，比較s1,s2對(duì)應(yīng)的數(shù)，如果s1小，就將s1對(duì)應(yīng)的數(shù)拷貝到tmp數(shù)組，然后s1++，反之s2++。直到s1>e1或s2>e2時(shí)結(jié)束，此時(shí)如果s1<=e1，說(shuō)明左面的數(shù)還沒(méi)有完全拷貝到tmp中，因?yàn)橐呀?jīng)有序，所以直接拷貝即可，反之操作s2
總結(jié)
1.時(shí)間復(fù)雜度：O(Nlog2N)。這個(gè)數(shù)組最終被拆成了一棵完全二叉樹，所以一共經(jīng)歷了log2N層，在回退進(jìn)行二路歸并時(shí)，每層都遍歷了n個(gè)元素，所以是O(log2N)。
2.空間復(fù)雜度：O(log2N)。一共log2N層，就是開辟了log2N個(gè)空間后才開始回收空間去遞歸另一邊。
3.穩(wěn)定性：穩(wěn)定
2.非遞歸實(shí)現(xiàn)歸并排序
先一個(gè)一個(gè)有序，然后倆個(gè)倆個(gè)有序，然后四個(gè)四個(gè)有序……
代碼如下：
比如數(shù)組1，4，2，3，6，5，3，2，首先每組一個(gè)數(shù)據(jù)，已經(jīng)有序，所以從每組兩個(gè)數(shù)據(jù)開始，14，23，65，32，left=i，right=i+gap-1，二路歸并后得到14，23，56，23，然后變成每組四個(gè)數(shù)，即1423，5623，進(jìn)行二路歸并排序(第一路是left到mid，第二路是mid+1到right)，得到1234，2356，最后gap=8,再排序。但這樣的代碼有錯(cuò)誤，對(duì)于數(shù)組長(zhǎng)度不是2^n的就不適用，比如1，4，2，6，5，3，共6個(gè)數(shù)，gap=2時(shí)變成14，26，35，然后當(dāng)gap=4時(shí)，i初始為0，i+=gap得到4，那么第二組的left=4,right=7超了，所以right變成5，同理mid也是5，排完變成1246，35，最后按理說(shuō)應(yīng)該再對(duì)整體排序，但gap=8超過(guò)數(shù)組長(zhǎng)度了，所以最后一組排序沒(méi)有正常進(jìn)行，所以這個(gè)代碼不適用
代碼修改：真正實(shí)現(xiàn)顯性的兩個(gè)有序數(shù)組的合并，即每次i+=gap*2，直接倆組倆組的操作
對(duì)于數(shù)組3，1，2，5，7，1，首先gap=1，分成每組一個(gè)，已經(jīng)有序，然后倆組倆組進(jìn)行二路歸并排序，首先是第1，2組，left=0，mid=0，right=1，……得到13，25，17，然后gap=2，即每組倆個(gè)數(shù)，兩組進(jìn)行歸并排序，前倆組得到1235，后面i=4時(shí)，left=4，mid=5，right=8，right超了，所以變成right=5，再去歸并排序，此時(shí)的倆個(gè)有序數(shù)組是17和空數(shù)組；最后gap=4，i=0時(shí)，left=0，mid=3，right=7超了，所以right=5，此時(shí)的倆個(gè)有序數(shù)組是1235和17，再去二路歸并排序。這樣就能全部排好序了文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-824674.html
我們不難發(fā)現(xiàn)，改進(jìn)后的代碼中l(wèi)eft和mid恰好是第一個(gè)有序數(shù)組的首尾，mid+1和right正好是第二個(gè)有序數(shù)組的首尾，而且第二個(gè)有序數(shù)組的長(zhǎng)度可以小于gap甚至為0。而之前的代碼可能排序不完善文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-824674.html
到了這里，關(guān)于Java基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)之排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
