七大排序的个人总结（一）
今天花了點(diǎn)時(shí)間把七個(gè)常見(jiàn)的內(nèi)部排序重新復(fù)習(xí)了一遍，總結(jié)一下，也算是驗(yàn)證一下自己有沒(méi)有真正理解。
?
冒泡排序（Bubble Sort）：
很多人聽(tīng)到排序第一個(gè)想到的應(yīng)該就是冒泡排序了。也確實(shí)，冒泡排序的想法非常的簡(jiǎn)單：大的東西沉底，汽泡上升。基于這種思想，我們可以獲得第一個(gè)版本的冒泡：
public static void sort1(int[] array) {for (int i = 0; i < array.length; i++) { // i為確定了幾個(gè)數(shù)for (int j = 1; j < array.length - i; j++) {if (array[j - 1] > array[j]) {// 進(jìn)行兩元素之間的位置交換int temp = array[j - 1];array[j - 1] = array[j];array[j] = temp;}}}}再想一想，其實(shí)有這樣一種情況：如果在某一個(gè)遍歷的過(guò)程中，沒(méi)有發(fā)生數(shù)據(jù)交換，那其實(shí)說(shuō)明了這個(gè)數(shù)組已經(jīng)是有序的了：所以我們可以作一點(diǎn)小小的優(yōu)化（雖然不經(jīng)常有用）：
// 升級(jí)版1// 基于一個(gè)事實(shí)，如果某一次遍歷沒(méi)有發(fā)生數(shù)據(jù)交換，那么排序已經(jīng)完成public static void sort2(int[] array) {boolean complete = false;for (int i = 0; i < array.length && !complete; i++) {complete = true; // 假設(shè)已經(jīng)完成了for (int j = 1; j < array.length - i; j++) {if (array[j - 1] > array[j]) {complete = false;int temp = array[j - 1];array[j - 1] = array[j];array[j] = temp;}}}}這樣在應(yīng)對(duì)某些比較特殊的情況下，會(huì)有一定的效果。
?
再來(lái)想想這樣一個(gè)事實(shí)：最后產(chǎn)生交換的位置之后的元素是有序的。想像一下，如果一個(gè)數(shù)組只是前半部分的元素是無(wú)序的，那么我們實(shí)際上只需要遍歷到無(wú)序的位置即可，其實(shí)我們上前面的算法中array.length – i這一步已經(jīng)是做了類(lèi)似的工作，因?yàn)槲覀冎篮竺嬉呀?jīng)有i個(gè)元素是有序的了。所以我們可以得到第三個(gè)版本的冒泡：
// 升級(jí)版2// 基于這樣一個(gè)事實(shí)，如果最后的數(shù)據(jù)交換位置之后的元素是有序的// 所以，這個(gè)也是基于版本1的再一次加強(qiáng)public static void sort3(int[] array) {int flag = array.length; // 用于標(biāo)識(shí)元素的最后的位置while (flag != 0) { // 為0說(shuō)明沒(méi)有發(fā)生數(shù)據(jù)的交換int last = flag;flag = 0;for (int j = 1; j < last; j++) {if (array[j - 1] > array[j]) {flag = j;int temp = array[j - 1];array[j - 1] = array[j];array[j] = temp;}}}}選擇排序（Selection Sort）：
選擇排序也是比較好理解的，每次從左到右掃描一次，可以得到最大的（或最小的）元素的下標(biāo)，然后我們?cè)侔阉c數(shù)組末尾（或者開(kāi)頭）的元素進(jìn)行交換，這樣每一次都可以找到一個(gè)最大的。實(shí)現(xiàn)起來(lái)也是很簡(jiǎn)單的：
// 每次從中選出最小的元素，只進(jìn)行一次交換// 相比冒泡，大大減少了元素的交換次數(shù)public static void sort(int[] array) {for (int i = 0; i < array.length; i++) { // 確定了多少個(gè)元素int min = i; // 每次都默認(rèn)第一個(gè)是最小的for (int j = i + 1; j < array.length; j++) {if (array[min] > array[j]) {min = j;}}int temp = array[min];array[min] = array[i];array[i] = temp;}}直接插入排序（Insertion Sort）：
直接插入排序的思路有點(diǎn)類(lèi)似于我們平時(shí)打牌時(shí)整理時(shí)的方法，比如我整理牌的方式是，右邊選擇，然后插入到左邊已經(jīng)整理好的牌中。
直接插入排序也是這樣：將要排序的元素分為有序區(qū)和無(wú)序區(qū)。每次從無(wú)序區(qū)拿出一個(gè)元素，然后在有序區(qū)找到自己的位置，強(qiáng)勢(shì)插入。
public static void sort(int[] array) {for (int i = 1; i < array.length; i++) { // 默認(rèn)第一個(gè)是有序的int temp = array[i]; // 拿出要插入的數(shù)據(jù)int j = i;// 尋找插入位置while (j > 0 && temp < array[j - 1]) {array[j] = array[j - 1];j--;}array[j] = temp;}}對(duì)于直接插入排序來(lái)說(shuō)，經(jīng)常用到一個(gè)“優(yōu)化”就是使用數(shù)組的第0個(gè)元素來(lái)放置要插入的數(shù)據(jù)，這樣做有一個(gè)好處就是不用每次都去檢查j指針是否小于0。理論上可以節(jié)省點(diǎn)時(shí)間。
另一種優(yōu)化就是可以在查找插入位置的時(shí)候可以通過(guò)二分查找來(lái)實(shí)現(xiàn)，也有一定的作用。
?
接下來(lái)看一下這三個(gè)算法的PK情況，為了加強(qiáng)對(duì)比我們找到了Java類(lèi)庫(kù)中的Arrays.sort()這個(gè)方法來(lái)參與PK，測(cè)試數(shù)據(jù)是50000個(gè)0到500000的整數(shù)。使用的是System.currentTimeMillis()這個(gè)方法來(lái)計(jì)時(shí)：
某幾次結(jié)果如下：
?
?
性能差別如此之大！顯然，這三個(gè)排序算法都“弱暴了”。
?
接下來(lái)來(lái)看看今天的第一個(gè)高級(jí)一點(diǎn)的算法，也就是傳說(shuō)中第一批被證明是突破了N的平方運(yùn)行時(shí)間的排序算法。
?
希爾排序（Shell Sort）:
先來(lái)看看具體的程序：
public static void sort(int[] array) {for (int step = array.length / 2; step > 0; step /= 2) {for (int i = step; i < array.length; i++) {int temp = array[i];int j = i;while (j >= step && temp < array[j - step]) {array[j] = array[j - step];j -= step;}array[j] = temp;}}}這~~~看起來(lái)是如此簡(jiǎn)單的代碼。很難想像它有什么牛X之處。我還記得當(dāng)時(shí)這個(gè)算法真是把我給糾結(jié)了很久，從代碼上看，它有兩個(gè)for循環(huán)嵌套，里面還有一個(gè)while循環(huán)。看起來(lái)時(shí)間復(fù)雜度很像是N的三次方吧。
再有，當(dāng)step為1的時(shí)候，看看，是不是和直接插入排序的代碼是一模一樣的。那這個(gè)算法怎么可能會(huì)快啊！
?
希爾排序有時(shí)被叫做縮減增量排序（diminishing increment sort），使用一個(gè)序列h1，h2，h3……這樣一個(gè)增量序列。只要h1=1時(shí)，任何增量序列都是可以的。但有些可能更好。對(duì)于希爾排序?yàn)槭裁磿?huì)比直接插入排序快的原因，我們可以來(lái)看一個(gè)比較極端的例子：
假如對(duì)于一個(gè)數(shù)組｛8，7，6，5，4，3，2，1｝以從小到大的順序來(lái)排。直接插入排序顯然是很悲劇的了。
它的每次排序結(jié)果是這樣的：
7, 8, 6, 5, 4, 3, 2, 1
?
6, 7, 8, 5, 4, 3, 2, 1
?
5, 6, 7, 8, 4, 3, 2, 1
?
4, 5, 6, 7, 8, 3, 2, 1
?
3, 4, 5, 6, 7, 8, 2, 1
?
2, 3, 4, 5, 6, 7, 8, 1
?
1, 2, 3, 4, 5, 6, 7, 8
?
然后我們來(lái)看看Shell排序會(huì)怎樣處理，一開(kāi)始步長(zhǎng)為4
數(shù)組分為8, 7, 6, 5和4, 3, 2, 1
首先是7和4進(jìn)行比較，交換位置。
變成了4, 7, 6, 5和8, 3, 2, 1
同理7和3，6和2，5和1也是樣的，所以當(dāng)步長(zhǎng)為4時(shí)的結(jié)果是：
4, 3, 2, 1, 8, 7, 6, 5
可以看到，大的數(shù)都在后邊了。
接下來(lái)的步長(zhǎng)為2
這一步過(guò)程就多了很多：
一開(kāi)始是4和2進(jìn)行比較，交換，得到：
2, 3, 4, 1, 8, 7, 6, 5
3和1比較，交換，得到：
2, 1, 4, 3, 8, 7, 6, 5
接下來(lái)是4和8，3和7，這兩個(gè)比較沒(méi)有元素交換。接下來(lái)8和6，7和5就需要交換了。所以步長(zhǎng)為2時(shí)的結(jié)果就是：
2, 1, 4, 3, 6, 5, 8, 7
可以明顯地感覺(jué)到，數(shù)組變得“基本有序”了。
接下來(lái)的步長(zhǎng)1，變成了直接插入排序。手動(dòng)模擬一下就可以發(fā)現(xiàn)，元素的交換次數(shù)只有四次！這是相當(dāng)可觀的。也由此我們可以得到一個(gè)基本的事實(shí)：對(duì)于基本有序的數(shù)組，使用直接插入排序的效率是很高的！
?
那回到我們一開(kāi)始的問(wèn)題，希爾排序?yàn)槭裁磿?huì)快？
首先說(shuō)明一下，我上邊的例子是極端的，不能作為正常情況來(lái)看的。但我們可以看出一點(diǎn)端倪：
希爾排序?qū)υ氐囊苿?dòng)效率比直接排序要高；比如我們看第一個(gè)步長(zhǎng)4時(shí)，直接就把4，3，2，1這四個(gè)元素的位置向前移動(dòng)了4位，比起直接插入排序的一次進(jìn)一步要明顯高效得多。
?
其次，希爾每次都將數(shù)據(jù)變得“更加有序”；這一個(gè)性質(zhì)相當(dāng)重要，因?yàn)樗昧松弦淮蔚呐判蚪Y(jié)果，在此之上讓數(shù)據(jù)向“更加有序”更進(jìn)一步。
?
最后，是一個(gè)觀察的事實(shí)，就是對(duì)于“基本有序”的數(shù)組而言，直接插入排序的效率是很高的，因?yàn)橹恍枰粨Q少量的元素。
?
好的，我們?cè)賮?lái)看看我們寫(xiě)的shell排序的效率怎樣：這一次是兩個(gè)重量級(jí)的選手，所以我們把數(shù)據(jù)量提高到500000，看看shell排序和類(lèi)庫(kù)中那個(gè)實(shí)現(xiàn)有多大的差距：
?
?
還是有差距，但比起上次那秒殺級(jí)的差距這個(gè)結(jié)果絕對(duì)可以接受了。要知道，類(lèi)庫(kù)個(gè)的那個(gè)算法可以用了“老長(zhǎng)老長(zhǎng)”的代碼~~~
?
還有三個(gè)比較麻煩的算法。一次是講不完的了。
先總結(jié)一下個(gè)人的一點(diǎn)體會(huì)：
對(duì)于排序而言，提高速度的方法明顯的有兩個(gè)，一個(gè)是減少數(shù)據(jù)的比較次數(shù)，一個(gè)是減少交換次數(shù)。
對(duì)于冒泡來(lái)說(shuō)，它這兩個(gè)方法都是最差的。
而選擇排序明顯就減少了交換的次數(shù)。
而直接插入排序顯然在比較次數(shù)上要比選擇要少，因?yàn)槲覀兪菑挠抑磷笳业胶线m的位置就停止。
而希爾排序相對(duì)于直接插入排序在數(shù)據(jù)交換次數(shù)上，要少得多。另外就是很好的利用了“基本有序”這個(gè)性質(zhì)。在比較次數(shù)上也會(huì)少很多。
?
本身菜鳥(niǎo)一個(gè)，這些都是個(gè)人的總結(jié)，認(rèn)識(shí)不足、甚至錯(cuò)誤在所難免。希望各位指出。
轉(zhuǎn)載于:https://www.cnblogs.com/yjiyjige/p/3256138.html
總結(jié)
以上是生活随笔為你收集整理的七大排序的个人总结（一）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 如何解决安卓SDK无法下载Package
- 下一篇： ylbtech-数据库设计与优化-对作为