數(shù)據(jù)結(jié)構(gòu)復習重點歸納二(適于清華嚴版教材)_跨考網(wǎng)
第八章 內(nèi)部排序
內(nèi)排是DS課程中最后一個重要的章節(jié),建立在此章之上的考題可以有多種類型:填空,選擇,判斷乃至大型算法題。但是,歸結(jié)到一點,就是考查你對書本上的各種排序算法及其思想以及其優(yōu)缺點和性能指標(時間復雜度)能否了如指掌。
這一章,我們對重點的規(guī)納將跟以上各章不同。我們將從以下幾個側(cè)面來對排序一章進行不同的規(guī)納,以期能更全面的理解排序一章的總體結(jié)構(gòu)及各種算法。
從排序算法的種類來分,本章主要闡述了以下幾種排序方法:插入、選擇、交換、歸并、計數(shù)等五種排序方法。
其中,在插入排序中又可分為:直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的最根本的不同點,說到底就是根據(jù)什么規(guī)則尋找新元素的插入點。直接插入是依次尋找,折半插入是折半尋找。希爾排序,是通過控制每次參與排序的數(shù)的總范圍“由小到大”的增量來實現(xiàn)排序效率提高的目的。
交換排序,又稱冒泡排序,在交換排序的基礎(chǔ)上改進又可以得到快速排序??焖倥判虻乃枷耄徽Z以敝之:用中間數(shù)將待排數(shù)據(jù)組一分為二??焖倥判?,在處理的“問題規(guī)?!边@個概念上,與希爾有點相反,快速排序,是先處理一個較大規(guī)模,然后逐漸把處理的規(guī)模降低,最終達到排序的目的。
選擇排序,相對于前面幾種排序算法來說,難度大一點。具體來說,它可以分為:簡單選擇、樹選擇、堆排。這三種方法的不同點是,根據(jù)什么規(guī)則選取最小的數(shù)。簡單選擇,是通過簡單的數(shù)組遍歷方案確定最小數(shù);樹選擇,是通過“錦標賽”類似的思想,讓兩數(shù)相比,不斷淘汰較大(小)者,最終選出最小(大)數(shù);而堆排序,是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì),通過堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建立、堆調(diào)整是重要考點。樹選擇排序,也曾經(jīng)在一些學校中的大型算法題中出現(xiàn),請大家注意。
歸并排序,故名思義,是通過“歸并”這種操作完成排序的目的,既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實現(xiàn)歸并。所以,在歸并排序中,關(guān)注最多的就是2路歸并。算法思想比較簡單,有一點,要銘記在心:歸并排序是穩(wěn)定排序。
基數(shù)排序,是一種很特別的排序方法,也正是由于它的特殊,所以,基數(shù)排序就比較適合于一些特別的場合,比如撲克牌排序問題等?;鶖?shù)排序,又分為兩種:多關(guān)鍵字的排序(撲克牌排序),鏈式排序(整數(shù)排序)?;鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個概念將問題規(guī)模規(guī)范、變小,并且,在排序的過程中,只要按照基排的思想,是不用進行關(guān)鍵字比較的,這樣得出的最終序列就是一個有序序列。
本章各種排序算法的思想以及偽代碼實現(xiàn),及其時間復雜度都是必須掌握的,學習時要多注意規(guī)納、總結(jié)、對比。此外,對于教材中的10.7節(jié),要求必須熟記,在理解的基礎(chǔ)上記憶,這一節(jié)幾乎成為很多學校每年的必考點。
數(shù)據(jù)結(jié)構(gòu)大學教程
The Complete Data Structure Training Course
第一章 數(shù)據(jù)結(jié)構(gòu)及其基本概念
Chapter 1 Data Structure and It’s Basic Concepts
1.1什么是數(shù)據(jù)結(jié)構(gòu)(What is Data Structure)
如果你問一個木匠學徒:你工作的工具要用什么,他可能會回答你:“我只要一把錘子和一個鋸”。但是如果你去問一個老木工或者是大師級的建筑師,他會告訴你“我需要一些精確的工具”。由于計算機所解決的問題都是從生活中抽象出來的問題,其復雜性不言而喻,所以我們需要這樣精確有效的工具去解決現(xiàn)實生活中的復雜問題。算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計語言都是這樣的工具。數(shù)據(jù)結(jié)構(gòu)是信息的組織方式。對于相同的算法,用不同的數(shù)據(jù)結(jié)構(gòu)表示其中的抽象數(shù)據(jù)類型會造成不同的執(zhí)行效率。這就有必要研究各種抽象數(shù)據(jù)類型用不同的數(shù)據(jù)結(jié)構(gòu)表示的效率差異,以及其適用場合。
何謂數(shù)據(jù)結(jié)構(gòu)(What is Data Structure)
數(shù)據(jù)結(jié)構(gòu)是在整個計算機科學與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成,即一個數(shù)據(jù)由哪些成分數(shù)據(jù)構(gòu)成,以什么方式構(gòu)成,呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分數(shù)據(jù)之間的邏輯關(guān)系,而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分數(shù)據(jù)在計算機內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式,好的數(shù)據(jù)結(jié)構(gòu)可以提高算法的效率,它通常與一組算法的集合相對應,通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進行某種操作。從學科角度來講,數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等等的學科。
數(shù)據(jù)結(jié)構(gòu)學科的研究對象 (The Object of Data Structure Research)
數(shù)據(jù)結(jié)構(gòu)作為一門學科,主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu),以及對數(shù)據(jù)的各種操作。因此,主要有三個方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu);數(shù)據(jù)的物理存儲結(jié)構(gòu);對數(shù)據(jù)的操作(即算法)。通常,算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu),算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計算機硬件的研究,比如存儲裝置和存取方法,而且解決編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)元素在存儲器中的分配問題的重要基礎(chǔ)。
1.2 基本概念與學科術(shù)語(Basic Concepts and Terminologies)
數(shù)據(jù)(Data):是一個集合的概念,是對客觀事物的符號表示,在計算機科學中是指所有能被輸入到計算機中,并被計算機處理的符號的總稱。是計算機處理的信息的某種特定的符號表示形式。
數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的基本單位,數(shù)據(jù)中的一個“個體”。又稱為“記錄”或者“表目”。
數(shù)據(jù)項(Data Item):數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)元素是數(shù)據(jù)項的集合。
數(shù)據(jù)對象(Data Object):是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個子集。
數(shù)據(jù)項組成數(shù)據(jù)元素,數(shù)據(jù)元素組成數(shù)據(jù)對象,數(shù)據(jù)對象組成數(shù)據(jù)
數(shù)據(jù)結(jié)構(gòu)(Data Structure):是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。它包括三個方面:數(shù)據(jù)元素的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和相適應的運算(操作)。
2022考研初復試已經(jīng)接近尾聲,考研學子全面進入2023屆備考,跨考為23考研的考生準備了10大課包全程準備、全年復習備考計劃、目標院校專業(yè)輔導、全真復試模擬練習和全程針對性指導;2023考研的小伙伴針也已經(jīng)開始擇校和復習了,跨考考研暢學5.0版本全新升級,無論你在校在家都可以更自如的完成你的考研復習,暑假集訓營帶來了院校專業(yè)初步選擇,明確方向;考研備考全年規(guī)劃,核心知識點入門;個性化制定備考方案,助你贏在起跑線,早出發(fā)一點離成功就更近一點!
點擊右側(cè)咨詢或直接前往了解更多
考研院校專業(yè)選擇和考研復習計劃 | |||
2023備考學習 | 2023線上線下隨時學習 | 34所自劃線院??佳袕驮嚪謹?shù)線匯總 | |
2022考研復試最全信息整理 | 全國各招生院校考研復試分數(shù)線匯總 | ||
2023全日制封閉訓練 | 全國各招生院??佳姓{(diào)劑信息匯總 | ||
2023考研先知 | 考研考試科目有哪些? | 如何正確看待考研分數(shù)線? | |
不同院校相同專業(yè)如何選擇更適合自己的 | 從就業(yè)說考研如何擇專業(yè)? | ||
手把手教你如何選專業(yè)? | 高校研究生教育各學科門類排行榜 |
相關(guān)推薦
跨考考研課程
班型 | 定向班型 | 開班時間 | 高定班 | 標準班 | 課程介紹 | 咨詢 |
秋季集訓 | 沖刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+專業(yè)課1對1+專業(yè)課定向輔導+協(xié)議加強課程(高定班)+專屬規(guī)劃答疑(高定班)+精細化答疑+復試資源(高定班)+復試課包(高定班)+復試指導(高定班)+復試班主任1v1服務(高定班)+復試面授密訓(高定班)+復試1v1(高定班) | |
2023集訓暢學 | 非定向(政英班/數(shù)政英班) | 每月20日 | 22800起(協(xié)議班) | 13800起 | 先行階在線課程+基礎(chǔ)階在線課程+強化階在線課程+真題階在線課程+沖刺階在線課程+專業(yè)課針對性一對一課程+班主任全程督學服務+全程規(guī)劃體系+全程測試體系+全程精細化答疑+擇校擇專業(yè)能力定位體系+全年關(guān)鍵環(huán)節(jié)指導體系+初試加強課+初試專屬服務+復試全科標準班服務 |