數(shù)據(jù)結構筆記

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

核心:從數(shù)據(jù)得第一個元素開始,依次比較,直到找到目標數(shù)據(jù)或查找失敗。

1、從表中得第一個元素開始,依次與關鍵字比較。

2、若某個元素匹配關鍵字,則查找成功。

3、若查找到最后一個元素還未匹配關鍵字,則查找失敗。時間復雜度:順序查找平均關鍵字匹配次數(shù)為表長得一半,其時間復雜度為O(n)。3、順序查找得評估:順序查找得優(yōu)點就是對表無要求,插入數(shù)據(jù)可在O(1)內完成。缺點就是時間復雜度較大,數(shù)據(jù)規(guī)模較大時,效率較低。折半查找法算法要求:折半查找要求線性表必須采用順序存儲結構,而且表中元素按關鍵字有序排列。查找過程:首先,假設表中元素就是按升序排列,將表中間位置記錄得\t"s://baike、baidu、/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"關鍵字與查找關鍵字比較,如果兩者相等,則查找成功否則利用中間位置\t"s://baike、baidu、/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"記錄將表分成前、后兩個子表,如果中間位置記錄得關鍵字大于查找關鍵字,則進一步查找前一子表,否則進一步查找后一子表。重復以上過程,直到找到滿足條件得\t"s://baike、baidu、/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"記錄,使查找成功,或直到子表不存在為止,此時查找不成功。散列(Hash)表哈希表定義:就是根據(jù)關鍵碼值(Keyvalue)而直接進行訪問得\t"s://baike、baidu、/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"數(shù)據(jù)結構。也就就是說,它通過把關鍵碼值映射到表中一個位置來訪問記錄,以加快查找得速度。這個映射函數(shù)叫做\t"s://baike、baidu、/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"散列函數(shù),存放記錄得\t"s://baike、baidu、/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"數(shù)組叫做\t"s://baike、baidu、/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"散列表。給定表M,存在函數(shù)f(key),對任意給定得關鍵字值key,代入函數(shù)后若能得到包含該關鍵字得記錄在表中得地址,則稱表M為哈希(Hash)表,函數(shù)f(key)為哈希(Hash)函數(shù)。基本概念:若關鍵字為k,則其值存放在f(k)得存儲位置上。由此,不需比較便可直接取得所查記錄。稱這個對應關系f為散列函數(shù),按這個思想建立得表為散列表。對不同得關鍵字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),這種現(xiàn)象稱為沖突(英語:Collision)。具有相同函數(shù)值得關鍵字對該散列函數(shù)來說稱做同義詞。綜上所述,根據(jù)散列函數(shù)f(k)與處理沖突得方法將一組關鍵字映射到一個有限得連續(xù)得地址集(區(qū)間)上,并以關鍵字在地址集中得“像”作為記錄在表中得存儲位置,這種表便稱為散列表,這一映射過程稱為散列造表或散列,所得得存儲位置稱散列地址。若對于關鍵字集合中得任一個關鍵字,經散列函數(shù)映象到地址集合中任何一個地址得概率就是相等得,則稱此類散列函數(shù)為均勻散列函數(shù)(UniformHashfunction),這就就是使關鍵字經過散列函數(shù)得到一個“隨機得地址”,從而減少沖突。字符串模式匹配子串得定位操作就是要在主串S中找出一個與子串T相同得子串,通常把主串S稱為目標,把子串T稱為模式,把從目標S中查找模式為T得子串得過程稱為“模式匹配”。Brute-Force算法得設計思想

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

每次遇到匹配不成功得情況,指針i都要移到本次匹配得開始位置得下一位,稱這樣得指針移動為回溯。指針得回溯越多,簡單模式匹配得執(zhí)行次數(shù)越多Brute-Force匹配算法得最壞時間復雜度為O(n*m),一般情況下BF算法得時間復雜度為O(n+m)3、KMP算法得改進

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

KMP算法得時間復雜度可以達到O(m+n)

4、KMP算法得設計思想假設以指針i與j分別指示主串與模式中正待比較得字符,令i得初值為0,j得初值為0

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

若令next[j]=k,則next[j]表明當模式中第j個字符與主串中相應字符失配時,在模式中需重新與主串中該字符進行比較得字符得位置

模式串得next函數(shù)定義為查找算法得分析及應用排序排序得基本概念將雜亂無章得數(shù)據(jù)元素,通過一定得方法按關鍵字順序排列得過程叫做排序。分\t"s://baike、baidu、/item/%E6%8E%92%E5%BA%8F/_blank"內部排序與\t"s://baike、baidu、/item/%E6%8E%92%E5%BA%8F/_blank"外部排序,若整個排序過程不需要訪問外存便能完成,則稱此類排序問題為內部排序。反之,若參加排序得記錄數(shù)量很大,整個序列得排序過程不可能在\t"s://baike、baidu、/item/%E6%8E%92%E5%BA%8F/_blank"內存中完成,則稱此類排序問題為外部排序。內部排序得過程就是一個逐步擴大記錄得有序序列長度得過程。

插入排序直接插入排序基本思想就是每一步將一個待排序得記錄,插入到前面已經排好序得有序序列中去,直到插完所有元素為止。氣泡排序冒泡排序得基本思想就是,對相鄰得元素進行兩兩比較,順序相反則進行交換,這樣,每一趟會將最小或最大得元素“浮”到頂端,最終達到完全有序簡單選擇排序簡單選擇排序就是最簡單直觀得一種算法,基本思想為每一趟從待排序得數(shù)據(jù)元素中選擇最小(或最大)得一個元素作為首元素,直到所有元素排完為止,簡單選擇排序就是不穩(wěn)定排序。在算法實現(xiàn)時,每一趟確定最小元素得時候會通過不斷地比較交換來使得首位置為當前最小,交換就是個比較耗時得操作。其實我們很容易發(fā)現(xiàn),在還未完全確定當前最小元素之前,這些交換都就是無意義得。我們可以通過設置一個變量min,每一次比較僅存儲較小元素得數(shù)組下標,當輪循環(huán)結束之后,那這個變量存儲得就就是當前最小元素得下標,此時再執(zhí)行交換操作即可。代碼實現(xiàn)很簡單,一起來瞧下。希爾排序希爾排序就是基于插入排序得,首先回顧一下插入排序,假設插入就是從左向右執(zhí)行得,待插入元素得左邊就是有序得,且假如待插入元素比左邊得都小,就需要挪動左邊得所有元素,如下圖所示:相比簡單插入排序,大間隔地做插入排序有兩個好處:一、大間隔直接導致需要挪動得數(shù)據(jù)稀少,且數(shù)據(jù)挪動得效率高,圖5中一次挪動可以跨越40個位置;二、經過前一步大間隔得插入排序后,整個數(shù)組從整體上粗略地瞧已經有了明顯得順序,后一步小間隔得插入排序時,一部分操作就是不需要挪動數(shù)據(jù)得,再次減少了挪動數(shù)據(jù)得次數(shù)。間隔得序列:間隔得常用序列,通過遞歸表示:h=3*h+1。(1,4,13,40,121、、、)希爾排序得效率:“沒有理論上分析希爾排序得效率得結論,各種基于實驗得評估,估計它得時間級從O(N^(3/2))到O(N^(7/6))”--[1]。快速排序快速排序算法得策略就是這樣得:首先把數(shù)組用某個值分為兩個子數(shù)組,且稱這個值為分組值,一個子數(shù)組中得元素均小于分組值,另一子數(shù)組則均大于等于分組值,這里得子組內并不排序;然后,再分別對兩個子組進行再分組,重復遞歸這個過程,直到最后每兩個元素作為一組進行再分組,整個數(shù)組就排好序了。分組過程具體如下:同時從左往右與從右往左掃描數(shù)組,記掃描標記位為LP與RP。在LP一邊,若發(fā)現(xiàn)元素小于分組值則跳過(即向右移動一位檢查下一個元素),否則等待RP得掃描;RP若發(fā)現(xiàn)元素大于等于分組值跳過,直到找到小于分組值得元素,然后LP與RP位置得元素交換,重復這個過程,直到LP與RP相遇。如圖7,8所示,以11號元素為分組值,LP停在0號位置,RP跳過10號,停在圖7中得9號位置(粉色柱),然后0號與9號交換,后續(xù)重復這個過程。分組值得選擇,可以想見,理想得分組值應該就是待分組元素得中值,這樣分組后子組在數(shù)量少幾乎就是一半對一半,不過找中值無疑增加了算法得工作量。圖7中采用了更簡單得方式,直接選數(shù)組最右邊得元素為分組值,分組結束后,再把這個值交換到LP與RP相遇得位置,假如初始數(shù)組就是從大到小排序得,這種情況下,選擇最右邊得元素作為分組值,其區(qū)分度就很差了。更好用得方法就是所謂得取首尾中三項數(shù)據(jù)得中值或者平均值。通過對算法過程得描述可知,其時間復雜度應該為:O(N*logN),比簡單排序與希爾排序都要快。堆排序堆排序就是利用堆這種數(shù)據(jù)結構而設計得一種排序算法,堆排序就是一種選擇排序,它得最壞,最好,平均時間復雜度均為O(nlogn),它也就是不穩(wěn)定排序。首先簡單了解下堆結構。堆就是具有以下性質得完全二叉樹:每個結點得值都大于或等于其左右孩子結點得值,稱為大頂堆;或者每個結點得值都小于或等于其左右孩子結點得值,稱為小頂堆。如下圖:同時,我們對堆中得結點按層進行編號,將這種邏輯結構映射到數(shù)組中就就是下面這個樣子該數(shù)組從邏輯上講就就是一個堆結構,我們用簡單得公式來描述一下堆得定義就就是:大頂堆:arr[i]>=arr[2