關(guān)于我的倉(cāng)庫(kù)

• 這篇文章是我為面試準(zhǔn)備的學(xué)習(xí)總結(jié)中的一篇
• 我將準(zhǔn)備面試中找到的所有學(xué)習(xí)資料，寫(xiě)的Demo，寫(xiě)的博客都放在了這個(gè)倉(cāng)庫(kù)里iOS-Engineer-Interview
• 歡迎star????
• 其中的博客在簡(jiǎn)書(shū)尼变，CSDN都有發(fā)布
• 博客中提到的相關(guān)的代碼Demo可以在倉(cāng)庫(kù)里相應(yīng)的文件夾里找到

前言

• 該系列為學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)與算法之美》的系列學(xué)習(xí)筆記
• 總結(jié)規(guī)律為一周一更贪庙，內(nèi)容包括其中的重要知識(shí)帶你计呈，以及課后題的解答
• 算法的學(xué)習(xí)學(xué)與刷題并進(jìn)，希望能真正養(yǎng)成解算法題的思維
• LeetCode刷題倉(cāng)庫(kù)：LeetCode-All-In
• 多說(shuō)無(wú)益掂器，你應(yīng)該開(kāi)始打代碼了

11講排序（上）：為什么插入排序比冒泡排序更受歡迎

• 開(kāi)始進(jìn)入排序章節(jié)了，專注于會(huì)俱箱，懂国瓮，好吧
• 敲之前我回我回，敲不出來(lái)我的我的
• GOGOGO

fb8394a588b12ff6695cfd664afb17cd

如何比較排序算法

• 執(zhí)行效率

  • 最好狞谱，最壞乃摹，平均時(shí)間復(fù)雜度
  • 這樣可以看出對(duì)于有序度比較高/低的測(cè)試數(shù)據(jù)效果如何

• 內(nèi)存損耗

  • 以空間復(fù)雜度衡量
  • 這里顯然原地排序算法比較屌，就是空間復(fù)雜度為O(1)的算法

• 穩(wěn)定性

  • 如果待排序的序列中存在值相等的元素跟衅，經(jīng)過(guò)排序之后孵睬，相等元素之間原有的先后順序不變
  • 不變就是穩(wěn)定排序算法，變就是穩(wěn)定排序算法
  • 這里對(duì)于數(shù)字看起來(lái)沒(méi)有什么意義伶跷，但是如果我們比較的是一個(gè)對(duì)象掰读，就可以在比較A的基礎(chǔ)上秘狞，保證B的順序不變
  • 比如我們希望實(shí)現(xiàn)按金額排序訂單，對(duì)于金額相同的訂單又希望下單時(shí)間從早到晚有序
  • 我們的做法其實(shí)就是先對(duì)下單時(shí)間排序蹈集，再對(duì)金額穩(wěn)定排序：
  img

冒泡排序（Bubble Sort）

• 冒泡就是對(duì)于相鄰元素做比較烁试，如果順序不對(duì)就進(jìn)行交換

原理

• 一次冒泡的詳細(xì)過(guò)程：

img

• 完成排序就只要進(jìn)行六次這樣的操作：

img

• 進(jìn)行優(yōu)化就是，假如有一次沒(méi)有任何交換拢肆，說(shuō)明已經(jīng)有序减响，可以終止排序了

a9783a3b13c11a5e064c5306c261e8e6

代碼

void bubbleSort(vector<int> &arr) {
    
    int arrLen = arr.size();
    if (arrLen == 0) {
        return ;
    }   
    for (int i = 0; i < arrLen; i++) {
        bool flag = false;
        for (int j = 0; j < arrLen - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
    return ;
}

特點(diǎn)分析

• 原地排序算法
• 由于我們?cè)O(shè)定了當(dāng)相鄰兩個(gè)元素大小相等的時(shí)候，不做交換郭怪，所以冒泡是穩(wěn)定的
• 時(shí)間復(fù)雜度為O(n2)

fe107c06da8b290fb78fcce4f6774c0f

插入排序（Insertion Sort）

• 插入排序就是將待排序區(qū)間的插入到已排序區(qū)間即可

原理

• 將數(shù)據(jù)區(qū)域分成已排序區(qū)間和未排序區(qū)間辩蛋，初始已排序區(qū)間只有一個(gè)元素就是第一個(gè)元素

b60f61ec487358ac037bf2b6974d2de1

代碼

void insertionSort(vector<int> &arr) {
    
    int arrLen = arr.size();
    if (arrLen == 0) {
        return ;
    }
    for (int i = 1; i < arrLen; i++) {
        int value = arr[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            if (arr[j] > value) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        arr[j + 1] = value;
    }   
}

特點(diǎn)分析

• 原地排序算法
• 我們可以選擇將后面出現(xiàn)的元素，插入到前面的出現(xiàn)的元素后面【對(duì)于相同的元素】移盆，所以是穩(wěn)定的
• 時(shí)間復(fù)雜度為O(n2)

選擇排序（Selection Sort）

• 選擇排序本質(zhì)就是從未排序區(qū)間中找到最小的元素悼院，放到已排序區(qū)間的末尾

原理

• 將數(shù)據(jù)區(qū)域分成已排序區(qū)間和未排序區(qū)間，初始已排序區(qū)間只有一個(gè)元素就是第一個(gè)元素

32371475a0b08f0db9861d102474181d

代碼

void selectionSort(vector<int> &arr) {
    int arrLen = arr.size();
    if (arrLen == 0) {
        return ;
    }
    for (int i = 0; i < arrLen; i++) {
        int minNum = arr[i];
        int minIndex = i;
        for (int j = i; j < arrLen; j++) {
            if (minNum > arr[j]) {
                minNum = arr[j];
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

特點(diǎn)分析

• 原地排序算法
• 比如5咒循，8据途，5，2叙甸，9這樣一組數(shù)據(jù)颖医，使用選擇排序算法來(lái)排序的話，第一次找到最小元素2裆蒸，與第一個(gè)5交換位置熔萧，那第一個(gè)5和中間的5順序就變了，所以就不穩(wěn)定了僚祷。正是因此佛致，相對(duì)于冒泡排序和插入排序，選擇排序就稍微遜色了辙谜“秤埽【不穩(wěn)定】
• 時(shí)間復(fù)雜度為O(n2)

希爾排序（Shell Sort）

• 將需要排序的序列劃分為若干個(gè)較小的序列，對(duì)這些序列進(jìn)行直接插入排序装哆，通過(guò)這樣的操作可使需要排序的數(shù)列基本有序罐脊，最后再使用一次直接插入排序

原理

• 在希爾排序中首先要解決的是怎樣劃分序列，對(duì)于子序列的構(gòu)成不是簡(jiǎn)單地分段蜕琴，而是采取將相隔某個(gè)增量的數(shù)據(jù)組成一個(gè)序列萍桌。一般選擇增量的規(guī)則是：取上一個(gè)增量的一半作為此次子序列劃分的增量，一般初始值元素的總數(shù)量

152AFA4194EF2E84767FDCC14520FDCB

代碼

void shellSort(vector<int> &arr) {
    
    int arrLen = arr.size();
    if (arrLen == 0) {
        return ;
    }
    
    int d = arrLen / 2;
    int x, j, k = 1;
    while (d >= 1) {
        for (int i = d; i < arrLen; i++) {
            x = arr[i];
            j = i - d;
            // 直接插入排序凌简，會(huì)向前找所適合的位置
            while (j >= 0 && arr[j] > x) {
                // 交換位置
                arr[j + d] = arr[j];
                j = j - d;
            }
            arr[j + d] = x;
        }
        d = d / 2;
    }
}

特點(diǎn)分析

• 原地排序算法
• 不穩(wěn)定
• 時(shí)間復(fù)雜度為O n的3/2次【比log(n)快】

總結(jié)

348604caaf0a1b1d7fee0512822f0e50

• 在真正地使用中上炎，我們傾向于使用插入排序，因?yàn)椴簧婕敖粨Q号醉，操作次數(shù)少反症，雖然它的時(shí)間復(fù)雜度和冒泡一樣辛块，而選擇排序更是弟中弟

課后題：我們今天講的幾種排序算法，都是基于數(shù)組實(shí)現(xiàn)的铅碍。如果數(shù)據(jù)存儲(chǔ)在鏈表中润绵，這三種排序算法還能工作嗎？如果能胞谈，那相應(yīng)的時(shí)間尘盼、空間復(fù)雜度又是多少呢？

• 對(duì)于老師所提課后題烦绳，覺(jué)得應(yīng)該有個(gè)前提卿捎，是否允許修改鏈表的節(jié)點(diǎn)value值，還是只能改變節(jié)點(diǎn)的位置径密。一般而言午阵，考慮只能改變節(jié)點(diǎn)位置，冒泡排序相比于數(shù)組實(shí)現(xiàn)享扔，比較次數(shù)一致底桂，但交換時(shí)操作更復(fù)雜；插入排序惧眠，比較次數(shù)一致籽懦，不需要再有后移操作，找到位置后可以直接插入氛魁，但排序完畢后可能需要倒置鏈表暮顺；選擇排序比較次數(shù)一致，交換操作同樣比較麻煩秀存。綜上捶码，時(shí)間復(fù)雜度和空間復(fù)雜度并無(wú)明顯變化，若追求極致性能应又，冒泡排序的時(shí)間復(fù)雜度系數(shù)會(huì)變大宙项，插入排序系數(shù)會(huì)減小乏苦，選擇排序無(wú)明顯變化株扛。

12講排序（下）：如何用快排思想在O(n)內(nèi)查找第K大元素

歸并排序（Merge Sort）

• 如果要排序一個(gè)數(shù)組，我們先把數(shù)組從中間分成前后兩部分汇荐，然后對(duì)前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了闲勺。

原理

• 先看一次分解圖

db7f892d3355ef74da9cd64aa926dc2b

• 這個(gè)的關(guān)鍵將在于merge函數(shù)耘纱，也就是將兩個(gè)已經(jīng)有序的子數(shù)組合并到一起應(yīng)該怎么做

• 這里其實(shí)就和我們進(jìn)行鏈表的插入一樣，兩個(gè)子數(shù)組同時(shí)遍歷革娄，比較倾贰，將小的跟在大的后面冕碟，這是這里我們不再是只要進(jìn)行節(jié)點(diǎn)指向就可以解決問(wèn)題了，而是需要使用輔助數(shù)組匆浙，在輔助數(shù)組里進(jìn)行插入安寺，在最后給原數(shù)組進(jìn)行賦值

95897ade4f7ad5d10af057b1d144a22f

代碼

void merge(vector<int> &arr, int l, int mid, int r) {
    int help[r - l + 1];
    int lIndex = l;
    int rIndex = mid + 1;
    int i = 0;
    while (lIndex <= mid && rIndex <= r) {
        help[i++] = arr[lIndex] < arr[rIndex] ? arr[lIndex++] : arr[rIndex++];
    }
    while (lIndex <= mid) {
        help[i++] = arr[lIndex++];
    }
    while (rIndex <= r) {
        help[i++] = arr[rIndex++];
    }
    for (i = 0; i < r - l + 1; i++) {
        arr[l + i] = help[i];
    }
}

static void mergeSort(vector<int> &arr, int l, int r) {
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

void mergeSort(vector<int> &arr) {
    int arrLen = arr.size();
    if (arrLen == 0) {
        return ;
    }
    mergeSort(arr, 0, arrLen - 1);
}

特點(diǎn)分析

• 非原地算法
• 在merge時(shí)，遇到相同的元素首尼，我們可以保證先把前一個(gè)數(shù)組里的數(shù)據(jù)放入挑庶，這樣就保證了不會(huì)錯(cuò)位，所以是穩(wěn)定的
• 時(shí)間：O(nlogn) 空間：O(n)

快速排序（Quick Sort）

原理

• 如果要排序數(shù)組中下標(biāo)從p到r之間的一組數(shù)據(jù)软能，我們選擇p到r之間的任意一個(gè)數(shù)據(jù)作為pivot（分區(qū)點(diǎn)）
• 我們遍歷p到r之間的數(shù)據(jù)迎捺，將小于pivot的放到左邊，將大于pivot的放到右邊查排，將pivot放到中間凳枝。經(jīng)過(guò)這一步驟之后，數(shù)組p到r之間的數(shù)據(jù)就被分成了三個(gè)部分跋核，前面p到q-1之間都是小于pivot的范舀，中間是pivot，后面的q+1到r之間是大于pivot的

4d892c3a2e08a17f16097d07ea088a81

• 這里有個(gè)partition分區(qū)函數(shù)了罪，就和上面的merge一樣需要一波理解锭环，我們需要把所有比游標(biāo)小的數(shù)字放在左邊，把比游標(biāo)大的數(shù)字放在右邊泊藕，返回游標(biāo)的下標(biāo)
• 具體操作如圖：

086002d67995e4769473b3f50dd96de7

代碼

int partition(vector<int> &arr, int p, int r) {
    int pivot = arr[r];
    int i = p;
    for (int j = p; j < r; j++) {
        if (arr[j] < pivot) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[r]);
    return i;
}

static void quickSort(vector<int> &arr, int p, int r) {
    if (p >= r) {
        return;
    }
    
    int q = partition(arr, p, r);
    quickSort(arr, p, q - 1);
    quickSort(arr, q + 1, r);
}

void quickSort(vector<int> &arr) {
    
    int arrLen = arr.size();
        if (arrLen == 0) {
            return ;
        }
    quickSort(arr, 0, arrLen - 1);
}

特點(diǎn)分析

• 原地算法
• 不穩(wěn)定算法
• 時(shí)間：O(nlogn)

快速排序與歸并排序的異同

aa03ae570dace416127c9ccf9db8ac05

• 兩種排序很大一個(gè)區(qū)別就是歸并排序是從下到上的辅辩，快速排序是從上到下的

如何用快排思想在O(n)內(nèi)查找第K大元素

• 這個(gè)問(wèn)題其實(shí)就是在快排的partition就可以找到，每次選擇區(qū)分點(diǎn)后娃圆，把小的放前面玫锋，大的放后面
• 這樣我們可以判斷出我們要找的數(shù)字所在區(qū)間是哪一個(gè)，對(duì)其繼續(xù)劃分

898d94fc32e0a795fd65897293b98791

實(shí)際題目LeetCode 215 數(shù)組中的第K個(gè)最大元素

在未排序的數(shù)組中找到第 k 個(gè)最大的元素讼呢。請(qǐng)注意撩鹿，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素悦屏。

示例 1:

輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
示例 2:

輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
說(shuō)明:

你可以假設(shè) k 總是有效的节沦，且 1 ≤ k ≤ 數(shù)組的長(zhǎng)度。

題解

class Solution {
public:
    int partition(vector<int> &nums, int p, int r) {
        
        if (p == r) {
            return p;
        }
        
        int pivot = nums[r];
        int i = p;
        for (int j = p; j < r; j++) {
            if (nums[j] > pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        swap(nums[i], nums[r]);
        return i;
    }
    int findKthLargest(vector<int>& nums, int k) {
        
        int len = nums.size();
        if (len == 0 || len < k) {
            return 0;
        }
        int res = 0;
        int p = 0;
        int r = len;
        while (1) {
            int index = partition(nums, p, r - 1);
            // res += index;
            if ((index + 1) == k) {
                return nums[index];
            } else if ((index + 1) > k) {
                r = index;
            } else {
                p = index + 1;
            }
        }
        return -99;
    }
};

課后題：現(xiàn)在你有10個(gè)接口訪問(wèn)日志文件础爬，每個(gè)日志文件大小約300MB甫贯，每個(gè)文件里的日志都是按照時(shí)間戳從小到大排序的。你希望將這10個(gè)較小的日志文件看蚜，合并為1個(gè)日志文件叫搁，合并之后的日志仍然按照時(shí)間戳從小到大排列。如果處理上述排序任務(wù)的機(jī)器內(nèi)存只有1GB，你有什么好的解決思路渴逻，能“快速”地將這10個(gè)日志文件合并嗎疾党？

• 每次從各個(gè)文件中取一條數(shù)據(jù)，在內(nèi)存中根據(jù)數(shù)據(jù)時(shí)間戳構(gòu)建一個(gè)最小堆惨奕，然后每次把最小值給寫(xiě)入新文件仿贬，同時(shí)將最小值來(lái)自的那個(gè)文件再出來(lái)一個(gè)數(shù)據(jù)，加入到最小堆中墓贿。這個(gè)空間復(fù)雜度為常數(shù)茧泪，但沒(méi)能很好利用1g內(nèi)存，而且磁盤(pán)單個(gè)讀取比較慢聋袋，所以考慮每次讀取一批數(shù)據(jù)队伟，沒(méi)了再?gòu)拇疟P(pán)中取，時(shí)間復(fù)雜度還是一樣O(n)幽勒。
• 先構(gòu)建十條io流嗜侮，分別指向十個(gè)文件，每條io流讀取對(duì)應(yīng)文件的第一條數(shù)據(jù)啥容，然后比較時(shí)間戳锈颗，選擇出時(shí)間戳最小的那條數(shù)據(jù)，將其寫(xiě)入一個(gè)新的文件咪惠，然后指向該時(shí)間戳的io流讀取下一行數(shù)據(jù)击吱，然后繼續(xù)剛才的操作，比較選出最小的時(shí)間戳數(shù)據(jù)遥昧，寫(xiě)入新文件覆醇，io流讀取下一行數(shù)據(jù)，以此類推炭臭，完成文件的合并永脓， 這種處理方式，日志文件有n個(gè)數(shù)據(jù)就要比較n次鞋仍，每次比較選出一條數(shù)據(jù)來(lái)寫(xiě)入常摧，時(shí)間復(fù)雜度是O（n），空間復(fù)雜度是O（1）,幾乎不占用內(nèi)存威创，這是我想出的認(rèn)為最好的操作了落午，希望老師指出最佳的做法！那婉！

13講線性排序：如何根據(jù)年齡給100萬(wàn)用戶數(shù)據(jù)排序

桶排序（Bucket Sort）

• 桶排序是大一進(jìn)來(lái)學(xué)的第一個(gè)排序了板甘，后面做了這么多題用到的場(chǎng)景其實(shí)也挺多的，對(duì)桶排序有特殊的情感详炬，是咱們的老朋友
• 核心思想是將要排序的數(shù)據(jù)分到幾個(gè)有序的桶里，每個(gè)桶里的數(shù)據(jù)再單獨(dú)進(jìn)行排序。桶內(nèi)排完序之后呛谜，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出在跳，組成的序列就是有序的了。

987564607b864255f81686829503abae

• 如果要排序的數(shù)據(jù)有n個(gè)隐岛，我們把它們均勻地劃分到m個(gè)桶內(nèi)猫妙，每個(gè)桶里就有k=n/m個(gè)元素。每個(gè)桶內(nèi)部使用快速排序聚凹，時(shí)間復(fù)雜度為O(k * logk)割坠。m個(gè)桶排序的時(shí)間復(fù)雜度就是O(m * k * logk)，因?yàn)閗=n/m妒牙，所以整個(gè)桶排序的時(shí)間復(fù)雜度就是O(n*log(n/m))彼哼。當(dāng)桶的個(gè)數(shù)m接近數(shù)據(jù)個(gè)數(shù)n時(shí)，log(n/m)就是一個(gè)非常小的常量湘今，這個(gè)時(shí)候桶排序的時(shí)間復(fù)雜度接近O(n)敢朱。

適用場(chǎng)景

• 桶排序比較適合用在外部排序中。所謂的外部排序就是數(shù)據(jù)存儲(chǔ)在外部磁盤(pán)中摩瞎，數(shù)據(jù)量比較大拴签，內(nèi)存有限，無(wú)法將數(shù)據(jù)全部加載到內(nèi)存中旗们。
• 將所有訂單根據(jù)金額劃分到100個(gè)桶里蚓哩，第一個(gè)桶我們存儲(chǔ)金額在1元到1000元之內(nèi)的訂單，第二桶存儲(chǔ)金額在1001元到2000元之內(nèi)的訂單上渴，以此類推杖剪。每一個(gè)桶對(duì)應(yīng)一個(gè)文件，并且按照金額范圍的大小順序編號(hào)命名（00驰贷，01盛嘿，02…99）。

計(jì)數(shù)排序（Counting Sort）

• 計(jì)數(shù)排序就是之前我理解的桶排序括袒，一個(gè)桶里只存放一個(gè)數(shù)據(jù)的個(gè)數(shù)

adc75672ef33fa54b023a040834fcbc9

• 這里額外講到了怎么根據(jù)桶中的內(nèi)容推算在有序數(shù)組中的位置
• 首先次兆，進(jìn)行順序求和，結(jié)果就是小于等于k的個(gè)數(shù)【OS：這有啥難的呢】

dd6c62b12b0dc1b3a294af0fa1ce371f

• 之后就是遍歷原數(shù)組和這個(gè)C數(shù)組來(lái)復(fù)原這個(gè)排序后的序列【這有啥用咧】
• 我們從后到前依次掃描數(shù)組A锹锰。比如芥炭，當(dāng)掃描到3時(shí)，我們可以從數(shù)組C中取出下標(biāo)為3的值7恃慧，也就是說(shuō)园蝠，到目前為止，包括自己在內(nèi)痢士，分?jǐn)?shù)小于等于3的考生有7個(gè)彪薛，也就是說(shuō)3是數(shù)組R中的第7個(gè)元素（也就是數(shù)組R中下標(biāo)為6的位置）。當(dāng)3放入到數(shù)組R中后，小于等于3的元素就只剩下了6個(gè)了善延，所以相應(yīng)的C[3]要減1少态，變成6。

1d730cb17249f8e92ef5cab53ae65784

基數(shù)排序（Radix Sort）

• 基數(shù)排序就很簡(jiǎn)單易遣，只要是一位一位排序就行
• 就和第一次講排序的時(shí)候提到的穩(wěn)定排序一樣彼妻，從后往前，保證穩(wěn)定排序

df0cdbb73bd19a2d69a52c54d8b9fc0c

• 另外對(duì)于長(zhǎng)度不齊的可以通過(guò)補(bǔ)零來(lái)對(duì)齊
• 基數(shù)排序?qū)σ判虻臄?shù)據(jù)是有要求的豆茫，需要可以分割出獨(dú)立的“位”來(lái)比較侨歉，而且位之間有遞進(jìn)的關(guān)系，如果a數(shù)據(jù)的高位比b數(shù)據(jù)大揩魂，那剩下的低位就不用比較了幽邓。除此之外，每一位的數(shù)據(jù)范圍不能太大肤京，要可以用線性排序算法來(lái)排序颊艳，否則，基數(shù)排序的時(shí)間復(fù)雜度就無(wú)法做到O(n)了

課后題：假設(shè)我們現(xiàn)在需要對(duì)D忘分，a棋枕，F(xiàn)，B妒峦，c重斑，A，z這個(gè)字符串進(jìn)行排序肯骇，要求將其中所有小寫(xiě)字母都排在大寫(xiě)字母的前面窥浪，但小寫(xiě)字母內(nèi)部和大寫(xiě)字母內(nèi)部不要求有序。比如經(jīng)過(guò)排序之后為a笛丙，c漾脂，z，D胚鸯，F(xiàn)骨稿，B，A姜钳，這個(gè)如何來(lái)實(shí)現(xiàn)呢坦冠？如果字符串中存儲(chǔ)的不僅有大小寫(xiě)字母，還有數(shù)字哥桥。要將小寫(xiě)字母的放到前面辙浑，大寫(xiě)字母放在最后，數(shù)字放在中間拟糕，不用排序算法判呕，又該怎么解決呢倦踢？

• 用兩個(gè)指針a、b：a指針從頭開(kāi)始往后遍歷佛玄，遇到大寫(xiě)字母就停下硼一，b從后往前遍歷累澡，遇到小寫(xiě)字母就停下梦抢，交換a、b指針對(duì)應(yīng)的元素愧哟；重復(fù)如上過(guò)程奥吩，直到a、b指針相交蕊梧。
• 利用桶排序思想霞赫，弄小寫(xiě)，大寫(xiě)肥矢，數(shù)字三個(gè)桶端衰，遍歷一遍，都放進(jìn)去甘改，然后再?gòu)耐爸腥〕鰜?lái)就行了旅东。相當(dāng)于遍歷了兩遍，復(fù)雜度O(n)

14講排序優(yōu)化：如何實(shí)現(xiàn)一個(gè)通用的十艾、高性能的排序函數(shù)

前面講的八種排序算法總結(jié)

1f6ef7e0a5365d6e9d68f0ccc71755fd

• 這里要注意的是雖然歸并排序看起來(lái)很爽抵代，但是由于需要重開(kāi)一塊空間進(jìn)行分區(qū)，所以空間復(fù)雜度太高忘嫉，我們不使用
• 歸并排序可以做到平均情況荤牍、最壞情況下的時(shí)間復(fù)雜度都是O(nlogn)

如何優(yōu)化快速排序

• 當(dāng)我們需要排序的序列本身就已經(jīng)是接近有序的時(shí)候，我們的快速排序效率是最低的庆冕，因?yàn)槊看芜x擇的分區(qū)點(diǎn)都是最后一個(gè)數(shù)據(jù)康吵，這樣時(shí)間復(fù)雜度就會(huì)退化到O(n2)
• 理想的分區(qū)點(diǎn)應(yīng)該是在左右兩個(gè)分區(qū)中，數(shù)據(jù)的數(shù)量都差不多
• 這里介紹兩種分區(qū)算法

三數(shù)取中法

• 選擇第一個(gè)访递，中間一個(gè)晦嵌，最后一個(gè)三個(gè)數(shù)中間那個(gè)作為分區(qū)點(diǎn)
• 如果要排序的數(shù)組比較大，那“三數(shù)取中”可能就不夠了力九，可能要“五數(shù)取中”或者“十?dāng)?shù)取中”

隨機(jī)法

• 機(jī)法就是每次從要排序的區(qū)間中耍铜，隨機(jī)選擇一個(gè)元素作為分區(qū)點(diǎn)。這種方法并不能保證每次分區(qū)點(diǎn)都選的比較好跌前，但是從概率的角度來(lái)看棕兼，也不大可能會(huì)出現(xiàn)每次分區(qū)點(diǎn)都選的很差的情況，所以平均情況下抵乓，這樣選的分區(qū)點(diǎn)是比較好的伴挚。時(shí)間復(fù)雜度退化為最糟糕的O(n2)的情況靶衍，出現(xiàn)的可能性不大。

Glibc中的qsort()函數(shù)

• ibc是GNU發(fā)布的libc庫(kù)茎芋，即c運(yùn)行庫(kù)颅眶。glibc是linux系統(tǒng)中最底層的api，幾乎其它任何運(yùn)行庫(kù)都會(huì)依賴于glibc
• 對(duì)于數(shù)據(jù)特別小的田弥，會(huì)使用插入排序涛酗；較小的使用歸并排序；特別大的是用快速排序
• 這很重要的一點(diǎn)是因?yàn)槲覀兊臅r(shí)間復(fù)雜度代表的是一種上升趨勢(shì)偷厦，對(duì)于數(shù)據(jù)在代入不同的值的時(shí)候要區(qū)別思考

課后題：在今天的內(nèi)容中商叹，我分析了C語(yǔ)言的中的qsort()的底層排序算法，你能否分析一下你所熟悉的語(yǔ)言中的排序函數(shù)都是用什么排序算法實(shí)現(xiàn)的呢只泼？都有哪些優(yōu)化技巧剖笙？

• 查看了下Arrays.sort的源碼，主要采用TimSort算法, 大致思路是這樣的：

  1 元素個(gè)數(shù) < 32, 采用二分查找插入排序(Binary Sort)
  2 元素個(gè)數(shù) >= 32, 采用歸并排序请唱，歸并的核心是分區(qū)(Run)
  3 找連續(xù)升或降的序列作為分區(qū)弥咪，分區(qū)最終被調(diào)整為升序后壓入棧
  4 如果分區(qū)長(zhǎng)度太小，通過(guò)二分插入排序擴(kuò)充分區(qū)長(zhǎng)度到分區(qū)最小闕值
  5 每次壓入棧十绑，都要檢查棧內(nèi)已存在的分區(qū)是否滿足合并條件聚至，滿足則進(jìn)行合并
  6 最終棧內(nèi)的分區(qū)被全部合并，得到一個(gè)排序好的數(shù)組

  Timsort的合并算法非常巧妙：

  1 找出左分區(qū)最后一個(gè)元素(最大)及在右分區(qū)的位置
  2 找出右分區(qū)第一個(gè)元素(最小)及在左分區(qū)的位置
  3 僅對(duì)這兩個(gè)位置之間的元素進(jìn)行合并孽惰，之外的元素本身就是有序的

15講二分查找（上）：如何用最省內(nèi)存的方式實(shí)現(xiàn)快速查找功能

• 二分查找雖然簡(jiǎn)單晚岭，但隨著做的題目多了，發(fā)現(xiàn)后續(xù)的變化是真的多勋功，甚至不需要一定使用有序的序列

導(dǎo)入：智力題坦报，猜數(shù)字

045608AB-D447-49CA-A46B-D186FA6EC54A

8bce81259abf0e9a06f115e22586b829

• 二分查找針對(duì)的是一個(gè)有序的數(shù)據(jù)集合，查找思想有點(diǎn)類似分治思想狂鞋。每次都通過(guò)跟區(qū)間的中間元素對(duì)比片择，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素骚揍，或者區(qū)間被縮小為0

驚人的查找速度

• 我們的時(shí)間復(fù)雜度是O(logn)字管，這是一個(gè)很牛掰的速度，就算我們需要查找的數(shù)據(jù)集大小為2的32次也就大約是42億信不，也只需要查找32次就能出答案了
• 這里可以參考下阿基米德與國(guó)王下棋的故事參考下指數(shù)的強(qiáng)大

這是一個(gè)很著名的故事：阿基米德與國(guó)王下棋嘲叔，國(guó)王輸了，國(guó)王問(wèn)阿基米德要什么獎(jiǎng)賞抽活？阿基米德對(duì)國(guó)王說(shuō)：“我只要在棋盤(pán)上第一格放一粒米硫戈，第二格放二粒，第三格放四粒下硕，第四格放十六炼∈牛…按這個(gè)方法放滿整個(gè)棋盤(pán)就行．”國(guó)王以為要不了多少糧食汁胆，就隨口答應(yīng)了，結(jié)果國(guó)王輸了

最后需要的大米數(shù)量為2的64次方-1

代碼實(shí)現(xiàn)

非遞歸

• 學(xué)到了霜幼，使用mid = low+((high-low)>>1)
• 別問(wèn)為什么嫩码，問(wèn)就是學(xué)了

int BinarySearch(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (arr[mid] == value) {
            return mid;
        } else if (arr[mid] < value) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
}

• 這樣子返回right，如果查找不到value罪既，那么返回的就是在其中靠左的下標(biāo)
• e.g. arr為{1, 3, 7, 9, 13}铸题，value為0返回-1，value為2返回0

遞歸

• 遞歸做法沒(méi)得說(shuō)萝衩，學(xué)學(xué)學(xué)

int bsearchInternally(vector<int> &arr, int left, int right, int value) {
    if (left > right) {
        return -1;
    }
    
    int mid = left + ((right - left) >> 1);
    if (arr[mid] == value) {
        return mid;
    } else if (arr[mid] < value) {
        return bsearchInternally(arr, mid + 1, right, value);
    } else {
        return bsearchInternally(arr, left, mid - 1, value);
    }
}

• 這個(gè)遞歸應(yīng)該算是比較好理解的那種了

二分的局限性

• 首先回挽，二分查找依賴的是順序表結(jié)構(gòu)没咙，簡(jiǎn)單點(diǎn)說(shuō)就是數(shù)組猩谊。
• 其次，二分查找針對(duì)的是有序數(shù)據(jù)祭刚。
• 再次牌捷，數(shù)據(jù)量太小不適合二分查找。
• 最后涡驮，數(shù)據(jù)量太大也不適合二分查找暗甥。

開(kāi)篇的思考題：如何在1000萬(wàn)個(gè)整數(shù)中快速查找某個(gè)整數(shù)？

• 雖然大部分情況下捉捅，用二分查找可以解決的問(wèn)題撤防，用散列表、二叉樹(shù)都可以解決棒口。但是寄月，我們后面會(huì)講，不管是散列表還是二叉樹(shù)无牵，都會(huì)需要比較多的額外的內(nèi)存空間漾肮。如果用散列表或者二叉樹(shù)來(lái)存儲(chǔ)這1000萬(wàn)的數(shù)據(jù)，用100MB的內(nèi)存肯定是存不下的茎毁。而二分查找底層依賴的是數(shù)組克懊，除了數(shù)據(jù)本身之外，不需要額外存儲(chǔ)其他信息七蜘，是最省內(nèi)存空間的存儲(chǔ)方式谭溉，所以剛好能在限定的內(nèi)存大小下解決這個(gè)問(wèn)題。

課后題

如何編程實(shí)現(xiàn)“求一個(gè)數(shù)的平方根”橡卤？要求精確到小數(shù)點(diǎn)后6位扮念。

• 根據(jù)x的值，判斷求解值y的取值范圍蒜魄。假設(shè)求解值范圍min < y < max扔亥。若0<x<1场躯，則min=x，max=1旅挤；若x=1踢关，則y=1；x>1粘茄，則min=1签舞，max=x；在確定了求解范圍之后柒瓣，利用二分法在求解值的范圍中取一個(gè)中間值middle=(min+max)÷2儒搭，判斷middle是否是x的平方根？若(middle+0.000001)(middle+0.000001)＞x且(middle-0.000001)(middle-0.000001)<x芙贫，根據(jù)介值定理搂鲫，可知middle既是求解值;若middlemiddle > x，表示middle＞實(shí)際求解值磺平，max=middle; 若middlemiddle ＜ x魂仍，表示middle＜實(shí)際求解值，min =middle;之后遞歸求解拣挪！
  備注：因?yàn)槭潜Ａ?位小數(shù)擦酌，所以middle上下浮動(dòng)0.000001用于介值定理的判斷

我剛才說(shuō)了，如果數(shù)據(jù)使用鏈表存儲(chǔ)菠劝，二分查找的時(shí)間復(fù)雜就會(huì)變得很高赊舶，那查找的時(shí)間復(fù)雜度究竟是多少呢？如果你自己推導(dǎo)一下赶诊，你就會(huì)深刻地認(rèn)識(shí)到笼平，為何我們會(huì)選擇用數(shù)組而不是鏈表來(lái)實(shí)現(xiàn)二分查找了。

• 說(shuō)說(shuō)第二題吧甫何，感覺(jué)爭(zhēng)議比較大:
  假設(shè)鏈表長(zhǎng)度為n出吹，二分查找每次都要找到中間點(diǎn)(計(jì)算中忽略奇偶數(shù)差異):
  第一次查找中間點(diǎn)，需要移動(dòng)指針n/2次辙喂；
  第二次捶牢，需要移動(dòng)指針n/4次；
  第三次需要移動(dòng)指針n/8次巍耗；
  ......
  以此類推秋麸，一直到1次為值

  總共指針移動(dòng)次數(shù)(查找次數(shù)) = n/2 + n/4 + n/8 + ...+ 1，這顯然是個(gè)等比數(shù)列炬太，根據(jù)等比數(shù)列求和公式：Sum = n - 1.

  最后算法時(shí)間復(fù)雜度是：O(n-1)灸蟆，忽略常數(shù)，記為O(n)亲族，時(shí)間復(fù)雜度和順序查找時(shí)間復(fù)雜度相同

  但是稍微思考下炒考，在二分查找的時(shí)候可缚，由于要進(jìn)行多余的運(yùn)算，嚴(yán)格來(lái)說(shuō)斋枢，會(huì)比順序查找時(shí)間慢