數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)歸納二（適于清華嚴(yán)版教材)_跨考網(wǎng)

　　第八章　內(nèi)部排序

　　內(nèi)排是DS課程中最后一個(gè)重要的章節(jié)，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型算法題。但是，歸結(jié)到一點(diǎn)，就是考查你對(duì)書本上的各種排序算法及其思想以及其優(yōu)缺點(diǎn)和性能指標(biāo)(時(shí)間復(fù)雜度)能否了如指掌。

　　這一章，我們對(duì)重點(diǎn)的規(guī)納將跟以上各章不同。我們將從以下幾個(gè)側(cè)面來對(duì)排序一章進(jìn)行不同的規(guī)納，以期能更全面的理解排序一章的總體結(jié)構(gòu)及各種算法。

　　從排序算法的種類來分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸并、計(jì)數(shù)等五種排序方法。

　　其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的最根本的不同點(diǎn)，說到底就是根據(jù)什么規(guī)則尋找新元素的插入點(diǎn)。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過控制每次參與排序的數(shù)的總范圍“由小到大”的增量來實(shí)現(xiàn)排序效率提高的目的。

　　交換排序，又稱冒泡排序，在交換排序的基礎(chǔ)上改進(jìn)又可以得到快速排序?？焖倥判虻乃枷耄徽Z以敝之：用中間數(shù)將待排數(shù)據(jù)組一分為二。快速排序，在處理的“問題規(guī)?！边@個(gè)概念上，與希爾有點(diǎn)相反，快速排序，是先處理一個(gè)較大規(guī)模，然后逐漸把處理的規(guī)模降低，最終達(dá)到排序的目的。

　　選擇排序，相對(duì)于前面幾種排序算法來說，難度大一點(diǎn)。具體來說，它可以分為：簡(jiǎn)單選擇、樹選擇、堆排。這三種方法的不同點(diǎn)是，根據(jù)什么規(guī)則選取最小的數(shù)。簡(jiǎn)單選擇，是通過簡(jiǎn)單的數(shù)組遍歷方案確定最小數(shù);樹選擇，是通過“錦標(biāo)賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大(小)者，最終選出最小(大)數(shù);而堆排序，是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，通過堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建立、堆調(diào)整是重要考點(diǎn)。樹選擇排序，也曾經(jīng)在一些學(xué)校中的大型算法題中出現(xiàn)，請(qǐng)大家注意。

　　歸并排序，故名思義，是通過“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實(shí)現(xiàn)歸并。所以，在歸并排序中，關(guān)注最多的就是2路歸并。算法思想比較簡(jiǎn)單，有一點(diǎn)，要銘記在心：歸并排序是穩(wěn)定排序。

　　基數(shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場(chǎng)合，比如撲克牌排序問題等。基數(shù)排序，又分為兩種：多關(guān)鍵字的排序(撲克牌排序)，鏈?zhǔn)脚判?整數(shù)排序)?；鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個(gè)概念將問題規(guī)模規(guī)范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進(jìn)行關(guān)鍵字比較的，這樣得出的最終序列就是一個(gè)有序序列。

　　本章各種排序算法的思想以及偽代碼實(shí)現(xiàn)，及其時(shí)間復(fù)雜度都是必須掌握的，學(xué)習(xí)時(shí)要多注意規(guī)納、總結(jié)、對(duì)比。此外，對(duì)于教材中的10.7節(jié)，要求必須熟記，在理解的基礎(chǔ)上記憶，這一節(jié)幾乎成為很多學(xué)校每年的必考點(diǎn)。

　　數(shù)據(jù)結(jié)構(gòu)大學(xué)教程

　　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)

　　如果你問一個(gè)木匠學(xué)徒：你工作的工具要用什么，他可能會(huì)回答你：“我只要一把錘子和一個(gè)鋸”。但是如果你去問一個(gè)老木工或者是大師級(jí)的建筑師，他會(huì)告訴你“我需要一些精確的工具”。由于計(jì)算機(jī)所解決的問題都是從生活中抽象出來的問題，其復(fù)雜性不言而喻，所以我們需要這樣精確有效的工具去解決現(xiàn)實(shí)生活中的復(fù)雜問題。算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)語言都是這樣的工具。數(shù)據(jù)結(jié)構(gòu)是信息的組織方式。對(duì)于相同的算法，用不同的數(shù)據(jù)結(jié)構(gòu)表示其中的抽象數(shù)據(jù)類型會(huì)造成不同的執(zhí)行效率。這就有必要研究各種抽象數(shù)據(jù)類型用不同的數(shù)據(jù)結(jié)構(gòu)表示的效率差異，以及其適用場(chǎng)合。

　　何謂數(shù)據(jù)結(jié)構(gòu)(What is Data Structure)

　　數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由哪些成分?jǐn)?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)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，好的數(shù)據(jù)結(jié)構(gòu)可以提高算法的效率，它通常與一組算法的集合相對(duì)應(yīng)，通過這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。從學(xué)科角度來講，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。

　　數(shù)據(jù)結(jié)構(gòu)學(xué)科的研究對(duì)象 (The Object of Data Structure Research)

　　數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科，主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)的各種操作。因此，主要有三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu);數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu);對(duì)數(shù)據(jù)的操作(即算法)。通常，算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計(jì)算機(jī)硬件的研究，比如存儲(chǔ)裝置和存取方法，而且解決編譯原理、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)的數(shù)據(jù)元素在存儲(chǔ)器中的分配問題的重要基礎(chǔ)。

　　1.2 基本概念與學(xué)科術(shù)語(Basic Concepts and Terminologies)

　　數(shù)據(jù)(Data):是一個(gè)集合的概念，是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能被輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)處理的符號(hào)的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。

　　數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的基本單位，數(shù)據(jù)中的一個(gè)“個(gè)體”。又稱為“記錄”或者“表目”。

　　數(shù)據(jù)項(xiàng)(Data Item)：數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合。

　　數(shù)據(jù)對(duì)象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

　　數(shù)據(jù)項(xiàng)組成數(shù)據(jù)元素，數(shù)據(jù)元素組成數(shù)據(jù)對(duì)象，數(shù)據(jù)對(duì)象組成數(shù)據(jù)

　　數(shù)據(jù)結(jié)構(gòu)(Data Structure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。它包括三個(gè)方面：數(shù)據(jù)元素的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相適應(yīng)的運(yùn)算(操作)。