3. 數據結構相關算法

　　3.1排序算法

　　基本概念

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

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

　　排序分為兩類：內排序和外排序。

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

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

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

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

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

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

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