算法與數(shù)據(jù)結(jié)構(gòu)概要

最近研究 MIT 6.828 操作系統(tǒng)課程，也重溫了一下機(jī)器語(yǔ)言，還 IDA 這樣的逆向屠龍寶刀窍育，還有基于 Rust 的 Deno，研究了其架構(gòu)及閱讀了部分源代碼宴胧。Rust QuickJS V8 Deno TypeScript 等太有吸引力漱抓，估計(jì)相今后當(dāng)長(zhǎng)的時(shí)間都會(huì)在玩這幾個(gè)玩具。

另外恕齐，總結(jié)了一下數(shù)據(jù)結(jié)構(gòu)與算法乞娄，花了相當(dāng)多的時(shí)間在 Binary Tree 特別是 Red-Black Tree 上面。

本文相當(dāng)長(zhǎng)，涉及了以下排序或搜索算法仪或，都是最基本要掌握的确镊，感覺(jué)也寫(xiě)得相當(dāng)簡(jiǎn)明了，基本沒(méi)有公式什么的：

  • ?? Algrithms & Data Structures
  • ?? Insertion sort
  • ?? Selection sort
  • ?? Counting sort
  • ?? Shell sort
  • ?? Quick Sort NORMAL
  • ?? Heap sort
  • ?? Interpolation Search

?? Algrithms & Data Structures 算法與數(shù)據(jù)結(jié)構(gòu)

網(wǎng)絡(luò)有大量算法訓(xùn)練平臺(tái)范删，如 AlgoExpert 是一個(gè) LeetCode 精選的服務(wù)蕾域，因?yàn)?LeetCode 現(xiàn)在的題目實(shí)在是太多了，但解答到旦、提示等內(nèi)容的質(zhì)量又參差不齊束铭。AlgoExpert 解決了這些問(wèn)題：首先，它提供不到 100 道算法題厢绝，覆蓋不同難度和不同知識(shí)點(diǎn)；其次带猴，每道題都有一系列循序漸進(jìn)的提示昔汉，使得你可以從毫無(wú)頭緒開(kāi)始一步一步做到最優(yōu)解；最后拴清，每道題最后都有視頻講解靶病，從最笨的解法開(kāi)始一步一步講解如何優(yōu)化，最后達(dá)成最優(yōu)解口予。

Data structures & algorithms 是計(jì)算機(jī)語(yǔ)言的基石娄周，是軟件靈魂的支撐。研究計(jì)算機(jī)編程本質(zhì)上就是在弄清楚底層的數(shù)據(jù)結(jié)構(gòu)與算法沪停，了解信息的數(shù)字化與其保存在內(nèi)存的結(jié)構(gòu)排列煤辨，與各種算法和數(shù)據(jù)結(jié)構(gòu)的性能。

面向?qū)ο缶幊膛c傳統(tǒng)的函數(shù)式編程最大差別就是木张，從數(shù)據(jù) --> 函數(shù) --> 結(jié)果的這條流程轉(zhuǎn)變?yōu)橹诒妫瑢?duì)象包含函數(shù)方法，不同的對(duì)象實(shí)現(xiàn)不同的功能舷礼，對(duì)象本身包含數(shù)據(jù)鹃彻，也可以處理數(shù)據(jù)的輸入輸出。

與函數(shù)式編程簡(jiǎn)潔的表達(dá)不同妻献，面向?qū)ο缶幊桃氲囊惶壮橄罄碚摵蛯?duì)象封裝方法 Abstraction & Encapsulation蛛株，會(huì)大大增加軟件的復(fù)雜度。所以無(wú)論是 OOP - Object-Oriented Programming 還 FP - Functional Programming 沒(méi)有絕對(duì)的好壞育拨，只有合適的才是最好的谨履。

面向?qū)ο蟮恼Z(yǔ)言設(shè)計(jì)，基于抽象的數(shù)據(jù)類型定義 ADT - Abstract Data Type至朗，將最基本的數(shù)據(jù)類型屉符，始數(shù)值、字符串等等重新做了整體組織，抽象成面向?qū)ο蟮木幊腆w系矗钟。包括不僅限于 stacks, queues, deques, ordered lists, sorted lists, hash and scatter tables, trees, priority queues, sets, and graphs.

在設(shè)計(jì)算法時(shí)唆香，需要考慮知種因素，如內(nèi)存需求量吨艇、時(shí)間效率等復(fù)雜度躬它，Time Factor、Space Factor 這兩個(gè)的指標(biāo)是最關(guān)鍵东涡，有各種漸進(jìn)評(píng)價(jià)方法 Asymptotic Notations冯吓，如 Big O, Little o, Theta, Omega, Little w。

根據(jù)算法的具體特點(diǎn)差異疮跑，可能對(duì)不同的數(shù)據(jù)會(huì)有不同的表現(xiàn)组贺，所以 Worst Case、 Average Case祖娘、 Best Case 三種情況也是比較重要的評(píng)判依據(jù)失尖。

漸近分析法大 O 表示法較常見(jiàn)，根據(jù)輸入的不同渐苏，復(fù)雜度可以如下表示：

  • O(1) 常數(shù)復(fù)雜度 constant掀潮，最好，表示與輸入沒(méi)有關(guān)系琼富，算法保持固定的時(shí)間或空間效率仪吧。
  • O(logn) 對(duì)數(shù)復(fù)雜度 logarithmic，相當(dāng)好鞠眉。
  • O(n) 線性復(fù)雜度 linear薯鼠，和輸入成正相關(guān)，還不錯(cuò)械蹋，輸入數(shù)據(jù)越多需要時(shí)間也越多人断。
  • O(nlogn) 線性對(duì)數(shù)階 n log n，QuickSort 排序?qū)儆谶@個(gè)級(jí)別朝蜘，輸入變量引起的復(fù)雜度是線性復(fù)雜度的倍率增長(zhǎng)恶迈。
  • O(n^2) 平方階 quadratic，有點(diǎn)問(wèn)題了谱醇。
  • O(n^3) 立方階 cubic暇仲，算法特沒(méi)效率。
  • O(2^n) 指數(shù)階 polynomial副渴，冪復(fù)雜度奈附，非常復(fù)雜，輸入數(shù)據(jù)稍有增加煮剧，需要消耗的時(shí)間會(huì)劇增斥滤。
  • O(n!) 階乘級(jí) exponential将鸵，Traveling Salesman Problem 旅行商問(wèn)題在計(jì)算機(jī)科學(xué)領(lǐng)域是無(wú)解的，n 個(gè)城市就有 n! 種規(guī)劃方案佑颇。

作為數(shù)據(jù)結(jié)構(gòu)入門(mén)顶掉，一般都會(huì)從搜索算法、排序算法挑胸、遞歸等基礎(chǔ)問(wèn)題入手痒筒，配合相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，如數(shù)組茬贵、鏈表簿透、Stack、Queue解藻、二叉樹(shù)老充，由簡(jiǎn)單到復(fù)雜：

  • Searching Techniques
    • Linear Search
    • Binary Search
    • Interpolation Search
    • Hash Table
  • Sorting Techniques
    • Comparison Sorting
      • Bubble Sort
      • Selection Sort
      • Insertion Sort
      • Shell Sort
      • Merge Sort
      • Comb Sort
      • Quck Sort
    • Bucket Sort
    • Counting Sort
    • Radix Sort
    • Heap Sort
  • Recursion
    • Recursion Basics
    • Tower of Hanoi
    • Fibonacci Series

數(shù)據(jù)結(jié)構(gòu)和算法是密不可分，前者重于數(shù)據(jù)的組織螟左，而后者著重于具體問(wèn)題的方法邏輯實(shí)現(xiàn)蚂维。根據(jù)問(wèn)題的不同，算法的一般策略有以下這些：

  • Greedy Algorithms 貪婪算法
    • Travelling Salesman Problem
    • Prim's Minimal Spanning Tree Algorithm
    • Kruskal's Minimal Spanning Tree Algorithm
    • Dijkstra's Minimal Spanning Tree Algorithm
    • Graph - Map Coloring
    • Graph - Vertex Cover
    • Knapsack Problem
    • Job Scheduling Problem
  • Divide and Conquer 分而治之
    • Merge Sort
    • Quick Sort
    • Binary Search
    • Strassen's Matrix Multiplication
    • Closest pair (points)
  • Dynamic Programming 動(dòng)態(tài)規(guī)劃
    • Fibonacci number series
    • Knapsack problem
    • Tower of Hanoi
    • All pair shortest path by Floyd-Warshall
    • Shortest path by Dijkstra
    • Project scheduling

動(dòng)態(tài)規(guī)劃（Dynamic Programming路狮，DP）是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的過(guò)程蔚约。20 世紀(jì) 50 年代初奄妨，美國(guó)數(shù)學(xué)家貝爾曼（R.Bellman）等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理苹祟，從而創(chuàng)立了動(dòng)態(tài)規(guī)劃砸抛。動(dòng)態(tài)規(guī)劃的應(yīng)用極其廣泛，包括工程技術(shù)树枫、經(jīng)濟(jì)直焙、工業(yè)生產(chǎn)、軍事以及自動(dòng)化控制等領(lǐng)域砂轻，并在背包問(wèn)題奔誓、生產(chǎn)經(jīng)營(yíng)問(wèn)題、資金管理問(wèn)題搔涝、資源分配問(wèn)題厨喂、最短路徑問(wèn)題和復(fù)雜系統(tǒng)可靠性問(wèn)題等中取得了顯著的效果。

動(dòng)態(tài)規(guī)劃和分治法非常類似庄呈，但是子問(wèn)題間的解決方案聯(lián)系更密切：

  • 這個(gè)問(wèn)題應(yīng)該可以劃分成更小的重疊子問(wèn)題蜕煌。
  • 用較小的子問(wèn)題的最優(yōu)解可以得到最優(yōu)解。
  • 動(dòng)態(tài)算法使用記憶诬留，已有的解可以輔助解決未解決的子問(wèn)題斜纪。

數(shù)組可能是最簡(jiǎn)單的抽象類型了贫母，在連續(xù)的內(nèi)存區(qū)域開(kāi)辟一塊專用區(qū)域就可以用來(lái)保存數(shù)組：

int[] a = new int[5];
int[][] x = new int[3][5];

然后通過(guò)下標(biāo)訪問(wèn)每個(gè)數(shù)組元素，通過(guò)抽象概念將保存數(shù)據(jù)的每個(gè)內(nèi)存地址表達(dá)為一個(gè)元素盒刚。多維數(shù)據(jù)和一維數(shù)組沒(méi)有本質(zhì)區(qū)別腺劣，就是增加一個(gè)維度計(jì)算的變量，同時(shí)二維數(shù)組還可以抽象為矩陣 Matrices伪冰。

比數(shù)組復(fù)雜一點(diǎn)的就是單向鏈表了 Singly-Linked Lists誓酒，每個(gè)元素連接下一個(gè)元素。只需要知道鏈表的起點(diǎn)贮聂，就可以依次訪問(wèn)到尾端元素靠柑。每個(gè)元素只需要 head data tail 三個(gè)基本屬性，data 存放數(shù)據(jù)吓懈，另外兩個(gè)作為指針引用鏈表的前后端元素歼冰。

#include <iostream>
using namespace std;

struct listNode {
    int value;
    listNode * next;

    // 鏈表節(jié)點(diǎn)默認(rèn)構(gòu)造函數(shù)，顯式使用 nullptr 初始化空指針
    listNode(): next(nullptr) { }
    listNode(int theValue): value(theValue), next(nullptr) {
        // listNode(); 
    }

    listNode * attachNode(int value) {
        listNode *n = new listNode(value);
        n->next = this;
        return n;
    }
};

int main() {

    listNode * node = new listNode(0);

    node = node->attachNode(1)->attachNode(2)->attachNode(3)->attachNode(4);

    int indexNode = 0;
    while (node != nullptr) {
        cout << "鏈表節(jié)點(diǎn) " << indexNode << ": " << node->value << " @" << node << endl;
        node = node->next;
        indexNode++;
    }

    return 0;
}

?? Insertion sort

Insertion sort 是和 Bubbble sort 差不多難度的算法耻警，和打撲克牌時(shí)對(duì)手上的卡片進(jìn)行排序的過(guò)程類似：

  • 先以第 1 張作為參考隔嫡，比較 1、2 張牌甘穿，然后將小的放前面腮恩，即交換位置。
  • 再比較第 2温兼、3 張秸滴，將小的交換到前面，如果比前面一張要大就表示已經(jīng)是從小到大排序好了募判。
  • 重復(fù)這個(gè)操作直到所有牌都排序完畢荡含。

這樣的算法對(duì)少量的數(shù)據(jù)是很有效率的，時(shí)間復(fù)雜度為 O(n^2)，隨著數(shù)據(jù)數(shù)量的增加，時(shí)間要求按 2 次方增加升薯，如果能對(duì)前面已排序的數(shù)據(jù)進(jìn)行二分法查找將大量節(jié)省時(shí)間盈匾，對(duì)有序數(shù)據(jù)進(jìn)行 Binary search 折半查找，在大量數(shù)據(jù)處理中效率是明顯的，它能將 isort 算法內(nèi)層的 for 循環(huán)，即查找部分的時(shí)間復(fù)雜度降為 Ο(log n)，而不是 Linear search 的 O(n^2)找前，對(duì)于大量數(shù)據(jù)的排序，isort 的主要消耗就在內(nèi)層循環(huán)判族。

int isort(unsigned char a[], int n){
   unsigned char k;
   for (size_t i = 1; i < n; i++)
   {
       k = a[i];
       for (size_t j = i; j > 0; j--)
       {
           if (k < a[j-1]) {
               a[j] = a[j-1];
               a[j-1] = k;
           }
       }
   }
   return n;
}

unsigned char s[0xff] = "You would supposed to type some words:";
printf("%s\n", s);
scanf("%[^\n]", s);
isort(s, strlen(s));
printf("isort:%s", s);

scanf 可以用來(lái)獲取一行內(nèi)容輸入躺盛，但是不能處理非 ASCII 字符，如 "French suits of trèfles" 將獲取不到后面的 4 個(gè)字符形帮。

?? Selection sort

選擇和插入排序很像槽惫，只是方向反過(guò)來(lái)操作周叮。

? 將第 1 個(gè)數(shù)據(jù)作為 MIN 參考值。
? 搜索后面比它小的數(shù)界斜，如果有更小的仿耽，就更新 MIN，直到找到所有數(shù)據(jù)中最小的數(shù)各薇，并將最小的數(shù)交換到前面项贺。
? 將 MIN 參考值設(shè)置為第 2 個(gè)數(shù)據(jù)，按以上同樣操作峭判，直到所有數(shù)據(jù)排序完成开缎。

console.log(selectionSort(genArray(20)).join(","));
function genArray(len: number){
  let arr = [], scale = len*10;
  while(len-->0) arr.push(Math.ceil(Math.random()*scale));
  console.log(arr.join(","));
  return arr;
}

function selectionSort(a: number[]){
    let length = a.length;
    for (var i = 0; i < length; ++i) {
        let k = 0, min = a[i];
        for (var j = i+1; j < length; ++j) {
            if(min>a[j]) {
                k = j;
                min = a[j];
            }
        }
        if(k){
            let t = a[i];
            a[i] = a[k];
            a[k] = t;
        }
    }
    return a;
}

?? Counting sort

計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為 key 并將相同值的出現(xiàn)的次數(shù)記錄在另外開(kāi)辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序林螃，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)奕删，所以，如果數(shù)據(jù)數(shù)值的跨度在將會(huì)導(dǎo)致消耗大量的內(nèi)存疗认。

輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí)完残，它的運(yùn)行時(shí)間是 Θ(n + k)。計(jì)數(shù)排序不是比較排序横漏，排序的速度快于任何比較排序算法谨设。

計(jì)數(shù)排序不適合按字母順序排序人名，但是缎浇，可以用在基數(shù)排序中扎拣，來(lái)排序數(shù)據(jù)范圍很大的數(shù)組。

算法步驟如下：

  • 統(tǒng)計(jì)數(shù)據(jù)元素出現(xiàn)的次數(shù)华畏，記錄到數(shù)組 C，數(shù)據(jù)的值作為數(shù)組元素索引尊蚁。
  • 按統(tǒng)計(jì)數(shù)量亡笑，將值按順序回填到原數(shù)組，得到的就是排好序的數(shù)據(jù)横朋。

以下代碼為 TypeScript仑乌，使用腳本的好處就是方便，可以直接使用鍵值對(duì)存儲(chǔ)數(shù)據(jù)琴锭，如果使用 C 語(yǔ)言需要使用動(dòng)態(tài)內(nèi)存分配晰甚，需要找最大值，或者預(yù)設(shè)最大值决帖。

console.log(countingSort(genArray(20)).join(","));
function genArray(len: number){
  let arr = [], scale = len*10;
  while(len-->0) arr.push(Math.ceil(Math.random()*scale));
  console.log(arr.join(","));
  return arr;
}

function countingSort(a: number[]){
    let c:{[key:number]:number} = {};
    let key = 0;
    for (var i = 0; i < a.length; ++i) {
        key = a[i];
        c[key] = c[key]? c[key] + 1:1;
    }
    key = 0;
    for(var k in c){
        for (var j = 0; j < c[k]; ++j) {
            a[key++] = +k;
        }
    }
    return a;
}

?? Shell sort

The C Programming Language 教材為了解析 for 循環(huán)厕九，演示了 Shell sort 排序算法：

/* shellsort:  sort v[0]...v[n-1] into increasing order */
void shellsort(int v[], int n)
{
   int gap, i, j, temp;

   for (gap = n/2; gap > 0; gap /= 2)
       for (i = gap; i < n; i++)
           for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
               temp = v[j];
               v[j] = v[j+gap];
               v[j+gap] = temp;
           }
}

這是一個(gè)三層 for 嵌套的函數(shù)結(jié)構(gòu)，外層定義 gap 負(fù)責(zé)控制兩個(gè)子集比較的粒度地回，從 n/2 到 1 的粒度逐次縮小扁远。中間層負(fù)責(zé)遍歷所有數(shù)據(jù)俊鱼，而最內(nèi)層負(fù)責(zé)比較并更新順序。

在多個(gè)嵌套循環(huán)保持循環(huán)控制集中的優(yōu)勢(shì)明顯畅买，Shell sort 這種排序算法的基本思想是 D. L. Shell 設(shè)計(jì)的并闲，名字念希爾。在比較初期階段谷羞，用粗粒度間距對(duì)元素進(jìn)行粗排帝火，而不是簡(jiǎn)單的交換相鄰的元素。這種粗排往往會(huì)很快消除大量的紊亂湃缎，使后期的工作更少犀填。隨著比較元素之間的間隔逐漸減小為 1，此時(shí)排序有效地成為相鄰交換方法雁歌，所有元素最終都會(huì)正確排序宏浩。

注意 for 的通用性使外循環(huán)與其他循環(huán)以相同的形式擬合，即使它不是算術(shù)級(jí)數(shù)靠瞎，即可以指定 step 值比庄。因?yàn)槊枯喌拈g隔在遞減，但粗排序好的數(shù)據(jù)在增加乏盐，所以也叫遞減增量排序佳窑，增量意思指數(shù)據(jù)的有序性在增加。正是這種逐次減半的粒度控制父能，使用得所有數(shù)據(jù)都得到正常的排序神凑，而不被遺漏。類似的概念的排序還 Comb sort何吝，梳排序溉委，同時(shí)它結(jié)合 Bubble sort 的比較邏輯。

列如爱榕，對(duì)一個(gè)單詞的字母進(jìn)行排序：

supposed <- gap = 4
^   ^
ouppssed
 ^   ^
osppsued
  ^   ^
osepsupd
   ^   ^
osedsupp <- gap = 2
^ ^
esodsupp
 ^ ^
edossupp
    ^ ^
edospusp
     ^ ^
edosppsu
   ^ ^
edoppssu <- gap = 1
^^
deoppssu

?? Quick Sort NORMAL

快速排序核心思維是二分法加遞歸處理瓣喊，而巧妙之處在于二分策略，即分治法（Divide and conquer）策略黔酥，按一個(gè)參考值將數(shù)據(jù)分為大小 2 個(gè)子集藻三，然后遞歸地排序兩個(gè)子序列。

它使用了 3 個(gè)元素跪者，基本排序流程如下：

  • pivot 中樞元素棵帽，指向一個(gè)參考值，將數(shù)據(jù)分成兩個(gè)區(qū)渣玲；
  • low 左邊界逗概，從左向右與 pivot 進(jìn)行比較，將更大的值交換到右區(qū)忘衍，并進(jìn)入下一步驟仗谆；
  • high 右邊界指巡，從右向左與 pivot 進(jìn)行比較，將更小的值交換到左區(qū)隶垮，完全分區(qū)后藻雪，將 pivot 放到新的中樞位，進(jìn)入新一輪遞歸處理狸吞；

就是這三個(gè)元素完成了 Quick Sort 的最巧妙的二分策略勉耀，在快速分組的同時(shí)，又進(jìn)行了初步的排序蹋偏。

Complexity

Name Best Average Worst Memory Stable
Quick sort n log(n) n log(n) n^2 log(n) No

而對(duì)于漸進(jìn)有序的數(shù)組來(lái)說(shuō)便斥，每次區(qū)分其實(shí)都是極其不平衡的，普通快排甚至?xí)嘶?O(n^2)威始，可能需要多路快排枢纠。

選擇合適的 pivot 值對(duì)效率有很大影響，比如 [ 7, 6, 5, 4, 3, 2, 1 ] 選擇了 1 作為 pivot 就很沒(méi)效率黎棠。

console.log(sortArray(genArray(200)).join(","));
function genArray(len: number){
  let arr = [], scale = len*100;
  while(len-->0) arr.push(Math.ceil(Math.random()*scale));
  console.log(arr.join(","));
  return arr;
}

function sortArray(nums: number[]): number[] {
    quickSort(nums, 0, nums.length-1);
    return nums;
};

function quickSort(nums: number[], low:number, high: number){
    let s = low, e = high;
    if(low >= high) return;
    let p = nums[high];
    while(low<high){
        while(low<high && nums[low]<p) low++;
        nums[high] = nums[low];
        while(low<high && nums[high]>=p) high--;
        nums[low] = nums[high];
    }
    nums[high] = p;
    quickSort(nums, s, low-1);
    quickSort(nums, low+1, e);
}

?? Heap sort

堆排序是利用 Binary Heap 二叉堆晋渺，也叫 Heap Tree 堆積樹(shù)，這種樹(shù)狀數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法脓斩，是一種選擇排序木西，它的最壞，最好随静，平均時(shí)間復(fù)雜度均為 O(nlogn)八千，它也是不穩(wěn)定排序。

在計(jì)算機(jī)科學(xué)中燎猛，二叉堆是二叉樹(shù)形狀的堆結(jié)構(gòu)恋捆，所以稱為堆積樹(shù)，是最常見(jiàn)的實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方法重绷，在很多主流語(yǔ)言的標(biāo)準(zhǔn)算法庫(kù)中都能看到它們的身影沸停。同時(shí)它也是很多算法中需要用到的底層數(shù)據(jù)結(jié)構(gòu)，能夠快速地掌握這些已有的標(biāo)準(zhǔn)庫(kù)和類论寨，能夠很高效地實(shí)現(xiàn)諸多算法星立。

binary treee

學(xué)習(xí) Heap sort 之前爽茴，需要對(duì)二叉樹(shù)的主要概念有一定理解：

  • Path ? Path refers to the sequence of nodes along the edges of a tree.
  • Root ? The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.
  • Parent ? Any node except the root node has one edge upward to a node called parent.
  • Child ? The node below a given node connected by its edge downward is called its child node.
  • Leaf ? The node which does not have any child node is called the leaf node.
  • Subtree ? Subtree represents the descendants of a node.
  • Visiting ? Visiting refers to checking the value of a node when control is on the node.
  • Traversing ? Traversing means passing through nodes in a specific order.
  • Levels ? Level of a node represents the generation of a node.
  • keys ? Key represents a value of a node based on which a search operation is to be carried out for a node.

堆積樹(shù)是一種完全二叉樹(shù)葬凳，有兩種形式，min-heap 小根堆要求節(jié)點(diǎn)小于或等于子節(jié)點(diǎn)值室奏，max-heap 大根堆要求節(jié)點(diǎn)大于或等于子節(jié)點(diǎn)值火焰。

      max-heap          min-heap
         9                 3        <-- Leevl 0
     ┌───┴───┐         ┌───┴───┐     
     8       7         4       5    <-- Leevl 1
   ┌─┴─┐   ┌─┴─┐     ┌─┴─┐   ┌─┴─┐   
   6   5   4   3     6   7   8   9  <-- Leevl 2
 ┌─┴─┐             ┌─┴                
 6   5             7                <-- Leevl 3

所謂完全二叉樹(shù)，即除最底層 L 的葉節(jié)點(diǎn)外胧沫，L-2 層以上的所有節(jié)點(diǎn)都有 2 個(gè)子節(jié)點(diǎn)昌简，如果 L-1 層以上所有節(jié)點(diǎn)都有 2 個(gè)子節(jié)點(diǎn)則稱為完滿二叉樹(shù)占业。

完全二叉樹(shù)是一種效率很高的數(shù)據(jù)結(jié)構(gòu)，通常采用數(shù)組形式存儲(chǔ)纯赎，可以快速計(jì)算出一個(gè)節(jié)點(diǎn)的父子節(jié)點(diǎn)谦疾，同時(shí)不需要額外存儲(chǔ)索引信息。

根據(jù)葉節(jié)點(diǎn)的分布不同犬金，二叉樹(shù)可以按以下分類：

  • 完美二叉樹(shù) Perfect Binary Tree 所有葉節(jié)點(diǎn)深度相同念恍，所有非葉節(jié)點(diǎn)都有兩點(diǎn)子節(jié)點(diǎn)。也稱為滿二叉樹(shù)晚顷，深度為 k(>=-1) 且有 2^(k+1) - 1 個(gè)節(jié)點(diǎn)峰伙。
  • 完全二叉樹(shù) Complete Binary Tree，除了最底層该默，所有節(jié)點(diǎn)都是完全充滿子節(jié)點(diǎn)瞳氓，而葉子節(jié)點(diǎn)從左到友依次排列，不需要填滿二叉樹(shù)栓袖。
  • 完滿二叉樹(shù) Full Binary Tree/Strictly Binary Tree匣摘，除葉節(jié)點(diǎn)外，所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)叽赊。換句話說(shuō)恋沃，只要有子節(jié)點(diǎn)，就必有兩個(gè)子節(jié)點(diǎn)必指。
  • 平衡二叉樹(shù) Balance Binary Tree 要求左右子樹(shù)的高度差至多為 1 個(gè)節(jié)點(diǎn)囊咏。
  • 自平衡二叉樹(shù) Self-Balancing Binary Search Tree 簡(jiǎn)稱 AVL 平衡二叉樹(shù)，名字來(lái)源于它的發(fā)明作者 G.M. Adelson-Velsky 和 E.M. Landis塔橡。

二叉堆的空間復(fù)雜度和相關(guān)操作的時(shí)間復(fù)雜度如下表所示：

| Algorithm | Average  | Worst Case |
|-----------|----------|------------|
| Space     | O(n)     | O(n)       |
| Search    | O(n)     | O(n)       |
| Insert    | O(1)     | O(log n)   |
| Delete    | O(log n) | O(log n)   |
| Peek      | O(1)     | O(1)       |

堆排序基本思想：將序列數(shù)據(jù)構(gòu)造成大頂堆梅割，整個(gè)序列的最大值就是根節(jié)點(diǎn)，將其交換到末尾葛家，作為已排序數(shù)據(jù)户辞。然后將剩余 n-1 個(gè)元素重新構(gòu)造成一個(gè)堆，這樣會(huì)得到 n 個(gè)元素的次大值癞谒。重復(fù)操作底燎，直到得到一個(gè)有序序列。

所以弹砚，堆排序的要點(diǎn)在于構(gòu)造二叉堆双仍，還有摘頂后二叉堆的重建，這個(gè)過(guò)程稱為 heapify桌吃。事實(shí)上朱沃，在排序過(guò)程中并不需要定義一個(gè) BinaryHeap 對(duì)象，在一個(gè)堆中，k = 0 即頂級(jí)節(jié)點(diǎn)逗物，位置 k 的子節(jié)點(diǎn)的父元素的位置是 (k+1)/2-1搬卒，而它的兩個(gè)子節(jié)點(diǎn)的位置分別是 2k+1 和 2k+2，這樣節(jié)點(diǎn)就和數(shù)組的索引關(guān)聯(lián)起來(lái)了翎卓。對(duì)于一個(gè) N 元素的堆積樹(shù)契邀，其節(jié)點(diǎn)也同樣有 N 個(gè)，包括葉節(jié)點(diǎn)失暴。

假設(shè)數(shù)據(jù)為 8 個(gè)元素的數(shù)組 [4,2,5,7,1,9,8,0]蹂安，升序采用大頂堆，降序采用小頂堆锐帜。

首先田盈，將數(shù)組的數(shù)據(jù)按先后順序填充到二叉堆，從頂層 Level 0 到底層缴阎，從左節(jié)點(diǎn)到右節(jié)點(diǎn)依次填充允瞧，并依次給節(jié)點(diǎn)編號(hào)。

      max-heap     
         4         <-- Leevl 0
     ┌───┴───┐      
     2       5     <-- Leevl 1
   ┌─┴─┐   ┌─┴─┐    
   7   1   9   8   <-- Leevl 2
 ┌─┴               
 0                 <-- Leevl 3

從最后底層的非葉子結(jié)點(diǎn)開(kāi)始調(diào)整蛮拔，按按照數(shù)組的線性結(jié)構(gòu)述暂，最后的 7 號(hào)數(shù)組元素對(duì)應(yīng) 3 號(hào)節(jié)點(diǎn)，7 = 2 * 3 + 1建炫，節(jié)點(diǎn)對(duì)應(yīng)位置畦韭。

從左至右，從下至上進(jìn)行調(diào)整肛跌，因?yàn)楣?jié)點(diǎn)值 7 比唯一的子節(jié)點(diǎn)值 0 大艺配，所以不用調(diào)整，通過(guò) 2k+2 超出數(shù)組范圍可以判斷出沒(méi)有第二個(gè)子節(jié)點(diǎn)衍慎。

接下來(lái)转唉，對(duì) 3 號(hào)節(jié)點(diǎn)的父節(jié)點(diǎn)調(diào)整，依次比較兩個(gè)子節(jié)點(diǎn)并按需要交換位置稳捆。即對(duì) 1 號(hào)節(jié)點(diǎn)調(diào)整赠法，從子節(jié)點(diǎn)也可以反推父節(jié)點(diǎn) 3 = ( 2 * x) + 1，就是解個(gè)方程式乔夯。

這個(gè)過(guò)程就是一個(gè)沉降或抬升的操作砖织，可以定義一個(gè) heapify 函數(shù)將數(shù)據(jù)交換到合適位置，當(dāng)移除根節(jié)點(diǎn)時(shí)末荐，可以直接將數(shù)組最后元素提升為根節(jié)點(diǎn)侧纯，然后，再通過(guò)沉降函數(shù)交換到合適的位置上鞠评。

堆排序算法可以概括如下幾個(gè)步驟：

  • 使用 heapify 函數(shù)將數(shù)組 H[0……n-1] 轉(zhuǎn)換為一個(gè)二叉堆茂蚓；
  • 把堆首（最大值）和堆尾互換壕鹉；
  • 把堆的尺寸縮小 1剃幌，即將堆尾的元素排除聋涨，并調(diào)用 heapify 將新的根節(jié)點(diǎn)調(diào)整到合適位置；
  • 重復(fù)操作负乡，直到堆的尺寸為 1 即完成排序牍白。

注意，設(shè)計(jì) heapify 函數(shù)時(shí)抖棘，需要先從節(jié)點(diǎn)樹(shù)最底部抬升或沉降茂腥，相當(dāng)于一個(gè)粗排，然后在后續(xù)對(duì)上層節(jié)點(diǎn)進(jìn)行的 heapify 操作中切省，再細(xì)化一次以確保數(shù)據(jù)滿足二叉堆的要求最岗，這個(gè)過(guò)程相當(dāng)巧妙。

如果使用 max-heap朝捆，那么就從數(shù)組的末尾即二叉樹(shù)最底層節(jié)點(diǎn)開(kāi)始抬升大值數(shù)據(jù)般渡。如果使用 min-heap，則從底層開(kāi)始沉降小值數(shù)據(jù)芙盘。

可以參考舊金山大學(xué) University of San Francisco 官方網(wǎng)站驯用，David Galles 助教制作的數(shù)據(jù)結(jié)構(gòu)與算法動(dòng)畫(huà)演示工具。

let result = heapSort(genArray(8));
console.log(result.join(","));
verify(result);

function genArray(len: number){
  let arr = [], scale = len*10;
  while(len-->0) arr.push(Math.ceil(Math.random()*scale));
  console.log(arr.join(","));
  return arr;
}

function verify(a: number[]){
    for(let i=0; i<a.length; i++){
        if (a[i]>a[i+1]) {
            return console.log(a.slice(0, i).join(",").replace(/./g, " ") + "^ VERIFY FAILURE AT "+i);
        }
    }
    return console.log("VERIFY PASSED!");
}

function heapSort(a: number[]){
    // build an max-heap
    let length = a.length;
    for (var i = length/2; i >= 0; --i) {
        heapfy(a, Math.floor(i), length);
    }
    console.log("HEAPFIED!");
    // sort all nodes
    for(let i=length-1; i>=0; i--){
        swap(a, 0, i);
        heapfy(a, 0, i);
    }
    return a;
}

function heapfy(a:number[], k:number, N:number) {
    while (2*k+1 < N) {
        let g = Math.floor(2*k + 1);
        if (g < N-1 && a[g+1] >= a[g]){
            g ++;
        }
        if (a[k] < a[g]){
            swap(a, k, g);
        }
        k = g;
    }
}

function swap(a:number[], x:number, y:number){
    let tag = a.slice(0, x+1).join(",").replace(/./g, " ")+"^"+
        a.slice(x, y).join(",").replace(/./g, " ")+"^";
    let pad = a.join(",").slice(0, a.join(",").length-tag.length+2).replace(/./g, " ");
    console.log(a.join(","));
    console.log(tag+pad+a[x]+" <==> "+a[y]);
    let t = a[x];
    a[x] = a[y];
    a[y] = t;
}

測(cè)試輸出：

11,55,59,37,65,3,23,21                     34,9,9,24,80,15,42,25             
     ^        ^         55 <==> 65                  ^           ^ 24 <==> 25 
11,65,59,37,55,3,23,21                     34,9,9,25,80,15,42,24             
  ^  ^                  11 <==> 65               ^          ^     9 <==> 42  
65,11,59,37,55,3,23,21                     34,9,42,25,80,15,9,24             
     ^        ^         11 <==> 55             ^       ^          9 <==> 80  
HEAPFIED!                                  34,80,42,25,9,15,9,24             
65,55,59,37,11,3,23,21                       ^  ^                 34 <==> 80 
  ^                   ^ 65 <==> 21         HEAPFIED!                         
21,55,59,37,11,3,23,65                     80,34,42,25,9,15,9,24             
  ^     ^               21 <==> 59           ^                  ^ 80 <==> 24 
59,55,21,37,11,3,23,65                     24,34,42,25,9,15,9,80             
        ^          ^    21 <==> 23           ^     ^              24 <==> 42 
59,55,23,37,11,3,21,65                     42,34,24,25,9,15,9,80             
  ^                ^    59 <==> 21           ^                ^   42 <==> 9  
21,55,23,37,11,3,59,65                     9,34,24,25,9,15,42,80             
  ^  ^                  21 <==> 55          ^ ^                   9 <==> 34  
55,21,23,37,11,3,59,65                     34,9,24,25,9,15,42,80             
     ^     ^            21 <==> 37             ^    ^             9 <==> 25  
55,37,23,21,11,3,59,65                     34,25,24,9,9,15,42,80             
  ^              ^      55 <==> 3            ^            ^       34 <==> 15 
3,37,23,21,11,55,59,65                     15,25,24,9,9,34,42,80             
 ^ ^                    3 <==> 37            ^  ^                 15 <==> 25 
37,3,23,21,11,55,59,65                     25,15,24,9,9,34,42,80             
    ^    ^              3 <==> 21            ^          ^         25 <==> 9  
37,21,23,3,11,55,59,65                     9,15,24,9,25,34,42,80             
  ^          ^          37 <==> 11          ^    ^                9 <==> 24  
11,21,23,3,37,55,59,65                     24,15,9,9,25,34,42,80             
  ^     ^               11 <==> 23           ^       ^            24 <==> 9  
23,21,11,3,37,55,59,65                     9,15,9,24,25,34,42,80             
  ^        ^            23 <==> 3           ^ ^                   9 <==> 15  
3,21,11,23,37,55,59,65                     15,9,9,24,25,34,42,80             
 ^ ^                    3 <==> 21            ^    ^               15 <==> 9  
21,3,11,23,37,55,59,65                     9,9,15,24,25,34,42,80             
  ^    ^                21 <==> 11          ^ ^                   9 <==> 9   
11,3,21,23,37,55,59,65                     9,9,15,24,25,34,42,80             
  ^  ^                  11 <==> 3           ^^                    9 <==> 9   
3,11,21,23,37,55,59,65                     9,9,15,24,25,34,42,80             
 ^^                     3 <==> 3           VERIFY PASSED!                    
3,11,21,23,37,55,59,65                    
VERIFY PASSED!

?? Interpolation Search

在有序數(shù)據(jù)搜索算法中儒老，Linear search 是直觀但也是最沒(méi)有效率的蝴乔，它從第一個(gè)數(shù)據(jù)查找一到到數(shù)據(jù)結(jié)束，如果剛好目標(biāo)是最后一個(gè)驮樊，那么就是它的最差表現(xiàn)薇正，算法復(fù)雜度為 O(n)。

如果在大量數(shù)據(jù)的查找囚衔，使用二分法查找 Binary Search铝穷，則可以大大節(jié)省時(shí)間。

mid = Lo + (Hi - Lo) / 2

首先佳魔，將數(shù)據(jù)對(duì)半分成兩部分曙聂，目標(biāo)的值落在哪個(gè)范圍就找哪個(gè)部分的數(shù)據(jù)，重復(fù)進(jìn)行數(shù)據(jù)的拆分鞠鲜，直到找到目標(biāo)宁脊，復(fù)雜度為 Ο(log n)，表現(xiàn)相當(dāng)好了贤姆。

二分法的搜索過(guò)程相當(dāng)于建立了一個(gè)二叉樹(shù)榆苞，所以叫做 BST - Binary Search Tree。

但是對(duì)有序數(shù)據(jù)的利用還不夠充分霞捡，而插值查找 Interpolation Search 則利用插值算法來(lái)分拆數(shù)據(jù)坐漏，使得分拆點(diǎn)更合理。

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where ?
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

插值算法通過(guò)計(jì)算差值空間，挑選出更靠近目標(biāo)值 X 的拆分點(diǎn)赊琳，這樣也就間接地減少了比較次數(shù)街夭。

同樣思想衍生出來(lái)的還有利用 Fibonacci Series 來(lái)定拆分點(diǎn)，裴波那契數(shù)列最重要的一個(gè)性質(zhì)是每個(gè)數(shù)都等于前兩個(gè)數(shù)之和躏筏，滿足 F(0)=1板丽，F(xiàn)(1)=1, F(n)=F(n-1)+F(n-2) (n>=2，n∈N)趁尼，兩個(gè)相鄰項(xiàng)的比值會(huì)逐漸逼近 0.618 黃金分割比值埃碱，這個(gè)神奇的數(shù)列在自然界廣泛存在。

對(duì)于表長(zhǎng)較大酥泞，而關(guān)鍵字分布又比較均勻的查找表來(lái)說(shuō)砚殿，插值查找算法的平均性能比折半查找要好的多。但是芝囤，數(shù)組中如果分布非常不均勻瓮具，那么插值查找未必是很合適的選擇。

算法時(shí)間復(fù)雜度 Ο(log (log n)) 優(yōu)于二分法搜索 Ο(log n)凡人。

另外名党，計(jì)算分布需要用浮點(diǎn)數(shù)，如果數(shù)據(jù)中有重復(fù)值挠轴，那么公式將可能出現(xiàn)除 0 異常传睹，正好通過(guò)一個(gè)小數(shù)偏差可以解決類型轉(zhuǎn)換和除 0 問(wèn)題。

#include <stdio.h>
#include <string.h>

// Interpolation Search
int isearch(char a[], int n, char x){
    int lo = 0, mi, hi = n-1;
    printf("%s\n", a);
    while (lo<hi) {
        mi = lo + (hi-lo)/(a[hi] - a[lo] + .1)*(x - a[lo]);
        printf("%*c%*c%*c<---try to find %c\n", 
            lo+1, '[', mi-lo, '^', hi-mi, ']', x);
        if (a[mi]==x){
            return mi;
        } else if (a[mi]<x) {
            lo = mi + 1;
        } else {
            hi = mi - 1;
        }
    }
    return a[lo] == x? lo : -1;
}

// Insertion sort
int isort(char a[], int n){
    char k;
    for (size_t i = 1; i < n; i++)
    {
        k = a[i];
        for (size_t j = i; j > 0; j--)
        {
            if (k < a[j-1]) {
                a[j] = a[j-1];
                a[j-1] = k;
            }
        }
    }
    return n;
}

int main()
{
    char s[0xff] = "You would supposed to type some words then a character:";
    char key;
    printf("%s\n", s);
    scanf(" %[^\n] %c", s, &key);
    isort(s, strlen(s));
    int k = isearch(s, strlen(s), key);
    printf("%s\n", s);
    printf("%*c[key at %d]", k+1, key, k);
    return 0;
}

測(cè)試輸出：

You would supposed to type some words then a character:
a
         :Yaaaccdddeeeeehhlmnooooooppprrrssssttttuuuwwy
[                                      ^              ]<---try to find a
[                             ^       ]<---try to find a
[                      ^     ]<---try to find a
[                   ^ ]<---try to find a
[                ^ ]<---try to find a
[              ^]<---try to find a
[            ^]<---try to find a
         :Yaaaccdddeeeeehhlmnooooooppprrrssssttttuuuwwy
             a[key at 13]
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末岸晦，一起剝皮案震驚了整個(gè)濱河市欧啤，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌启上，老刑警劉巖邢隧，帶你破解...
    沈念sama閱讀 206,378評(píng)論 6贊 481
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異冈在，居然都是意外死亡倒慧，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,356評(píng)論 2贊 382
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門(mén)包券，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)纫谅，“玉大人，你說(shuō)我怎么就攤上這事溅固「讹酰” “怎么了？”我有些...
    開(kāi)封第一講書(shū)人閱讀 152,702評(píng)論 0贊 342
  • 道士緝兇錄：失蹤的賣(mài)姜人
    文/不壞的土叔 我叫張陵侍郭，是天一觀的道長(zhǎng)询吴。 經(jīng)常有香客問(wèn)我掠河，道長(zhǎng)，這世上最難降的妖魔是什么猛计？ 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 55,259評(píng)論 1贊 279
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任唠摹，我火速辦了婚禮，結(jié)果婚禮上有滑，老公的妹妹穿的比我還像新娘。我一直安慰自己嵌削，他們只是感情好毛好，可當(dāng)我...
    茶點(diǎn)故事閱讀 64,263評(píng)論 5贊 371
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著苛秕，像睡著了一般肌访。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上艇劫，一...
    開(kāi)封第一講書(shū)人閱讀 49,036評(píng)論 1贊 285
  • 城市分裂傳說(shuō)
    那天吼驶，我揣著相機(jī)與錄音，去河邊找鬼店煞。 笑死蟹演，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的顷蟀。 我是一名探鬼主播酒请，決...
    沈念sama閱讀 38,349評(píng)論 3贊 400
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼鸣个！你這毒婦竟也來(lái)了羞反？” 一聲冷哼從身側(cè)響起，我...
    開(kāi)封第一講書(shū)人閱讀 36,979評(píng)論 0贊 259
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤囤萤，失蹤者是張志新（化名）和其女友劉穎昼窗，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體涛舍，經(jīng)...
    沈念sama閱讀 43,469評(píng)論 1贊 300
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡澄惊，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,938評(píng)論 2贊 323
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了富雅。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片缤削。...
    茶點(diǎn)故事閱讀 38,059評(píng)論 1贊 333
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖吹榴，靈堂內(nèi)的尸體忽然破棺而出亭敢，到底是詐尸還是另有隱情，我是刑警寧澤图筹，帶...
    沈念sama閱讀 33,703評(píng)論 4贊 323
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布帅刀，位于F島的核電站让腹，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏扣溺。R本人自食惡果不足惜骇窍，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,257評(píng)論 3贊 307
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望锥余。 院中可真熱鬧腹纳，春花似錦、人聲如沸驱犹。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,262評(píng)論 0贊 19
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)雄驹。三九已至佃牛，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間医舆，已是汗流浹背俘侠。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,485評(píng)論 1贊 262
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留蔬将，地道東北人爷速。 一個(gè)月前我還...
    沈念sama閱讀 45,501評(píng)論 2贊 354
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長(zhǎng)得像霞怀，于是被迫代替她去往敵國(guó)和親遍希。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,792評(píng)論 2贊 345

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