快速排序及優(yōu)化

quicksort可以說是應(yīng)用最廣泛的排序算法之一,它的基本思想是分治法屯援,選擇一個pivot(中軸點)矿筝,將小于pivot放在左邊鸯乃,將大于 pivot放在右邊,針對左右兩個子序列重復(fù)此過程跋涣,直到序列為空或者只有一個元素缨睡。這篇blog主要目的是關(guān)注quicksort可能的改進方法,并對 這些改進方法做評測陈辱。其目的是為了理解Arrays.sort(int [ ]a)的實現(xiàn)奖年。實現(xiàn)本身有paper介紹。

quicksort一個教科書式的簡單實現(xiàn)沛贪,采用左端點做pivot(《算法導(dǎo)論》上偽代碼是以右端點做pivot):

[java]

public void qsort1(int[] a, int p, int r) {

// 0個或1個元素陋守,返回

if (p >= r)

return;

// 選擇左端點為pivot

int x = a[p];

int j = p;

for (int i = p + 1; i <= r; i++) {

// 小于pivot的放到左邊

if (a[i] < x) {

swap(a, ++j, i);

}

}

// 交換左端點和pivot位置

swap(a, p, j);

// 遞歸子序列

qsort1(a, p, j - 1);

qsort1(a, j + 1, r);

}

[/java]

quicksort的最佳情況下的時間復(fù)雜度O(n logn)震贵,最壞情況下的時間復(fù)雜度是O(n^2),退化到插入排序的最壞情況水评,平均情況下的平均復(fù)雜度接近于最佳情況也就是O(nlog n)猩系,這也是基于比較的排序算法的比較次數(shù)下限。

為了對排序算法的性能改進有個直觀的對比中燥,我們建立一個測試基準寇甸,分別測試隨機數(shù)組的排序、升序數(shù)組的排序疗涉、降序數(shù)組的排序以及重復(fù)元素的數(shù)組排序拿霉。首先 使用java.util.Arrays.sort建立一個評測基準,注意這里的時間單位是秒咱扣,這些絕對時間沒有意義绽淘,我們關(guān)注的是相對值,因此這里我不會 列出詳細的評測程序:

算法

隨機數(shù)組

升序數(shù)組

降序數(shù)組

重復(fù)數(shù)組

Arrays.sort

136.293

0.548

0.524

26.822

qsort1對于輸入做了假設(shè)闹伪,假設(shè)輸入是隨機的數(shù)組沪铭,如果排序已經(jīng)排序的數(shù)組,qsort1馬上退化到O(n^2)的復(fù)雜度偏瓤,這是由于選定的pivot每次都會跟剩余的所有元素做比較杀怠。它跟Arrays.sort的比較:

算法

隨機數(shù)組

升序數(shù)組

降序數(shù)組

重復(fù)數(shù)組

Arrays.sort

136.293

0.548

0.524

26.822

qsort1

134.475

48.498

141.968

45.244

果然,在排序已經(jīng)排序的數(shù)組的時候硼补,qsort的性能跟Arrays.sort的差距太大了驮肉。那么我們能做的第一個優(yōu)化是什么熏矿?答案是將pivot的選擇隨機化已骇,不再是固定選擇左端點,而是利用隨機數(shù)產(chǎn)生器選擇一個有效的位置作為pivot票编,這就是qsort2:

[java]

public void qsort2(int[] a, int p, int r) {

// 0個或1個元素褪储,返回

if (p >= r)

return;

// 隨機選擇pivot

int i = p + rand.nextInt(r - p + 1);

// 交換pivot和左端點

swap(a, p, i);

// 劃分算法不變

int x = a[p];

int j = p;

for (i = p + 1; i <= r; i++) {

// 小于pivot的放到左邊

if (a[i] < x) {

swap(a, ++j, i);

}

}

// 交換左端點和pivot位置

swap(a, p, j);

// 遞歸子序列

qsort2(a, p, j - 1);

qsort2(a, j + 1, r);

}

[/java]

再次進行測試,查看qsort1和qsort2的對比:

算法

隨機數(shù)組

升序數(shù)組

降序數(shù)組

重復(fù)數(shù)組

qsort1

134.475

48.498

141.968

45.244

qsort2

227.87

19.009

18.597

74.639

從隨機數(shù)組的排序來看慧域,qsort2比之qsort1還有所下降鲤竹,這主要是隨機數(shù)產(chǎn)生器帶來的消耗,但是在已經(jīng)排序數(shù)組的排序上面昔榴,qsort2有很大進步辛藻,在有大量隨機重復(fù)元素的數(shù)組排序上,qsort2卻有所下降互订,主要消耗也是來自隨機數(shù)產(chǎn)生器的影響吱肌。

更進一步的優(yōu)化是在劃分算法上,現(xiàn)在的劃分算法只使用了一個索引i仰禽,i從左向右掃描氮墨,遇到比pivot小的纺蛆,就跟從p+1開始的位置(由j索引進行遞增標 志)進行交換,最終的劃分點落在了j规揪,然后將pivot調(diào)換到j(luò)上桥氏,再遞歸排序左右兩邊子序列。一個更高效的劃分過程是使用兩個索引i和j猛铅,分別從左右兩 端進行掃描字支,i掃描到大于等于pivot的元素就停止,j掃描到小于等于pivot的元素也停止奕坟,交換兩個元素祥款,持續(xù)這個過程直到兩個索引相遇,此時的 pivot的位置就落在了j月杉,然后交換pivot和j的位置刃跛,后續(xù)的工作沒有不同,示意圖

改進后的qsort3代碼如下:

[java]

public void qsort3(int[] a, int p, int r) {

if (p >= r)

return;

// 隨機選

int i = p + rand.nextInt(r - p + 1);

swap(a, p, i);

// 左索引i指向左端點

i = p;

// 右索引j初始指向右端點

int j = r + 1;

int x = a[p];

while (true) {

// 查找比x大于等于的位置

do {

i++;

} while (i <= r && a[i] < x);

// 查找比x小于等于的位置

do {

j--;

} while (a[j] > x);

if (j < i)

break;

// 交換a[i]和a[j]

swap(a, i, j);

}

swap(a, p, j);

qsort3(a, p, j - 1);

qsort3(a, j + 1, r);

}

[/java]

這里要用do……while是因為i索引的初始位置是pivot值存儲的左端點,而j所在初始位置是右端點之外苛萎,因此都需要先移動一個位置才是合法的桨昙。查看下qsort2和qsort3的基準測試對比:

算法

隨機數(shù)組

升序數(shù)組

降序數(shù)組

重復(fù)數(shù)組

qsort2

227.87

19.009

18.597

74.639

qsort3

229.44

18.696

18.507

43.428

可以看到qsort3的改進主要體現(xiàn)在了大量重復(fù)元素的數(shù)組的排序上,這是因為qsort3在遇到跟pivot相等的元素的時候腌歉,還是進行停止并交換蛙酪,而 非跳過;假設(shè)遇到相等的元素你不停止翘盖,那么這些相等的元素在下次劃分的時候需要再次進行比較桂塞,比較次數(shù)退化到最差情況的O(n^2),而通過在遇到相等元 素的時候停止并交換馍驯,盡管增加了交換的次數(shù)阁危,但是卻避免了所有元素相同情況下最差情況的發(fā)生。

改進到這里汰瘫,回頭看看我們做了什么狂打,首先是使用隨機挑選pivot替代固定選擇,其次是改進了劃分算法混弥,從兩端進行掃描替代單向查找趴乡,并仔細處理元素相同的情況。

插入排序的時間復(fù)雜度是O(N^2)蝗拿,但是在已經(jīng)排序好的數(shù)組上面晾捏,插入排序的最佳情況是O(n),插入排序在小數(shù)組的排序上是非常高效的哀托,這給我們一個 提示惦辛,在快速排序遞歸的子序列,如果序列規(guī)模足夠小萤捆,可以使用插入排序替代快速排序裙品,因此可以在快排之前判斷數(shù)組大小俗批,如果小于一個閥值就使用插入排序, 這就是qsort4:

[java]

public void qsort4(int[] a, int p, int r) {

if (p >= r)

return;

// 在數(shù)組大小小于7的情況下使用快速排序

if (r - p + 1 < 7) {

for (int i = p; i <= r; i++) {

for (int j = i; j > p && a[j - 1] > a[j]; j--) {

swap(a, j, j - 1);

}

}

return;

}

int i = p + rand.nextInt(r - p + 1);

swap(a, p, i);

i = p;

int j = r + 1;

int x = a[p];

while (true) {

do {

i++;

} while (i <= r && a[i] < x);

do {

j--;

} while (a[j] > x);

if (j < i)

break;

swap(a, i, j);

}

swap(a, p, j);

qsort4(a, p, j - 1);

qsort4(a, j + 1, r);

}

[/java]

如果數(shù)組大小小于7就使用插入排序市怎,7這個數(shù)字完全是經(jīng)驗值岁忘。查看qsort3和qsort4的測試比較:

算法

隨機數(shù)組

升序數(shù)組

降序數(shù)組

重復(fù)數(shù)組

qsort3

229.44

18.696

18.507

43.428

qsort4

173.201

7.436

7.477

32.195

qsort4改進的效果非常明顯,所有基準測試的結(jié)果都取得了明顯的進步区匠。qsort4還有一種變形干像,現(xiàn)在是在每個遞歸的子序列上進行插入排序,也可以換一種形式驰弄,當(dāng)小于某個特定閥值的時候直接返回不進行任何排序麻汰,在遞歸返回之后,對整個數(shù)組進行一次插入排序戚篙,這個時候整個數(shù)組是由一個一個沒有排序的子序列按照順序組成的五鲫,因此插入排序可以很快地將整個數(shù)組排序,這個變形的qsort5跟qsort4沒有本質(zhì)上的不同:

[java]

public void qsort5(int[] a, int p, int r) {

if (p >= r)

return;

// 遞歸子序列岔擂,并且數(shù)組大小小于7位喂,直接返回

if (p != 0 && r!=(a.length-1) && r - p + 1 < 7)

return;

// 隨機選

int i = p + rand.nextInt(r - p + 1);

swap(a, p, i);

i = p;

int j = r + 1;

int x = a[p];

while (true) {

do {

i++;

} while (i <= r && a[i] < x);

do {

j--;

} while (a[j] > x);

if (j < i)

break;

swap(a, i, j);

}

swap(a, p, j);

qsort5(a, p, j - 1);

qsort5(a, j + 1, r);

// 最后對整個數(shù)組進行插入排序

if (p == 0 && r==a.length-1) {

for (i = 0; i <= r; i++) {

for (j = i; j > 0 && a[j - 1] > a[j]; j--) {

swap(a, j, j - 1);

}

}

return;

}

}

[/java]

基準測試的結(jié)果也證明了qsort4和qsort5是一樣的:

算法

隨機數(shù)組

升序數(shù)組

降序數(shù)組

重復(fù)數(shù)組

qsort4

173.201

7.436

7.477

32.195

qsort5

175.031

7.324

7.453

32.322

現(xiàn)在,最大的開銷還是隨機數(shù)產(chǎn)生器選擇pivot帶來的開銷乱灵,我們用隨機數(shù)產(chǎn)生器來選擇pivot塑崖,是希望pivot能盡量將數(shù)組劃分得均勻一些,可以選 擇一個替代方案來替代隨機數(shù)產(chǎn)生器來選擇pivot痛倚,比如三數(shù)取中规婆,通過對序列的first、middle和last做比較蝉稳,選擇三個數(shù)的中間大小的那一 個做pivot抒蚜,從概率上可以將比較次數(shù)下降到12/7 ln(n)。

median-of-three對小數(shù)組來說有很大的概率選擇到一個比較好的pivot颠区,但是對于大數(shù)組來說就不足以保證能夠選擇出一個好的pivot削锰, 因此還有個辦法是所謂median-of-nine通铲,這個怎么做呢毕莱?它是先從數(shù)組中分三次取樣,每次取三個數(shù)颅夺,三個樣品各取出中數(shù)朋截,然后從這三個中數(shù)當(dāng)中 再取出一個中數(shù)作為pivot,也就是median-of-medians吧黄。取樣也不是亂來部服,分別是在左端點、中點和右端點取樣拗慨。什么時候采用 median-of-nine去選擇pivot廓八,這里也有個數(shù)組大小的閥值奉芦,這個值也完全是經(jīng)驗值,設(shè)定在40剧蹂,大小大于40的數(shù)組使用median-of-nine選擇pivot声功,大小在7到40之間的數(shù)組使用three-of-median選擇pivot,大小等于7的數(shù)組直接選擇中數(shù)作為pivot,大小小于7的數(shù)組則直接使用插入排序宠叼,這就是改進后的qsort6先巴,已經(jīng)非常接近于Arrays.sort的實現(xiàn):

[java]

public void qsort6(int[] a, int p, int r) {

if (p >= r)

return;

// 在數(shù)組大小小于7的情況下使用快速排序

if (r - p + 1 < 7) {

for (int i = p; i <= r; i++) {

for (int j = i; j > p && a[j - 1] > a[j]; j--) {

swap(a, j, j - 1);

}

}

return;

}

// 計算數(shù)組長度

int len = r - p + 1;

// 求出中點,大小等于7的數(shù)組選擇pivot

int m = p + (len >> 1);

// 大小大于7

if (len > 7) {

int l = p;

int n = p + len - 1;

if (len > 40) { // 大數(shù)組冒冬,采用median-of-nine選擇

int s = len / 8;

l = med3(a, l, l + s, l + 2 * s); // 取樣左端點3個數(shù)并得出中數(shù)

m = med3(a, m - s, m, m + s); // 取樣中點3個數(shù)并得出中數(shù)

n = med3(a, n - 2 * s, n - s, n); // 取樣右端點3個數(shù)并得出中數(shù)

}

m = med3(a, l, m, n); // 取中數(shù)中的中數(shù)

}

// 交換pivot到左端點伸蚯,后面的操作與qsort4相同

swap(a, p, m);

m = p;

int j = r + 1;

int x = a[p];

while (true) {

do {

m++;

} while (m <= r && a[m] < x);

do {

j--;

} while (a[j] > x);

if (j < m)

break;

swap(a, m, j);

}

swap(a, p, j);

qsort6(a, p, j - 1);

qsort6(a, j + 1, r);

}

[/java]

其中的med3函數(shù)用于取三個數(shù)的中數(shù):

[java]

private static int med3(int x[], int a, int b, int c) {

return x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)

: x[b] > x[c] ? b : x[a] > x[c] ? c : a;

}

[/java]

運行基準測試跟qsort4進行比較:

算法

隨機數(shù)組

升序數(shù)組

降序數(shù)組

重復(fù)數(shù)組

qsort4

173.201

7.436

7.477

32.195

qsort6

143.264

0.54

0.836

27.311

觀察到qsort6的改進也非常明顯,消除了隨機產(chǎn)生器帶來的開銷简烤,取中數(shù)的時間復(fù)雜度在O(1)剂邮。此時qsort6跟Arrays.sort的差距已經(jīng) 非常小了。Array.sort所做的最后一個改進是針對劃分算法横侦,采用了所謂”split-end”的劃分算法抗斤,這主要是為了針對equals的元素, 降低equals元素參與遞歸的開銷丈咐。我們原來的劃分算法是分為兩個區(qū)域加上一個pivot:

跟pivot equals的元素分散在左右兩個子序列里瑞眼,繼續(xù)參與遞歸調(diào)用。當(dāng)數(shù)組里的相同元素很多的時候棵逊,這個開銷是不可忽視的伤疙,因此一個方案是將這些相同的元素集 中存放到中間這個地方,不參與后續(xù)的遞歸處理辆影,這就是”fat partition”徒像,此時是將數(shù)組劃分為3個區(qū)域:小于pivot,等于pivot以及大于pivot:

但是Arrays.sort采用的卻不是”fat partition”蛙讥,這是因為fat partition的實現(xiàn)比較復(fù)雜并且低效锯蛀,Arrays.sort是將與pivot相同的元素劃分到兩端,也就是將數(shù)組分為了4個區(qū)域:

這就是split-end名稱的由來次慢,這個算法的實現(xiàn)可以跟qsort3的改進結(jié)合起來旁涤,同樣是進行兩端掃描,但是遇到equals的元素不是進行互換迫像, 而是各自交換到兩端劈愚。當(dāng)掃描結(jié)束,還要將兩端這些跟pivot equals的元素交換到中間位置闻妓,不相同的元素交換到兩端菌羽,左邊仍然是比pivot小的,右邊是比pivot大的由缆,分別進行遞歸的快速排序處理注祖,這樣改 進后的算法我們成為qsort7:

[java]

public void qsort7(int[] x, int p, int r) {

if (p >= r)

return;

// 在數(shù)組大小小于7的情況下使用快速排序

if (r - p + 1 < 7) {

for (int i = p; i <= r; i++) {

for (int j = i; j > p && x[j - 1] > x[j]; j--) {

swap(x, j, j - 1);

}

}

return;

}

// 選擇中數(shù)猾蒂,與qsort6相同。

int len = r - p + 1;

int m = p + (len >> 1);

if (len > 7) {

int l = p;

int n = p + len - 1;

if (len > 40) {

int s = len / 8;

l = med3(x, l, l + s, l + 2 * s);

m = med3(x, m - s, m, m + s);

n = med3(x, n - 2 * s, n - s, n);

}

m = med3(x, l, m, n);

}

int v = x[m];

// a,b進行左端掃描是晨,c,d進行右端掃描

int a = p, b = a, c = p + len - 1, d = c;

while (true) {

// 嘗試找到大于pivot的元素

while (b <= c && x[b] <= v) {

// 與pivot相同的交換到左端

if (x[b] == v)

swap(x, a++, b);

b++;

}

// 嘗試找到小于pivot的元素

while (c >= b && x[c] >= v) {

// 與pivot相同的交換到右端

if (x[c] == v)

swap(x, c, d--);

c--;

}

if (b > c)

break;

// 交換找到的元素

swap(x, b++, c--);

}

// 將相同的元素交換到中間

int s, n = p + len;

s = Math.min(a - p, b - a);

vecswap(x, p, b - s, s);

s = Math.min(d - c, n - d - 1);

vecswap(x, b, n - s, s);

// 遞歸調(diào)用子序列

if ((s = b - a) > 1)

qsort7(x, p, s + p - 1);

if ((s = d - c) > 1)

qsort7(x, n - s, n - 1);

}

[/java]

其中用到了vecswap方法用于批量交換一批數(shù)據(jù)婚夫,將a位置(包括a)之后n個元素與b位置(包括b)之后n個元素進行交換:

[java]

private static void vecswap(int x[], int a, int b, int n) {

for (int i = 0; i < n; i++, a++, b++)

swap(x, a, b);

}

[/java]

主要是用于劃分后將兩端與pivot相同的元素交換到中間來。qsort7的實現(xiàn)跟Arrays.sort的實現(xiàn)是一樣的署鸡,看看split-end劃分帶來的改進跟qsort6的對比:

算法

隨機數(shù)組

升序數(shù)組

降序數(shù)組

重復(fù)數(shù)組

qsort6

143.264

0.54

0.836

27.311

qsort6

140.468

0.491

0.506

26.639

這個結(jié)果跟Arrays.sort保持一致案糙。

最后給幾張7個快排程序的在4種測試中的對比圖

還可以做的優(yōu)化:

1、內(nèi)聯(lián)swap和vecswap函數(shù)靴庆,循環(huán)中的swap調(diào)用可以展開时捌。

2、改進插入排序炉抒,這是《編程珠璣》里提到的奢讨,減少取值次數(shù)。

[java]

for (int i = p; i <= r; i++) {

int t = x[i];

int j = i;

for (; j > p && x[j - 1] > t; j–) {

x[j] = x[j - 1];

}

x[j] = t;

}

[/java]

3焰薄、遞歸可以展開為循環(huán)拿诸,最后一個遞歸調(diào)用是尾遞歸調(diào)用,很容易展開為循環(huán)塞茅,左子序列的遞歸調(diào)用就沒那么容易展開了亩码。

4、嘗試更多取樣算法來提高選擇好的pivot的概率野瘦。

5描沟、遞歸處理并行化

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市鞭光,隨后出現(xiàn)的幾起案子吏廉,更是在濱河造成了極大的恐慌,老刑警劉巖惰许,帶你破解...
    沈念sama閱讀 216,402評論 6 499
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件席覆,死亡現(xiàn)場離奇詭異,居然都是意外死亡汹买,警方通過查閱死者的電腦和手機佩伤,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,377評論 3 392
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來卦睹,“玉大人畦戒,你說我怎么就攤上這事方库〗嵝颍” “怎么了?”我有些...
    開封第一講書人閱讀 162,483評論 0 353
  • 文/不壞的土叔 我叫張陵纵潦,是天一觀的道長徐鹤。 經(jīng)常有香客問我垃环,道長,這世上最難降的妖魔是什么返敬? 我笑而不...
    開封第一講書人閱讀 58,165評論 1 292
  • 正文 為了忘掉前任遂庄,我火速辦了婚禮,結(jié)果婚禮上劲赠,老公的妹妹穿的比我還像新娘涛目。我一直安慰自己,他們只是感情好凛澎,可當(dāng)我...
    茶點故事閱讀 67,176評論 6 388
  • 文/花漫 我一把揭開白布霹肝。 她就那樣靜靜地躺著,像睡著了一般塑煎。 火紅的嫁衣襯著肌膚如雪沫换。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,146評論 1 297
  • 那天最铁,我揣著相機與錄音讯赏,去河邊找鬼。 笑死冷尉,一個胖子當(dāng)著我的面吹牛漱挎,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播雀哨,決...
    沈念sama閱讀 40,032評論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼识樱,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了震束?” 一聲冷哼從身側(cè)響起怜庸,我...
    開封第一講書人閱讀 38,896評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎垢村,沒想到半個月后割疾,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,311評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡嘉栓,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,536評論 2 332
  • 正文 我和宋清朗相戀三年宏榕,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片侵佃。...
    茶點故事閱讀 39,696評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡麻昼,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出馋辈,到底是詐尸還是另有隱情抚芦,我是刑警寧澤,帶...
    沈念sama閱讀 35,413評論 5 343
  • 正文 年R本政府宣布,位于F島的核電站叉抡,受9級特大地震影響尔崔,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜褥民,卻給世界環(huán)境...
    茶點故事閱讀 41,008評論 3 325
  • 文/蒙蒙 一季春、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧消返,春花似錦载弄、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至秦驯,卻和暖如春尺碰,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背译隘。 一陣腳步聲響...
    開封第一講書人閱讀 32,815評論 1 269
  • 我被黑心中介騙來泰國打工亲桥, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人固耘。 一個月前我還...
    沈念sama閱讀 47,698評論 2 368
  • 正文 我出身青樓题篷,卻偏偏與公主長得像,于是被迫代替她去往敵國和親厅目。 傳聞我的和親對象是個殘疾皇子番枚,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,592評論 2 353

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪:刷leetcod...
    土汪閱讀 12,743評論 0 33
  • 概述 排序有內(nèi)部排序和外部排序损敷,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序葫笼,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部...
    蟻前閱讀 5,183評論 0 52
  • 概述:排序有內(nèi)部排序和外部排序拗馒,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序路星,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部...
    每天刷兩次牙閱讀 3,730評論 0 15
  • 總結(jié)一下常見的排序算法诱桂。 排序分內(nèi)排序和外排序洋丐。內(nèi)排序:指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序。外排序:指在排序...
    jiangliang閱讀 1,338評論 0 1
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 將一個記錄插入到已排序好...
    依依玖玥閱讀 1,253評論 0 2