3. 數(shù)據(jù)結構相關算法

　　3.1排序算法

　　基本概念

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

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

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

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

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

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

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

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

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

　　　　　　　計算機軟考軟件設計師練習試題及答案解析匯總