軟考軟件設(shè)計師專題講義九：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

　　3. 數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

　　3.1排序算法

　　基本概念

　　排序(Sorting)是計算機程序設(shè)計中的一種重要操作，其功能是對一個數(shù)據(jù)元素集合或序列重新排列成一個按數(shù)據(jù)元素某個項值有序的序列。作為排序依據(jù)的數(shù)據(jù)項稱為“排序碼”，也即數(shù)據(jù)元素的關(guān)鍵碼。為了便于查找，通常希望計算機中的數(shù)據(jù)表是按關(guān)鍵碼有序的。如有序表的折半查找，查找效率較高。還有，二叉排序樹、B-樹和B+樹的構(gòu)造過程就是一個排序過程。若關(guān)鍵碼是主關(guān)鍵碼，則對于任意待排序序列，經(jīng)排序后得到的結(jié)果是唯一的;若關(guān)鍵碼是次關(guān)鍵碼，排序結(jié)果可能不唯一，這是因為具有相同關(guān)鍵碼的數(shù)據(jù)元素，這些元素在排序結(jié)果中，它們之間的的位置關(guān)系與排序前不能保持。

　　若對任意的數(shù)據(jù)元素序列，使用某個排序方法，對它按關(guān)鍵碼進行排序：若相同關(guān)鍵碼元素間的位置關(guān)系，排序前與排序后保持一致，稱此排序方法是穩(wěn)定的;而不能保持一致的排序方法則稱為不穩(wěn)定的。

　　排序分為兩類：內(nèi)排序和外排序。

　　內(nèi)排序：指待排序列完全存放在內(nèi)存中所進行的排序過程，適合不太大的元素序列。

　　外排序：指排序過程中還需訪問外存儲器，足夠大的元素序列，因不能完全放入內(nèi)存，只能使用外排序。

　　對于有n個結(jié)點的線性表(e0，e1，…，en-1)，將結(jié)點中某些數(shù)據(jù)項的值按遞增或遞減的次序，重新排列線性表結(jié)點的過程，稱為排序。排序時參照的數(shù)據(jù)項稱為排序碼，通常選擇結(jié)點的鍵值作為排序碼。

　　若線性表中排序碼相等的結(jié)點經(jīng)某種排序方法進行排序后，仍能保持它們在排序之前的相對次序，稱這種排序方法是穩(wěn)定的;否則，稱這種排序方法是不穩(wěn)定的。

　　在排序過程中，線性表的全部結(jié)點都在內(nèi)存，并在內(nèi)存中調(diào)整它們在線性表中的存儲順序，稱為內(nèi)排序。在排序過程中，線性表只有部分結(jié)點被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整結(jié)點在外存中的存放順序的排序方法成為外排序。

　　下面通過一個表格簡單介紹幾種常見的內(nèi)排序方法，以及比較一下它們之間的性能特點。

　　　　　　　計算機軟考軟件設(shè)計師練習(xí)試題及答案解析匯總