我一直覺(jué)得寫(xiě)代碼也可以寫(xiě)出藝術(shù)，在不懂畫(huà)的人的眼里，《向日葵》不過(guò)是小孩子的涂鴉，在懂代碼的人眼里，那看似混亂的字符，確是邏輯藝術(shù)的完美體現(xiàn)。

排序算法基礎(chǔ)

排序算法，是一種能將一串?dāng)?shù)據(jù)按照特定的排序方式進(jìn)行排列的一種算法，一個(gè)排序算法的好壞，主要從時(shí)間復(fù)雜度，空間復(fù)雜度，穩(wěn)定性來(lái)衡量。

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度是一個(gè)函數(shù)，它描述了該算法的運(yùn)行時(shí)間，考察的是當(dāng)輸入值大小趨近無(wú)窮時(shí)的情況。數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用這個(gè)大 O 符號(hào)用來(lái)標(biāo)記不同”階“的無(wú)窮大。這里的無(wú)窮被認(rèn)為是一個(gè)超越邊界而增加的概念，而不是一個(gè)數(shù)。

想了解時(shí)間復(fù)雜度，我想講講常見(jiàn)的 O(1)，O(log n)，O(n)，O(n log n)，O(n^2) ，計(jì)算時(shí)間復(fù)雜度的過(guò)程，常常需要分析一個(gè)算法運(yùn)行過(guò)程中需要的基本操作，計(jì)量所有操作的數(shù)量。

O（1）常數(shù)時(shí)間

O（1）中的 1 并不是指時(shí)間為 1，也不是操作數(shù)量為 1，而是表示操作次數(shù)為一個(gè)常數(shù)，不因?yàn)檩斎?n 的大小而改變，比如哈希表里存放 1000 個(gè)數(shù)據(jù)或者 10000 個(gè)數(shù)據(jù)，通過(guò)哈希碼查找數(shù)據(jù)時(shí)所需要的操作次數(shù)都是一樣的，而操作次數(shù)和時(shí)間是成線性關(guān)系的，所以時(shí)間復(fù)雜度為 O（1）的算法所消耗的時(shí)間為常數(shù)時(shí)間。

O（log n）對(duì)數(shù)時(shí)間

O（log n）中的 log n 是一種簡(jiǎn)寫(xiě)，loga n 稱作為以 a 為底 n 的對(duì)數(shù)，log n 省略掉了 a，所以 log n 可能是 log2 n，也可能是 log10 n。但不論對(duì)數(shù)的底是多少，O（log n）是對(duì)數(shù)時(shí)間算法的標(biāo)準(zhǔn)記法，對(duì)數(shù)時(shí)間是非常有效率的，例如有序數(shù)組中的二分查找，假設(shè) 1000 個(gè)數(shù)據(jù)查找需要 1 單位的時(shí)間， 1000,000 個(gè)數(shù)據(jù)查找則只需要 2 個(gè)單位的時(shí)間，數(shù)據(jù)量平方了但時(shí)間只不過(guò)是翻倍了。如果一個(gè)算法他實(shí)際的得操作數(shù)是 log2 n + 1000， 那它的時(shí)間復(fù)雜度依舊是 log n， 而不是 log n + 1000，時(shí)間復(fù)雜度可被稱為是漸近時(shí)間復(fù)雜度，在 n 極大的情況，1000 相對(duì) 與 log2 n 是極小的，所以 log2 n + 1000 與 log2 n 漸進(jìn)等價(jià)。

O（n）線性時(shí)間

如果一個(gè)算法的時(shí)間復(fù)雜度為 O(n)，則稱這個(gè)算法具有線性時(shí)間，或 O(n) 時(shí)間。這意味著對(duì)于足夠大的輸入，運(yùn)行時(shí)間增加的大小與輸入成線性關(guān)系。例如，一個(gè)計(jì)算列表所有元素的和的程序，需要的時(shí)間與列表的長(zhǎng)度成正比。遍歷無(wú)序數(shù)組尋最大數(shù)，所需要的時(shí)間也與列表的長(zhǎng)度成正比。

O（n log n）線性對(duì)數(shù)時(shí)間

排序算法中的快速排序的時(shí)間復(fù)雜度即 O（n log n），它通過(guò)遞歸 log2n 次，每次遍歷所有元素，所以總的時(shí)間復(fù)雜度則為二者之積， 復(fù)雜度既 O（n log n）。

O（n^2）二次時(shí)間

冒泡排序的時(shí)間復(fù)雜度既為 O（n^2），它通過(guò)平均時(shí)間復(fù)雜度為 O（n）的算法找到數(shù)組中最小的數(shù)放置在爭(zhēng)取的位置，而它需要尋找 n 次，不難理解它的時(shí)間復(fù)雜度為 O（n^2）。時(shí)間復(fù)雜度為 O（n^2）的算法在處理大數(shù)據(jù)時(shí)，是非常耗時(shí)的算法，例如處理 1000 個(gè)數(shù)據(jù)的時(shí)間為 1 個(gè)單位的時(shí)間，那么 1000,000 數(shù)據(jù)的處理時(shí)間既大約 1000,000 個(gè)單位的時(shí)間。

時(shí)間復(fù)雜度又有最優(yōu)時(shí)間復(fù)雜度，最差時(shí)間復(fù)雜度，平均時(shí)間復(fù)雜度。部分算法在對(duì)不同的數(shù)據(jù)進(jìn)行操作的時(shí)候，會(huì)有不同的時(shí)間消耗，如快速排序，最好的情況是 O（n log n），最差的情況是 O（n^2），而平均復(fù)雜度就是所有情況的平均值，例如快速排序計(jì)算平均復(fù)雜度的公式為

![Uploading image-2_542306.png . . .]

image-1.png

最后的結(jié)果就是 1.39n * log2 n，與 n * log2 n 漸進(jìn)等價(jià)，是的，1.3 倍在無(wú)窮大級(jí)別都不算什么，只要不和無(wú)窮大的 n 相關(guān)的乘數(shù)都可以通過(guò)漸進(jìn)等價(jià)省略掉。

空間復(fù)雜度

和時(shí)間復(fù)雜度一樣，有 O(1)，O(log n)，O(n)，O(n log n)，O(n^2)，等等，但談?wù)撍惴ǖ目臻g復(fù)雜度，往往講它的額外空間復(fù)雜度，例如冒泡排序算法只需要額外的常數(shù)空間，放置交換兩個(gè)相鄰數(shù)時(shí)產(chǎn)生的中間變量，及循環(huán)時(shí)候用來(lái)記錄循環(huán)次數(shù)的變量。所以冒泡排序的額外空間復(fù)雜度為 O(1)。如果算法所需的額外空間為 O(n)，則操作數(shù)據(jù)的數(shù)目和所需的空間成線性關(guān)系。

穩(wěn)定性

當(dāng)相等的元素是無(wú)法分辨的，比如像是整數(shù)，穩(wěn)定性并不是一個(gè)問(wèn)題。然而，假設(shè)以下的數(shù)對(duì)將要以他們的第一個(gè)數(shù)字來(lái)排序。

(4, 1)  (3, 1)  (3, 7) （5, 6）

在這個(gè)狀況下，有可能產(chǎn)生兩種不同的結(jié)果，一個(gè)是讓相等鍵值的紀(jì)錄維持相對(duì)的次序，而另外一個(gè)則沒(méi)有：

(3, 1)  (3, 7)  (4, 1)  (5, 6)  （維持次序）
(3, 7)  (3, 1)  (4, 1)  (5, 6)  （次序被改變）

不穩(wěn)定排序算法可能會(huì)在相等的鍵值中改變紀(jì)錄的相對(duì)次序，這導(dǎo)致我們無(wú)法準(zhǔn)確預(yù)料排序結(jié)果（除非你把數(shù)據(jù)在你的大腦里用該算法跑一遍），但是穩(wěn)定排序算法從來(lái)不會(huì)如此。例如冒泡排序即穩(wěn)定的存在，相等不交換則不打亂原有順序。而快速排序有時(shí)候則是不穩(wěn)定的。（不穩(wěn)定原因會(huì)在講快速排序時(shí)說(shuō)明。）

常見(jiàn)排序算法

冒泡排序

冒泡排序是一種非常簡(jiǎn)單的排序算法，4，5 行代碼就能實(shí)現(xiàn)，過(guò)程分為 4 個(gè)步驟：

• 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
• 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
• 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
• 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑?，?huì)經(jīng)由交換慢慢的“浮”到數(shù)列的尾端。冒泡排序?qū)?n 個(gè)項(xiàng)目需要 O(n^2) 的比較次數(shù)，且是在原地排序，所以額外空間復(fù)雜度為 O(1) 。盡管這個(gè)算法是最容易了解和實(shí)現(xiàn)的排序算法之一，但它相當(dāng)于其它數(shù)列排序來(lái)說(shuō)是很沒(méi)有效率的排序，如果元素不多，對(duì)性能也沒(méi)有太大要求，倒是可以快速寫(xiě)出冒泡排序來(lái)使用。博客中出現(xiàn)的代碼都由 C++ 編寫(xiě)。

void bubbleSort(int array[], int length) {
    int i, j;
    for (i = 0; i < length - 1 ;i++)
        for (j = 0; j < length - 1 - i; j++)
            if (array[j] > array[j + 1])
                swap(array[j], array[j+1]);
}

插入排序

插入排序簡(jiǎn)單直觀，通過(guò)構(gòu)建有序序列，對(duì)于未排序的元素，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。時(shí)間復(fù)雜度為 O(n^2) ，原地排序，額外空間復(fù)雜度為 O（1）。

過(guò)程分為 6 個(gè)步驟：

• 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序
• 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
• 如果該元素（已排序）大于新元素，將該元素移到下一位置
• 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
• 將新元素插入到該位置后
• 重復(fù)步驟2~5

void insertSort(int array[], int length) {
    int i, j;
    int temporary;
    //從第二個(gè)元素開(kāi)始，將元素插入到已排好序的元素里。
    for (i = 1; i < length; i++) {
        //需要插入的新元素
        temporary = array[i];
        //從已排序的元素序列中從后向前掃描，找到已排序的元素小于或者等于新元素的位置，將新元素
        //插入到該位置后
        for (j = i - 1; j >= 0 && array[j] > temporary; j--)
            array[j+1] = array[j];
        array[j+1] = temporary;
    }
}

選擇排序

選擇排序也是非常簡(jiǎn)單的排序算法，選擇最小先排序，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。時(shí)間復(fù)雜度為 O(n^2)，額外空間復(fù)雜度為 O(1)。

過(guò)程分為 5 個(gè)步驟：

• 從第一個(gè)元素開(kāi)始，聲明一個(gè)變量?jī)?chǔ)存最小元素的位置，初始為第一個(gè)元素的位置。
• 取出下一個(gè)元素，與當(dāng)前最小元素進(jìn)行比較。如果元素比當(dāng)前最小元素小，則變量?jī)?chǔ)存這個(gè)元素的位置。
• 重復(fù)步驟 2，直到?jīng)]有下一個(gè)元素，變量里儲(chǔ)存的既最小元素的位置。
• 將最小元素放在排序序列的起始位置。
• 重復(fù) 1~3，從剩余未排序元素中繼續(xù)尋找最小元素，然后放到已排序序列的末尾。

//選擇排序  平均時(shí)間復(fù)雜度O(n^2) 額外空間復(fù)雜度O(1)
void selectionSort(int array[], int length) {
    int i, j, min;
    for (i = 0; i < length; i++) {
        //找到最小元素存放到起始位置。
        min = i;
        for (j = i + 1; j < length; j++)
            if (array[j] < array[min])
                min = j;
        swap(array[i], array[min]);
    }
}

快速排序

快速排序從名字上來(lái)說(shuō)并不能直觀的記憶它的實(shí)現(xiàn)思路，但它和它的名字一樣，很快速，快速排序是一個(gè)非常不錯(cuò)的排序算法，時(shí)間復(fù)雜度 O(n log n)，且通常明顯比其他 Ο(n log n) 算法更快，這是最應(yīng)該記憶，并能熟練寫(xiě)出的排序算法。

步驟為：

• 從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"，
• 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)操作。遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

為了減少數(shù)組中不必要的移動(dòng)，挑最后一個(gè)元素為基準(zhǔn)，在剩下的元素的左右兩端開(kāi)始尋找，左邊找到比它大的，右邊找到比它小的，交換這個(gè)數(shù)的位置，繼續(xù)尋找，只需要很少的交換步驟，即可將比基準(zhǔn)大的和比基準(zhǔn)小的數(shù)分開(kāi)，最后左右兩端匯集在一起，匯集在一起有兩種情況。

• 第一種，左端匯集到右端身上，說(shuō)明匯集之前左端的值比基準(zhǔn)小，所以它需要向右移動(dòng)去尋找，如果右端的值已經(jīng)交換過(guò)了，則右端比基準(zhǔn)大，左右兩端已匯集，所以只要交換左端和基準(zhǔn)的值就可以了。如果右端的值還沒(méi)交換過(guò)，則與基準(zhǔn)值進(jìn)行比較，大于的話交換左端和基準(zhǔn)的值，小于的話，則說(shuō)明左邊的值都比基準(zhǔn)值小，去掉基準(zhǔn)值，剩下的數(shù)繼續(xù)快排。
• 第二種，右端匯集到左端身上，說(shuō)明左端找到了比基準(zhǔn)大的值，而匯集之前右端的值也比基準(zhǔn)大，所以也只要交換左端和基準(zhǔn)的值就可以了。

邏輯看起來(lái)很復(fù)雜，只是對(duì)遞歸到最深的地方對(duì)各種情況做處理。

void quickSortRecursive(int array[], int start, int end) {
    if (start >= end)
        return;
    //從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"。
    int mid = array[end];
    int left = start;
    int right = end - 1;
    while (left < right) {
        //從左開(kāi)始找，找到大于等于 mid 的數(shù)停止。
        while (array[left] < mid && left < right) left++;
        //從右開(kāi)始找，找到小于 mid 的數(shù)停止。
        while (array[right] >= mid && right > left) right--;
        //交換left和right位置的數(shù)
        swap(array[left], array[right]);
    }
    //使 left 位置數(shù)小于它左邊的數(shù)，大于它右邊的數(shù)。
    if (array[left] >= array[end])
        swap(array[left], array[end]);
    else
        left++;
    //遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序
    quickSortRecursive(array, start, left - 1);
    quickSortRecursive(array, left + 1, end);
}

為什么說(shuō)快速排序有時(shí)候是不穩(wěn)定的呢，如上面代碼所寫(xiě)，相等的都按比基準(zhǔn)小做處理，因?yàn)榛鶞?zhǔn)在最右端，所以順序不會(huì)變，這是穩(wěn)定的，但有時(shí)候快速排序?yàn)榱朔乐鼓承O端情況，（比如本身就是順序排序，這個(gè)時(shí)候時(shí)間復(fù)雜度就是 O(n^2)），往往挑選中間的數(shù)移至末尾作為基準(zhǔn)，這個(gè)時(shí)候就會(huì)打亂與基準(zhǔn)相等數(shù)的順序，就是不穩(wěn)定的。(所以這些排序算法重要的是思路，代碼是可以根據(jù)情況進(jìn)行改變的)

遞歸的時(shí)候由于函數(shù)調(diào)用是有時(shí)間和空間的消耗的，所以快速排序的空間復(fù)雜度并不是 O(1)，因?yàn)樽畈钋闆r，遞歸調(diào)用 n 次，所以最差空間復(fù)雜度為 O(n)，最好情況，遞歸調(diào)用 log n 次，所以最優(yōu)空間復(fù)雜度為 O(log n)，因?yàn)轭~外空間復(fù)雜度一般看最差情況，因?yàn)闀r(shí)間可以平均，但空間一定得滿足，所以它的額外空間復(fù)雜度為 O(n)。

堆排序

堆排序比其它排序更難理解一點(diǎn)，但堆排序很有意思，它需要利用堆這種數(shù)據(jù)結(jié)構(gòu)，堆是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。小于則是最小堆，根結(jié)點(diǎn)為堆的最小值，大于則是最大堆，根節(jié)點(diǎn)為堆得最大值。而堆排序則利用最大堆的性質(zhì)，一個(gè)一個(gè)找出最大數(shù)的值。堆可以通過(guò)數(shù)組來(lái)實(shí)現(xiàn)。下圖是一個(gè)一維數(shù)組，第一個(gè)元素是根節(jié)點(diǎn)，每一個(gè)父節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，可以從圖中得出這樣的規(guī)律，

• 父節(jié)點(diǎn) i 的左子節(jié)點(diǎn)在位置 (2 * i + 1);
• 父節(jié)點(diǎn) i 的右子節(jié)點(diǎn)在位置 (2 * i + 2);
• 子節(jié)點(diǎn) i 的父節(jié)點(diǎn)在位置 floor((i - 1) / 2);

image-3.png

floor 函數(shù)的作用是向下取整，所以左子節(jié)點(diǎn)右子節(jié)點(diǎn)都能通過(guò)這個(gè)公式找到正確的父節(jié)點(diǎn)。

先上代碼。

//堆排序  平均時(shí)間復(fù)雜度O(n log n) 額外空間復(fù)雜度O(1)
void maxHeap(int array[], int start, int end) {
    int dad = start;
    int son = dad * 2 + 1;
    while (son < end) {
        //比較兩個(gè)子節(jié)點(diǎn)的大小。
        if (son + 1 < end && array[son] < array[son + 1])
            son++;
        //如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)，直接返回。
        if (array[dad] > array[son])
            return;
        //如果父節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換父子節(jié)點(diǎn)，因?yàn)樽庸?jié)點(diǎn)變了，所以子節(jié)點(diǎn)可能比孫節(jié)點(diǎn)小，需繼續(xù)
        //比較。
        swap(array[dad], array[son]);
        dad = son;
        son = dad * 2 + 1;
    }
}

void heapSort(int array[], int length) {
    int i;
    //i從最后一個(gè)父節(jié)點(diǎn)開(kāi)始調(diào)整
    for (i = length / 2 - 1; i >= 0; i--) {
        //形成最大堆，第一個(gè)元素為最大數(shù)。
        maxHeap(array, i, length);
    }
    //將第一個(gè)元素放置到最后，再將前面的元素重新調(diào)整，得到最大堆，將此時(shí)最大的數(shù)放置到倒數(shù)第二
    //位置，如此反復(fù)。
    for (int i = length - 1; i > 0; i--) {
        swap(array[0], array[i]);
        maxHeap(array, 0, i);
    }
}

maxHeap 函數(shù)是用來(lái)使以此父節(jié)點(diǎn)作為根節(jié)點(diǎn)的堆為最大堆，先比較兩個(gè)子節(jié)點(diǎn)的大小，找到最大的子節(jié)點(diǎn)，再與根做比較，如果根大則已經(jīng)是最大堆，如果根小，則交換子節(jié)點(diǎn)和根節(jié)點(diǎn)的數(shù)據(jù)，此時(shí)子節(jié)點(diǎn)還得保證以它為根節(jié)點(diǎn)的堆為最大堆，所以還需要與孫節(jié)點(diǎn)進(jìn)行比較。函數(shù)結(jié)束既調(diào)整完畢。

heapSort 函數(shù)里先從最后一個(gè)父節(jié)點(diǎn)開(kāi)始調(diào)整，調(diào)整完的數(shù)與有序數(shù)列前一位交換，形成新的有序數(shù)列，此時(shí)再對(duì)剩下來(lái)的數(shù)進(jìn)行堆調(diào)整，因?yàn)閮蓚€(gè)子節(jié)點(diǎn)已經(jīng)是最大堆了，所以這個(gè)時(shí)候是直接以第一個(gè)元素為根調(diào)整，只需要操作 log2 n 次，所以排好一個(gè)數(shù)據(jù)的平均時(shí)間漸進(jìn)等價(jià)于 log2 n，所以堆排序的時(shí)間復(fù)雜度為 O(n log n)。堆排序是原地排序，所以額外空間復(fù)雜度為 O(1)。堆排序和快速排序一樣，是一個(gè)不穩(wěn)定的排序，因?yàn)樵诟奈恢米笞訕?shù)和右子樹(shù)的數(shù)據(jù)，你并不知道哪個(gè)元素在原數(shù)組處于前面的位置。

總結(jié)

我最喜歡堆排序，它最差的時(shí)間復(fù)雜度也是 O(n log n)，而快速排序雖然比它更快點(diǎn)，但最差的時(shí)間復(fù)雜度為 O(n^2)，且堆排序的空間復(fù)雜度只有 O(1)。還有很多很有意思的排序方法，我稍微了解了一下思路，并未都寫(xiě)一遍。建議不管是哪個(gè)方向的程序員，都將這些常見(jiàn)的排序算法寫(xiě)寫(xiě)，體驗(yàn)一下編程之美。

生活不應(yīng)該只有 API 的調(diào)用，還應(yīng)該有邏輯與優(yōu)雅。

PS:算法雖然很有意思，但也一定要?jiǎng)x住，別一不小心被勾搭的轉(zhuǎn)方向了。- -！

最后留個(gè)項(xiàng)目鏈接:JMSort，這是我看完堆排序之后得到的靈感嘗試寫(xiě)的排序算法，大概思路就是兩兩比較之后每四個(gè)進(jìn)行一次比較，最后將得到的最大的數(shù)放置在數(shù)組末尾，剩下的繼續(xù)比較。因?yàn)樯洗伪容^的數(shù)據(jù)是可以復(fù)用的，所以應(yīng)該效率也不低，不過(guò)暫時(shí)只寫(xiě)了個(gè)沒(méi)復(fù)用版本(因?yàn)閺?fù)用版本被我寫(xiě)亂了)，時(shí)間復(fù)雜度 O(n^2)，實(shí)際運(yùn)行效率就比冒泡快一點(diǎn) TAT，等著我以后來(lái)優(yōu)化，目標(biāo)優(yōu)化到 O(n log n) 的時(shí)間復(fù)雜度。

下圖是1W條隨機(jī)數(shù)據(jù)所需的排序時(shí)間。

參考資料

維基百科-排序算法