上一章的 小全棧任務(wù)“番茄post”【1】拆分里程碑 最后，預(yù)料到接下來采用的將是增量模型的軟件開發(fā)模型。每一個增量都會經(jīng)歷針對該增量的分析、設(shè)計(jì)、編碼、測試、交付階段?！袄锍瘫北悴皇枨蠓治龅囊馕?。到了這一章，針對“番茄post”做概要設(shè)計(jì)；鑒于我們對項(xiàng)目的初始探索，這次概要設(shè)計(jì)將是一個簡化版，沒有詳細(xì)的文檔作為內(nèi)容沉淀。

1

隨著軟件的規(guī)模越來越大、結(jié)構(gòu)越來越復(fù)雜、開發(fā)工具落后、軟件開發(fā)管理困難而復(fù)雜等歷史原因，在十九世紀(jì)六十年代中期爆發(fā)了眾所周知的軟件危機(jī)。為了解決問題，在 1968、1969 年連續(xù)召開的兩次著名的北大西洋公約組織(NATO)會議時，提出了軟件工程的概念。

概要設(shè)計(jì)是軟件工程中所占比例很重的環(huán)節(jié)，在這個實(shí)踐過程中不僅將軟件工程的知識與數(shù)據(jù)庫、VB 以及數(shù)據(jù)結(jié)構(gòu)等知識相結(jié)合的知識交叉地帶，更是軟件設(shè)計(jì)的關(guān)鍵，為下一階段的詳細(xì)設(shè)計(jì)做參考。

設(shè)計(jì)軟件結(jié)構(gòu)的具體任務(wù)是：將一個復(fù)雜系統(tǒng)按功能進(jìn)行模塊劃分、建立模塊的層次結(jié)構(gòu)及調(diào)用關(guān)系、確定模塊間的接口及人機(jī)界面等。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)包括數(shù)據(jù)特征的描述、確定數(shù)據(jù)的結(jié)構(gòu)特性、以及數(shù)據(jù)庫的設(shè)計(jì)。顯然，概要設(shè)計(jì)建立的是目標(biāo)系統(tǒng)的邏輯模型，與計(jì)算機(jī)無關(guān)。知識錯綜復(fù)雜，這里閑談而至僅作點(diǎn)醒之筆。

2

鑒于我們對原型圖制作的不熟程度，尋找?guī)卓钍忻嫔匣诜压ぷ鞣ǖ能浖宰鞣褜W(xué)習(xí)，尋找?guī)卓钍忻嫔系纳鐓^(qū)軟件以作借鑒。

番茄土豆

番茄土豆見名知意，是對番茄工作法和 todo-list 的一次結(jié)合嘗試，美觀大方，簡潔如賓。功能上除了將剛剛提到的番茄工作法和 todo-list 結(jié)合之外，也有每日 8 個番茄目標(biāo)、番茄統(tǒng)計(jì)和番茄歷史等功能。同時，番茄土豆在各大 PC 端、Web 端、移動端乃至谷歌插件，都有相應(yīng)的訪問入口。

番茄盒子

Windows 平臺的免費(fèi)項(xiàng)目番茄盒子也毫不遜色，除了對番茄工作內(nèi)容的記錄、分析之外還有上網(wǎng)控制，時間記錄等功能，是一款功能強(qiáng)大的自我管理軟件。所謂“上網(wǎng)控制”，指在用戶主動設(shè)定想要克制住自己不去訪問的網(wǎng)站后，將在該段時間無法瀏覽這類網(wǎng)站，并在開啟“強(qiáng)力監(jiān)控”的情況下，無法修改設(shè)置甚至關(guān)閉、卸載軟件也無法后悔。

番茄鐘 for ios

作為一個移動端的基于番茄工作法來培養(yǎng)用戶專注力、提高工作效率的軟件，番茄鐘的界面夠簡潔，功能足夠豐富?？梢苑窒碜约旱姆褦?shù)據(jù)和查看排行榜，擁有了一定的社交屬性，值得借鑒。

簡書、知乎

不用多多介紹，簡書和知乎應(yīng)該是很多網(wǎng)客喜歡去的地方，作為社交性平臺，這些社區(qū)的首頁、關(guān)注頁里的很多哲學(xué)思維值得迭代中的“番茄post”原型圖吸收。

簡書

知乎

3

回顧主題，這里我們將共同探討并快速畫出“番茄post”的原型圖、組件圖、數(shù)據(jù)結(jié)構(gòu)圖和事件列表至白板上，以確定一個明確的、共同的開發(fā)目標(biāo)。

可見，對“番茄post”作出的簡化版概要設(shè)計(jì)這一階段，是里程碑的具體，也是接下來詳細(xì)設(shè)計(jì)階段的鋪墊。

更多內(nèi)容，持續(xù)更新中~。

• Hello，我是韓亦樂，現(xiàn)任本科軟工男一枚。軟件工程專業(yè)的一路學(xué)習(xí)中，我有很多感悟，也享受持續(xù)分享的過程。如果想了解更多或能及時收到我的最新文章，歡迎訂閱我的個人微信號：韓亦樂。我的簡書個人主頁中，有我的訂閱號二維碼和 Github 主頁地址；我的知乎主頁 中也會堅(jiān)持產(chǎn)出，歡迎關(guān)注。
• 本文內(nèi)部編號經(jīng)由我的 Github 相關(guān)倉庫統(tǒng)一管理；本文可能發(fā)布在多個平臺但僅在上述倉庫中長期維護(hù)；本文同時采用【知識共享署名-非商業(yè)性使用-禁止演繹 4.0 國際許可協(xié)議】進(jìn)行許可。
  
  
  最早擁有排序概念的機(jī)器出現(xiàn)在 1901 至 1904 年間由 Hollerith 發(fā)明出使用基數(shù)排序法的分類機(jī)，此機(jī)器系統(tǒng)包括打孔，制表等功能，1908 年分類機(jī)第一次應(yīng)用于人口普查，并且在兩年內(nèi)完成了所有的普查數(shù)據(jù)和歸檔。
  Hollerith 在 1896 年創(chuàng)立的分類機(jī)公司的前身，為電腦制表記錄公司（CTR）。他在電腦制表記錄公司（CTR）曾擔(dān)任顧問工程師，直到1921年退休，而電腦制表記錄公司（CTR）在1924年正式改名為IBM。
  ---- 摘自《維基百科 - 插入排序》

期中已到，期末將至。《算法設(shè)計(jì)與分析》的“預(yù)習(xí)”階段藉此開始~。在眾多的算法思想中，如果你沒有扎實(shí)的數(shù)據(jù)結(jié)構(gòu)的功底，不知道棧與隊(duì)列，哈希表與二叉樹，不妨可以從排序算法開始練手?？v觀各類排序算法，常見的、經(jīng)典的排序算法將由此篇引出。

排序算法的輸出必須遵守的下列兩個原則：

• 輸出結(jié)果為遞增序列（遞增是針對所需的排序順序而言）
• 輸出結(jié)果是原輸入的一種排列、或是重組

十大經(jīng)典排序算法

十大經(jīng)典的排序算法及其時間復(fù)雜度和穩(wěn)定性如上表所示。判斷一個排序算法是否穩(wěn)定是看在相等的兩個數(shù)據(jù)排序算法執(zhí)行完成后是否會前后關(guān)系顛倒，如若顛倒，則稱該排序算法為不穩(wěn)定，例如選擇排序和快速排序。

排序前：(4, 1) (3, 1) (3, 7)（5, 6）

排序后：(3, 1) (3, 7) (4, 1) (5, 6) （穩(wěn)定，維持次序）
排序后：(3, 7) (3, 1) (4, 1) (5, 6) （不穩(wěn)定，次序被改變）

00.交換兩個整數(shù)的值

接下來十個經(jīng)典排序算法的詳細(xì)探討缺少不了交換兩個整數(shù)值的掌握，這里回顧一下其中三種方交換法：用臨時變量交換兩個整數(shù)的值(SwapTwo_1)、不用第三方變量交換兩個整數(shù)的值(SwapTwo_2)、使用位運(yùn)算交換兩個整數(shù)的值(SwapTwo_3)。其中用臨時變量交換兩個整數(shù)的值效率最高，后倆者只適用于內(nèi)置整型數(shù)據(jù)類型的交換，并不高效。

void SwapTwo_1 (int *a, int* b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void SwapTwo_2 (int *a, int *b) {
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

void SwapTwo_3 (int *a, int *b) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

01. 冒泡排序(BubbleSort)

先不說公司面試筆試，大學(xué)實(shí)驗(yàn)室的納新題里最常有的就是冒泡排序。冒泡排序重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。這個算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端。由于它的簡潔，冒泡排序通常被用來對于程序設(shè)計(jì)入門的學(xué)生介紹算法的概念。

[圖片上傳失敗...(image-9172dd-1509644584398)]](http://upload-images.jianshu.io/upload_images/2558748-990f8de3fbdbb50d.gif?imageMogr2/auto-orient/strip)

上圖可見，冒泡排序算法的運(yùn)作如下：

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

通俗來講，整個冒泡排序就是通過兩次循環(huán)，外層循環(huán)將此輪最大(小)值固定到此輪尾部，內(nèi)層循環(huán)“冒泡”比較相鄰的兩個元素并決定是否交換位置。

從上圖也可理解冒泡排序如何將每一輪最大（?。┲倒潭ǖ酱溯單膊浚何膊靠倿橛行驙顟B(tài)，前面無序狀態(tài)區(qū)根據(jù)大小規(guī)則冒泡向后方傳遞最值。

/*
 * 冒泡排序。每次外循環(huán)將最值固定到數(shù)組最后
 * @param: {int []} arr
 * @param: {int} len
 * @return null;
 */
void BubbleSort (int arr[], int len) {
    int i, j, temp;
    for (int i = 0; i < len - 1; i++) {
        // 每趟 i 循環(huán)將最大(小)值固定到最后一位
        for (int j = 0; j < len - 1 - i; j++) {
            // 每趟 j 循環(huán)循環(huán)沒有被固定到后方的數(shù)字
            if (arr[j] > arr[j + 1]) {
                // arr[j] < arr[j + 1] 代表從小到大排序
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

更多十大經(jīng)典排序算法請戳我的 Github 倉庫 @LeetCode-C

02. 選擇排序(SelectionSort)

選擇排序首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動有關(guān)。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當(dāng)中至少有一個將被移到其最終位置上，因此對n個元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。

上圖左下角和右上角可以分別看做排序序列起始位置(已排序區(qū))和排序序列末尾(未排序區(qū))，左下角一直穩(wěn)定更新，但選擇排序不穩(wěn)定，即排序后曾經(jīng)相同的兩個元素的前后位置關(guān)系可能會發(fā)生顛倒。

/*
 * 選擇排序。每次外循環(huán)選擇最值固定到數(shù)組開始
 * @param: {int []} arr[]
 * @param: {int} len
 * @return null;
 */
void SelectionSort (int arr[], int len) {
    int i, j, temp, min;
    for (i = 0; i < len - 1; i++) {
        min = i;
        for (j = i + 1; j < len - 1; j++) {
            if (arr[min] > arr[j]) {
                // 只需找到最小的值的位置后一次性替換
                min = j;
            }
            temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}

更多十大經(jīng)典排序算法請戳我的 Github 倉庫 @LeetCode-C

03. 插入排序(InsertionSort)

插入排序的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用 in-place
排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

一般來說，插入排序都采用 in-place 在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：

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

如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個變種，稱為二分查找插入排序。這里先不做涉及。

/*
 * 插入排序。前面有序的數(shù)字循環(huán)向后留給滿足條件的第一個無序數(shù)字
 * @param: {int []} arr
 * @param: {int} len
 * @return null;
 */
void InsertionSort (int arr[], int len) 
{
    int i, j, temp;
    for (i = 1; i < len; i++) {
        // 與已排序的數(shù)逐一比較，大于 temp 時，該數(shù)向后移
        temp = arr[i];
        // 如果將賦值放到下面的for循環(huán)內(nèi), 會導(dǎo)致在第10行出現(xiàn) j 未聲明的錯誤
        j = i - 1;
        for (; j >= 0 && arr[j] > temp; j--) {
            // j 循環(huán)到-1時，由于短路求值，不會運(yùn)算 arr[-1]
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = temp; 
        // 被排序數(shù)放到正確的位置
    }
}

更多十大經(jīng)典排序算法請戳我的 Github 倉庫 @LeetCode-C

04. 希爾排序(ShellSort)

希爾排序按其設(shè)計(jì)者希爾（Donald Shell）的名字命名，該算法由1959年公布。希爾排序也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

• 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達(dá)到線性排序的效率
• 插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動一位

希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進(jìn)一大步。然后算法再取越來越小的步長進(jìn)行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）。

以23, 10, 4, 1的步長序列進(jìn)行希爾排序。

步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。算法最開始以一定的步長進(jìn)行排序。然后會繼續(xù)以一定步長進(jìn)行排序，最終算法以步長為1進(jìn)行排序。當(dāng)步長為1時，算法變?yōu)椴迦肱判颍@就保證了數(shù)據(jù)一定會被排序。

已知的最好步長序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,...)，這項(xiàng)研究也表明“比較在希爾排序中是最主要的操作，而不是交換?！庇眠@樣步長序列的希爾排序比插入排序要快，甚至在小數(shù)組中比快速排序和堆排序還快，但是在涉及大量數(shù)據(jù)時希爾排序還是比快速排序慢。

/*
 * 希爾排序。
 * @param: {int []} arr
 * @param: {int} len
 * @return null;
 */
void ShellSort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap >>= 1) {
        // gap 為間隔，每次間隔折半
        for (i = gap; i < len; i++) {
            // 循環(huán)該輪數(shù)組后半段
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                // 根據(jù)當(dāng)前 grap 間隔和條件進(jìn)行插入排序前的后移
                arr[j + gap] = arr[j];
            }
            // 插入到當(dāng)前位置
            arr[j + gap] = temp;
        }
    }
}

更多十大經(jīng)典排序算法請戳我的 Github 倉庫 @LeetCode-C

05. 歸并排序(MergeSort)

歸并排序是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為 O(n log n)。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用，且各層分治遞歸可以同時進(jìn)行。

歸并操作（merge），也叫歸并算法，指的是將兩個已經(jīng)排序的序列合并成一個序列的操作。歸并排序算法依賴歸并操作。

歸并排序用迭代法和遞歸法都可以實(shí)現(xiàn)，迭代法的算法步驟為：

• 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
• 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
• 比較兩個指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置
• 重復(fù)步驟3直到某一指針到達(dá)序列尾
• 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

遞歸法的算法步驟為：

• 將序列每相鄰兩個數(shù)字進(jìn)行歸并操作，形成 floor(n/2) 個序列，排序后每個序列包含兩個元素
• 將上述序列再次歸并，形成 floor(n/4) 個序列，每個序列包含四個元素
• 重復(fù)步驟 2，直到所有元素排序完畢

/*
 * 歸并排序。迭代版
 * @param: {int []} arr
 * @param: {int} len
 * @return null;
 */
void MergeSort_1 (int arr[], int len) {
    int* a = arr;
    int* b = (int*) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = Min (start + seg, len), high = Min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

int Min(int x, int y) {
    return x < y ? x : y;
}

/*
 * 歸并排序。遞歸版
 * @param: {int []} arr
 * @param: {const int} len
 * @return null;
 */
void MergeSort_2 (int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

void merge_sort_recursive (int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

總結(jié)【上】

這篇文章“十大經(jīng)典排序算法及其 C 語言實(shí)現(xiàn)【上】”引出了十大經(jīng)典算法的前五個并用 C 語言實(shí)踐：冒泡排序、選擇排序、插入排序、希爾排序和歸并排序，并作出了充足的圖文解釋。即將推出的“十大經(jīng)典排序算法及其 C 語言實(shí)現(xiàn)【下】”將對剩下五個經(jīng)典算法快速排序、堆排序、計(jì)數(shù)排序、桶排序、基數(shù)排序作出完善，盡請期待~。

維基百科 - 排序算法

• Hello，我是韓亦樂，現(xiàn)任本科軟工男一枚。軟件工程專業(yè)的一路學(xué)習(xí)中，我有很多感悟，也享受持續(xù)分享的過程。如果想了解更多或能及時收到我的最新文章，歡迎訂閱我的個人微信號：韓亦樂。我的簡書個人主頁中，有我的訂閱號二維碼和 Github 主頁地址；我的知乎主頁 中也會堅(jiān)持產(chǎn)出，歡迎關(guān)注。
• 本文內(nèi)部編號經(jīng)由我的 Github 相關(guān)倉庫統(tǒng)一管理；本文可能發(fā)布在多個平臺但僅在上述倉庫中長期維護(hù)；本文同時采用【知識共享署名-非商業(yè)性使用-禁止演繹 4.0 國際許可協(xié)議】進(jìn)行許可。