數(shù)據(jù)結(jié)構(gòu)筆記

數(shù)據(jù)構(gòu)造筆記基礎(chǔ)：數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造基本概念數(shù)據(jù)（data）：是對客觀事物的符號表達，在計算機科學(xué)中是指全部能輸入到計算機中并被計算機程序解決的符號總稱數(shù)據(jù)元素（dataelement）：是數(shù)據(jù)的基本單位，在計算機中普通被當做一種整體進行考慮和解決數(shù)據(jù)對象（dataobject）：性質(zhì)相似的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一種子集數(shù)據(jù)構(gòu)造（datastructure）：互相之間存在一種或多個特定關(guān)系的數(shù)據(jù)元素的集合4類基本構(gòu)造：集合、線性構(gòu)造、樹形構(gòu)造、圖形（網(wǎng)狀）構(gòu)造數(shù)據(jù)構(gòu)造的形式定義為數(shù)據(jù)構(gòu)造是一種二元組DataStructure=（D,S），其中D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集數(shù)據(jù)構(gòu)造定義中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此又稱為數(shù)據(jù)的邏輯構(gòu)造數(shù)據(jù)構(gòu)造在計算機中的表達（映像）稱為物理構(gòu)造（存儲構(gòu)造）計算機中表達信息的最小單位是二進制中的一位，叫做位（bit），一到若干位構(gòu)成一種位串表達一種數(shù)據(jù)元素，這個位串稱為元素或結(jié)點數(shù)據(jù)構(gòu)造之間關(guān)系在計算機中的表達有兩種：次序映像、非次序映像，并由此得到兩種存儲構(gòu)造：次序存儲、鏈式存儲，前者運用相對位置表達數(shù)據(jù)元素間的邏輯構(gòu)造，后者借助指針任何一種算法的設(shè)計取決于數(shù)據(jù)（邏輯）構(gòu)造，而實現(xiàn)依賴于存儲構(gòu)造數(shù)據(jù)類型是一種值的集合和定義在這個值集上的一組操作的總稱數(shù)據(jù)類型分兩種：原子類型、構(gòu)造類型，前者不可分解（例如int、char、float、void），后者構(gòu)造類型由若干成分按某種構(gòu)造構(gòu)成，可分解，成分既能夠是非構(gòu)造的也能夠是構(gòu)造的（例：數(shù)組）抽象數(shù)據(jù)類型（AbstractDataType）：是指一種數(shù)學(xué)模型及定義在該模型上的一組操作（P8）抽象數(shù)據(jù)類型格式以下：ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>數(shù)據(jù)操作：<數(shù)據(jù)操作的定義>}ADT抽象數(shù)據(jù)類型名基本操作格式以下：基本操作名（參數(shù)表）初始條件：<初始條件描述>操作成果：<操作成果描述>多形數(shù)據(jù)類型（polymorphicdatatype）：是指其值得成分不擬定的數(shù)據(jù)類型（P9）抽象數(shù)據(jù)類型可由固有數(shù)據(jù)類型來表達和實現(xiàn)算法（概念）和算法分析（時、空性能）算法（algorithm）：對特定問題求解環(huán)節(jié)的一種描述算法5特性：有窮、擬定、可行、輸入、輸出1、有窮性：算法必須在可接受的時間內(nèi)執(zhí)行有窮步后結(jié)束2、擬定性：每條指令必須要有確切含義，無二義性，并且只有唯一執(zhí)行途徑，即對相似的輸入只能得相似輸出3、可行性：算法中的操作都可通過已實現(xiàn)的基本運算執(zhí)行有限次來完畢4、輸入：一種算法有一到多個輸入，并取自某個特定對象合集5、輸出：一種算法有一到多個輸出，這些輸出與輸入有著某些特定關(guān)系的量算法設(shè)計規(guī)定（好算法）：對的性、可讀性、強健性、效率與低存儲需求強健性是指對于規(guī)范規(guī)定以外的輸入能夠判斷出這個輸入不符合規(guī)范規(guī)定，并能有合理的解決方式。算法效率的度量：事后統(tǒng)計：程序運行結(jié)束后借助計算機內(nèi)部計時功效，缺點一是必須先運行根據(jù)算法編制的程序，二是受限于計算機軟硬件，造成掩蓋了算法本身的優(yōu)劣事前分析預(yù)計：消耗時間影響因素：算法方略、問題規(guī)模、編程語言、編譯程序產(chǎn)生的機器碼質(zhì)量、機器執(zhí)行指令的速度撇開多個影響因素只考慮問題的規(guī)模（普通用整數(shù)量n表達），記為問題規(guī)模的函數(shù)算法時間取決于控制構(gòu)造（次序，分支，循環(huán)）和固有數(shù)據(jù)類型操作的綜合效果書寫格式：T（n）=O（f（n））f（n）為n的某個函數(shù)時間復(fù)雜度：算法的漸近時間復(fù)雜度（asymptotictimecomplexity），它表達隨問題規(guī)模的增大，算法執(zhí)行時間的增加率和f（n）的增加率相似以循環(huán)最深層原操作為度量基準頻度：該語句重復(fù)執(zhí)行的次數(shù)算法的存儲空間需求：空間復(fù)雜度（spacecomplexity）：算法所需存儲空間度量，記作S（n）=O（f（n）），其中n為問題規(guī)模的大小一、線性表線性表基本概念線性表（linear_list）：n個數(shù)據(jù)元素的有限序列構(gòu)造特點：存在唯一的被稱作“第一種”、“最后一種”的數(shù)據(jù)元素，且除了第一種以外每個元素都有唯一前驅(qū)，除最后一種以外都有唯一后繼在復(fù)雜線性表中存在：數(shù)據(jù)項->統(tǒng)計->文獻，例如每個學(xué)生狀況為一種統(tǒng)計，它由學(xué)號、性別......數(shù)據(jù)項構(gòu)成，多個學(xué)生統(tǒng)計構(gòu)成一種文獻在形如（a1，...，ai-1，ai，ai+1，...，an）中，ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1，且形成直接前驅(qū)元素，直接后繼元素關(guān)系元素個數(shù)n定義為線性表長度，n=0為空表有關(guān)操作算法見書（P20）線性表次序存儲構(gòu)造和鏈式存儲構(gòu)造（1）線性表次序表達和實現(xiàn)線性表次序存儲在一組持續(xù)的存儲單元中，鏈式存儲則不規(guī)定；次序構(gòu)造能夠隨機訪問，鏈式構(gòu)造能夠無限擴容擬定存儲位置（計算公式）：第i個元素：LOC（ai）=LOC（a1）+（i-1）*LL是偏移量，即每個元素占用存儲單元第ai+1個元素：LOC（ai+1）=LOC（ai）+La1（起始地址或基地址）C語言下標從“0”開始，則表中第i個元素是L.elem[i-1]當對線性表進行操作時，被操作元素背面的元素角標會對應(yīng)變化（前移、后移），算法（P24）（2）線性表鏈式表達和實現(xiàn)特點：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（存儲單元不一定持續(xù)）結(jié)點存儲數(shù)據(jù)元素及直接后繼的存儲位置信息，兩個域：數(shù)據(jù)域和指針域，指針域中存儲的信息稱為指針或鏈，僅含有一種指針域故又稱線性鏈表或單鏈表鏈表的插入：先增加一條指針再修改原指針頭指針指向第一種數(shù)據(jù)元素的存儲位置，最后一種結(jié)點的指針為空（NULL）鏈表表達辦法及算法（P28）單鏈表第一種結(jié)點前加一種頭結(jié)點Head，其數(shù)據(jù)域可為空也可存儲某些附加信息（鏈長等）假設(shè)p是指向線性表中i個元素（ai）的指針，則p->next是指向i+1個數(shù)據(jù)元素在單鏈表中，獲得第i個元素必須從頭指針開始尋找，因此單鏈表是非隨機的存儲構(gòu)造線性表指邏輯構(gòu)造，從抽象數(shù)據(jù)層面來說次序表和鏈表指物理存儲構(gòu)造邏輯構(gòu)造：離散、線性、層次、網(wǎng)狀應(yīng)用見書算法二、棧和隊列棧的基本概念棧（stack）是限定僅在表尾進行插入或刪除操作的線性表表尾為棧頂，表頭為棧底，遵照后進先出原理（（lastinfirston，LIFO），不含元素則為空棧操作：在棧頂插入（入棧）和刪除（出棧），棧初始化、判空、取棧頂元素（算法P45）棧的次序存儲和鏈式存儲次序棧，即棧的次序存儲構(gòu)造是運用一組持續(xù)的存儲單元依次寄存自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)指針top批示棧頂元素在次序棧中的位置初始棧時不應(yīng)限定棧的最大容量，基本做法是先為棧分派一種基本容量，然后在應(yīng)用過程中，不夠用再逐段擴大（算法P46）遞歸棧與遞歸的實現(xiàn)：一種直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)，稱為遞歸函數(shù)階乘函數(shù)、2階Fibonacci數(shù)列、Ackerman函數(shù)、3階Hanoi問題（多階呢？）（P54）函數(shù)調(diào)用函數(shù)執(zhí)行過程筆記（P56）隊列隊列先進先出（firstinfirstout，F(xiàn)IFO），隊尾一端插入，隊首一端刪除元素（日常排隊）隊列與棧都有八種基本操作（P59），隊列普通用鏈表實現(xiàn)，棧用次序表實現(xiàn)雙端隊列（限定操作的隊列）（P60）棧和隊列的應(yīng)用鏈隊列、循環(huán)隊列（P60），離散事件模擬（銀行接待工作（P65））特殊矩陣的壓縮存儲如何存儲矩陣的元，使矩陣的運算有效進行。高級語言慣用二維數(shù)組存儲陣元面對如高階矩陣，多值相似矩陣和多零元素矩陣進行壓縮存儲節(jié)省空間壓縮存儲：為多個值相似的元只分派一種空間，對零元不分派值相似元素或零元素含有分布規(guī)律則稱為特殊矩陣，反之為稀疏矩陣具體應(yīng)用與算法（P95）三、樹與二叉樹樹的基本概念樹是非線性數(shù)據(jù)構(gòu)造，以分支關(guān)系定義的層次構(gòu)造樹是n（n>=0）個結(jié)點的有限集詳見（P118），基本術(shù)語（P120）二叉樹二叉樹的定義及其重要特性：二叉樹是每個結(jié)點最多有兩個子樹的樹構(gòu)造。普通子樹被稱作“左子樹”（leftsubtree）和“右子樹”（rightsubtree）。性質(zhì)：1.2.3.滿二叉樹：完全二叉樹：4.5.二叉樹的次序存儲構(gòu)造和鏈式存儲構(gòu)造次序存儲，用一組地址持續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點元素，即將完全二叉樹上編號為i的結(jié)點依次存儲在如上定義的一位數(shù)組下標為i-1的分量中。123456789鏈式存儲，每個結(jié)點中最少包含三個域,[左指針，數(shù)據(jù)，右指針]，稱作“二叉鏈表”增加一種雙親指針域，則稱作“三叉鏈表”詳見P126-127二叉樹的遍歷遍歷二叉樹，每個結(jié)點均被訪問一次，且僅有一次。在限定先左后右的訪問序列后，有三種遍歷方式：先序（DLR），中序（LDR）,后續(xù)（LRD）P129算法6.1（波蘭式）層次遍歷，無論那種遍歷方式，對含n個結(jié)點的二叉樹，時間復(fù)雜度都為O（n），空間復(fù)雜度也為O（n）。線索二叉樹的基本概念和構(gòu)造摘要：對于n個結(jié)點的二叉樹，在二叉鏈存儲構(gòu)造中有n+1（2n-（n-1））個空鏈域，運用這些空鏈域寄存在某種遍歷次序下該結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點的指針，這些指針稱為線索概念：加上了線索的二叉鏈表稱為線索鏈表，對應(yīng)的二叉樹稱為線索二叉樹(ThreadedBinaryTree)。構(gòu)造辦法：樹與森林樹的存儲構(gòu)造鏈表構(gòu)造：1.雙親表達法2.孩子表達法3.孩子兄弟表達法詳見P135森林與二叉樹轉(zhuǎn)換左孩子右兄弟樹與森林的遍歷先序、中序遍歷，詳見P139當以二叉鏈表做樹的存儲構(gòu)造時，樹的先序=二叉樹先序、樹的后序=二叉樹中序樹與二叉樹的應(yīng)用二叉排序樹二叉排序樹（BinarySortTree），又稱二叉查找樹（BinarySearchTree），亦稱二叉搜索樹。定義：二叉排序樹或者是一棵空樹，或者是含有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上全部結(jié)點的值均不大于它的根結(jié)點的值；（2）若右子樹不空，則右子樹上全部結(jié)點的值均不不大于它的根結(jié)點的值；（3）左、右子樹也分別為二叉排序樹；（4）沒有鍵值相等的節(jié)點。查找：環(huán)節(jié)：若根結(jié)點的核心字值等于查找的核心字，成功。否則，若不大于根結(jié)點的核心字值，遞歸查左子樹。若不不大于根結(jié)點的核心字值，遞歸查右子樹。若子樹為空，查找不成功。平衡二叉樹(AVL)定義：它或者是一顆空樹，或者含有下列性質(zhì)的二叉樹：它的左子樹和右子樹的深度之差(平衡因子)的絕對值不超出1，且它的左子樹和右子樹都是一顆平衡二叉樹。平衡因子(bf)：結(jié)點的左子樹的深度減去右子樹的深度，那么顯然-1<=bf<=1圖一，圖二都是BST，但只有圖一是AVLtree哈夫曼（Huffman）樹和哈夫曼編碼哈夫曼樹是一類帶權(quán)途徑長度最短的樹，又稱最優(yōu)樹。途徑和途徑長度概念：從樹中一種結(jié)點到另一種結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的途徑，途徑上的分支數(shù)目稱為途徑長度。樹的途徑長度是從樹根到每一結(jié)點的途徑長度之和。推廣到普通狀況，考慮帶權(quán)結(jié)點：結(jié)點的帶權(quán)途徑長度為從該結(jié)點到樹根之間的途徑長度與結(jié)點上的權(quán)值的乘積，樹的帶權(quán)途徑長度為樹中全部葉子結(jié)點的帶權(quán)途徑長度之和，記作WPL=△帶權(quán)途徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹哈夫曼算法構(gòu)造哈夫曼樹（P145）哈夫曼編碼前綴編碼：設(shè)計長短不等的編碼，任一字符的編碼都不是另一種字符的編碼的前綴運用二叉樹來設(shè)計前綴編碼商定左分支表達字符“0”右分支表達字符“1”則從根結(jié)點到葉子結(jié)點的途徑上分支字符構(gòu)成的字符串作為該葉子結(jié)點字符的編碼。普通狀況，當帶有權(quán)值時，本質(zhì)上就是設(shè)計一棵哈夫曼樹，得到二進制前綴編碼=哈夫曼編碼------算法詳見P147圖圖的基本概念圖是一種數(shù)據(jù)構(gòu)造，加上一組基本操作，構(gòu)成的一種抽象數(shù)據(jù)類型詳見（P156）途中數(shù)據(jù)元素普通稱為頂點，V是頂點的有窮非空集合；VR是兩個頂點的關(guān)系集合，若<v，w>屬于VR，則<v,w>表達從v到w的弧，稱v為弧尾（初始點），w尾弧頭（終止點）此時圖是有向圖，若<v，w>屬于VR必有<w，v>屬于VR，則以無序?qū)?lt;v，w>，表達v和w的一條邊，此時稱圖為無向圖完全圖有向完全圖邊或弧極少（e<nlogn）的圖，稱為稀疏圖，反之為稠密圖邊或弧所含有的有關(guān)數(shù)稱為權(quán)，帶權(quán)的圖稱為網(wǎng)子圖連通圖（二）圖的存儲及基本操作1.鄰接矩陣法用兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）的信息，和數(shù)據(jù)元素之間的關(guān)系（邊或?。┑男畔⑺惴ㄔ斠姡≒161）鄰接表法鄰接表是圖的一種鏈式存儲構(gòu)造。算法詳見（P163）（三）圖的遍歷1.深度優(yōu)先搜索（DFS）類似于樹的先根遍歷，可把圖轉(zhuǎn)化為樹操作。圖示及算法（P168）2.廣度優(yōu)先搜索類似于樹的層次遍歷，可把圖轉(zhuǎn)為樹操作。詳見（P169）（四）圖的基本應(yīng)用1.最?。ù鷥r）生成樹（P173）普里姆算法構(gòu)造最小生成樹：克魯斯卡爾算法構(gòu)造最小生成樹：2.最短途徑（P186）在圖中從頂點A到B，找一條所含邊（?。┳钌俚耐緩剑瑥腁開始做廣度優(yōu)先搜索，直到B結(jié)束，則稱為最短途徑?？赏茝V的含權(quán)值的情形，此時最短途徑度量是途徑上權(quán)值之和帶權(quán)有向圖：源點->終點迪杰斯特拉算法：3.拓撲排序由某個集合上的偏序得到該集合的全序偏序：若集合X上的關(guān)系R是自反的、反對稱的和傳遞的，則稱R是集合X上的偏序關(guān)系；設(shè)R是集合上的偏序，如果對每個x，y屬于X必有xRy或yRx，則稱R是集合X上的全序關(guān)系。詳見（P180）4.核心途徑（最長途徑）（P183）查找查找的基本概念在某些（有序的/無序的）數(shù)據(jù)元素中，通過一定的辦法找出與給定核心字相似的數(shù)據(jù)元素的過程叫做查找。也就是根據(jù)給定的某個值，在查找表中擬定一種核心字等于給定值的統(tǒng)計或數(shù)據(jù)元素。次序查找法次序查找：

核心：從數(shù)據(jù)的第一種元素開始，依次比較，直到找到目的數(shù)據(jù)或查找失敗。

1.從表中的第一種元素開始，依次與核心字比較。

2.若某個元素匹配核心字，則查找成功。

3.若查找到最后一種元素尚未匹配核心字，則查找失敗。時間復(fù)雜度：次序查找平均核心字匹配次數(shù)為表長的二分之一，其時間復(fù)雜度為O(n)。3.次序查找的評定：次序查找的優(yōu)點是對表無規(guī)定，插入數(shù)據(jù)可在O(1)內(nèi)完畢。缺點是時間復(fù)雜度較大，數(shù)據(jù)規(guī)模較大時，效率較低。折半查找法算法規(guī)定：折半查找規(guī)定線性表必須采用次序存儲構(gòu)造，并且表中元素按核心字有序排列。查找過程：首先，假設(shè)表中元素是按升序排列，將表中間位置統(tǒng)計的核心字與查找核心字比較，如果兩者相等，則查找成功否則運用中間位置統(tǒng)計將表分成前、后兩個子表，如果中間位置統(tǒng)計的核心字不不大于查找核心字，則進一步查找前一子表，否則進一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的統(tǒng)計，使查找成功，或直到子表不存在為止，此時查找不成功。散列（Hash）表哈希表定義：是根據(jù)核心碼值(Keyvalue)而直接進行訪問的數(shù)據(jù)構(gòu)造。也就是說，它通過把核心碼值映射到表中一種位置來訪問統(tǒng)計，以加緊查找的速度。這個映射函數(shù)叫做散列函數(shù)，寄存統(tǒng)計的數(shù)組叫做散列表。給定表M，存在函數(shù)f(key)，對任意給定的核心字值key，代入函數(shù)后若能得到包含該核心字的統(tǒng)計在表中的地址，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash)函數(shù)?；靖拍睿喝艉诵淖譃閗，則其值寄存在f(k)的存儲位置上。由此，不需比較便可直接獲得所查統(tǒng)計。稱這個對應(yīng)關(guān)系f為散列函數(shù)，按這個思想建立的表為散列表。對不同的核心字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，這種現(xiàn)象稱為沖突（英語：Collision）。含有相似函數(shù)值的核心字對該散列函數(shù)來說稱做同義詞。總而言之，根據(jù)散列函數(shù)f(k)和解決沖突的辦法將一組核心字映射到一種有限的持續(xù)的地址集（區(qū)間）上，并以核心字在地址集中的“像”作為統(tǒng)計在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。若對于核心字集合中的任一種核心字，經(jīng)散列函數(shù)映象到地址集合中任何一種地址的概率是相等的，則稱這類散列函數(shù)為均勻散列函數(shù)（UniformHashfunction），這就是使核心字通過散列函數(shù)得到一種“隨機的地址”，從而減少沖突。字符串模式匹配子串的定位操作是要在主串S中找出一種與子串T相似的子串，普通把主串S稱為目的，把子串T稱為模式，把從目的S中查找模式為T的子串的過程稱為“模式匹配”。Brute-Force算法的設(shè)計思想

Brute-Force是普通的模式匹配算法。將主串S的第1個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串的下一字符起，重新與模式的第一種字符比較，直到主串的一種持續(xù)子串字符序列與模式相等，返回值為S中與T匹配的子序列第一種字符的序號，即匹配成功；否則，匹配失敗，返回值0。Brute-Force算法的特點：

每次碰到匹配不成功的狀況，指針i都要移到本次匹配的開始位置的下一位，稱這樣的指針移動為回溯。指針的回溯越多，簡樸模式匹配的執(zhí)行次數(shù)越多Brute-Force匹配算法的最壞時間復(fù)雜度為O(n*m)，普通狀況下BF算法的時間復(fù)雜度為O(n+m)3.KMP算法的改善

每當一趟匹配過程中出現(xiàn)字符比較不等時，不需回溯指針i，而是運用已經(jīng)得到的“部分匹配”的成果將模式向右“滑動”盡量遠的一段距離后，繼續(xù)比較

KMP算法的時間復(fù)雜度能夠達成O(m+n)

4.KMP算法的設(shè)計思想假設(shè)以指針i和j分別批示主串和模式中正待比較的字符，令i的初值為0，j的初值為0

若在匹配過程中，Si=Pj，則i和j分別增1，否則i不變，而j退到next[j]的位置再比較，若相等，則指針各自增1，否則j再退到下一種next值的位置，依次類推

若令next[j]=k，則next[j]表明當模式中第j個字符與主串中對應(yīng)字符失配時，在模式中需重新和主串中該字符進行比較的字符的位置

模式串的next函數(shù)定義為查找算法的分析及應(yīng)用排序排序的基本概念將雜亂無章的數(shù)據(jù)元素，通過一定的辦法按核心字次序排列的過程叫做排序。分內(nèi)部排序和外部排序，若整個排序過程不需要訪問外存便能完畢，則稱這類排序問題為內(nèi)部排序。反之，若參加排序的統(tǒng)計數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完畢，則稱這類排序問題為外部排序。內(nèi)部排序的過程是一種逐步擴大統(tǒng)計的有序序列長度的過程。

插入排序直接插入排序基本思想是每一步將一種待排序的統(tǒng)計，插入到前面已經(jīng)排好序的有序序列中去，直到插完全部元素為止。氣泡排序冒泡排序的基本思想是，對相鄰的元素進行兩兩比較，次序相反則進行交換，這樣，每一趟會將最小或最大的元素“浮”到頂端，最后達成完全有序簡樸選擇排序簡樸選擇排序是最簡樸直觀的一種算法，基本思想為每一趟從待排序的數(shù)據(jù)元素中選擇最小（或最大）的一種元素作為首元素，直到全部元素排完為止，簡樸選擇排序是不穩(wěn)定排序。在算法實現(xiàn)時，每一趟擬定最小元素的時候會通過不停地比較交換來使得首位置為現(xiàn)在最小，交換是個比較耗時的操作。其實我們很容易發(fā)現(xiàn)，在尚未完全擬定現(xiàn)在最小元素之前，這些交換都是無意義的。我們能夠通過設(shè)立一種變量min，每一次比較僅存儲較小元素的數(shù)組下標，當輪循環(huán)結(jié)束之后，那這個變量存儲的就是現(xiàn)在最小元素的下標，此時再執(zhí)行交換操作即可。代碼實現(xiàn)很簡樸，一起來看下。希爾排序希爾排序是基于插入排序的，首先回想一下插入排序，假設(shè)插入是從左向右執(zhí)行的，待插入元素的左邊是有序的，且如果待插入元素比左邊的都小，就需要挪動左邊的全部元素，以下圖所示：相比簡樸插入排序，大間隔地做插入排序有兩個好處：一、大間隔直接造成需要挪動的數(shù)據(jù)稀少，且數(shù)據(jù)挪動的效率高，圖5中一次挪動能夠跨越40個位置；二、通過前一步大間隔的插入排序后，整個數(shù)組從整體上粗略地看已有了明顯的次序，后一步小間隔的插入排序時，一部分操作是不需要挪動數(shù)據(jù)的，再次減少了挪動數(shù)據(jù)的次數(shù)。間隔的序列：間隔的慣用序列，通過遞歸表達：h=3*h+1。（1,4,13,40,121...）希爾排序的效率：“沒有理論上分析希爾排序的效率的結(jié)論，多個基于實驗的評定，預(yù)計它的時間級從O(N^(3/2))到O(N^(7/6))”--[1]?？焖倥判蚩焖倥判蛩惴ǖ姆铰允沁@樣的：首先把數(shù)組用某個值分為兩個子數(shù)組，且稱這個值為分組值，一種子數(shù)組中的元素均不大于分組值，另一子數(shù)組則均不不大于等于分組值，這里的子組內(nèi)并不排序；然后，再分別對兩個子組進行再分組，重復(fù)遞歸這個過程，直到最后每兩個元素作為一組進行再分組，整個數(shù)組就排好序了。分組過程具體以下：同時從左往右和從右往左掃描數(shù)組，記掃描標記位為LP和RP。在LP一邊，若發(fā)現(xiàn)元素不大于分組值則跳過（即向右移動一位檢查下一種元素），否則等待RP的掃描；RP若發(fā)現(xiàn)元素不不大于等于分組值跳過，直到找到不大于分組值的元素，然后LP和RP位置的元素交換，重復(fù)這個過程，直到LP和RP相遇。如圖7,8所示，以11號元素為分組值，LP停在0號位置，RP跳過10號，停在圖7中的9號位置（粉色柱），然后0號和9號交換，后續(xù)重復(fù)這個過程。分組值的選擇，能夠想見，抱負的分組值應(yīng)當是待分組元素的中值，這樣分組后子組在數(shù)量少幾乎是二分之一對二分之一，但是找中值無疑增加了算法的工作量。圖7中采用了更簡樸的方式，直接選數(shù)組最右邊的元素為分組值，分組結(jié)束后，再把這個值交換到LP和RP相遇的位置，如果初始數(shù)組是從大到小排序的，這種狀況下，選擇最右邊的元素作為分組值，其分辨度就很差了。更加好用的辦法是所謂的取首尾中三項數(shù)據(jù)的中值或者平均值。通過對算法過程的描述可知，其時間復(fù)雜度應(yīng)當為：O(N*logN)，比簡樸排序和希爾排序都要快。堆排序堆排序是運用堆這種數(shù)據(jù)構(gòu)造而設(shè)計的一種排序算法，堆排序是一種選擇排序，它的最壞，最佳，平均時間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序。首先簡樸理解下堆構(gòu)造。堆是含有下列性質(zhì)的完全二叉樹：每個結(jié)點的值都不不大于或等于其左右孩子結(jié)點的值，稱為大頂堆；或者每個結(jié)點的值都不大于或等于其左右孩子結(jié)點的值，稱為小頂堆。以下圖：同時，我們對堆中的結(jié)點按層進行編號，將這種邏輯構(gòu)造映射到數(shù)組中就是下面這個樣子該數(shù)組從邏輯上講就是一種堆構(gòu)造，我們用簡樸的公式來描述一下堆的定義就是：大頂堆：arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]

小頂堆：arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2]

堆排序的基本思想是：將待排序序列構(gòu)造成一種大