9.2?排序的基本概念與分類

9.2.1?排序的定義
??????? 排序是我們生活中經常會面對的問題。同學們做操時會按照從矮到高排列；老師查看上課出勤情況時，會按學生學號順序點名；高考錄取時，會按成績總分降序依次錄取等。那排序的嚴格定義是什么呢？
??????? 假設含有n個記錄的序列為{r1,r2,……,rn}，其相應的關鍵字分別為{k1,k2,……,kn}，需確定1，2，……，n的一種排列p1,p2,……,pn，使其相應的關鍵字滿足kp1≤kp2≤……≤kpn（非遞減或非遞增）關系，即使得序列成為一個按關鍵字有序的序列{rp1,rp2,……,rpn}，這樣的操作就稱為排序。
??????? 注意我們在排序問題中，通常將數據元素稱為記錄。顯然我們輸入的是一個記錄集合，輸出的也是一個記錄集合，所以說，可以將排序看成是線性表的一種操作。
??????? 排序的依據是關鍵字之間的大小關系，那么，對同一個記錄集合，針對不同的關鍵字進行排序，可以得到不同序列。
??????? 這里關鍵字ki可以是記錄r的主關鍵字，也可以是次關鍵字，甚至是若干數據項的組合。比如我們某些大學為了選拔在主科上更優秀的學生，要求對所有學生的所有科目總分降序排名，并且在同樣總分的情況下將語數外總分做降序排名。這就是對總分和語數外總分兩個次關鍵字的的組合排序。如圖9-2-1，對于組合排序的問題，當然可以先排序總分，若總分相等的情況下，再排序語數外總分，但這是比較土的辦法。我們還可以應用一個技巧來實現一次排序即完成組合排序問題，例如把總分與語數外都當成字符串首尾連接在一起（注意語數外總分如果位數不夠三位需要在前面補零），很容易可以得到令狐沖的“753229”要小于張無忌的“753236”，于是張無忌就排在了令狐沖的前面。

??????? 從這個例子也可看出，多個關鍵字的排序最終都可以轉化為單個關鍵字的排序，因此，我們這里主要討論的是單個關鍵字的排序。

?

9.2.2?排序的穩定性
??????? 也正是由于排序不僅是針對主關鍵字，那么對于次關鍵字，因為待排序的記錄序列中可能存在兩個或兩個以上的關鍵字相等的記錄，排序結果可能會存在不唯一的情況，我們給出了穩定與不穩定排序的定義。
??????? 假設ki=kj（1≤i≤n,1≤j≤n,i≠j），且在排序前的序列中ri領先于rj（即i<j）。如果排序后ri仍領先于rj，則稱所用的排序方法是穩定的；反之，若可能使得排序后的序列中rj領先ri，則稱所用的排序方法是不穩定的。如圖9-2-2，經過對總分的降序排序后，總分高的排在前列。此時對于令狐沖和張無忌而言，未排序時是令狐沖在前，那么它們總分排序后，分數相等的令狐沖依然應該在前，這樣才算是穩定的排序，如果他們二者顛倒了，則此排序是不穩定的了。只要有一組關鍵字實例發生類似情況，就可認為此排序方法是不穩定的。排序算法是否穩定的，要通過分析后才能得出。

?

9.2.3?內排序與外排序
??????? 根據在排序過程中待排序的記錄是否全部被放置在內存中，排序分為：內排序和外排序。
??????? 內排序是在排序整個過程中，待排序的所有記錄全部被放置在內存中。外排序是由于排序的記錄個數太多，不能同時放置在內存，整個排序過程需要在內外存之間多次交換數據才能進行。我們這里主要就介紹內排序的多種方法。
??????? 對于內排序來說，排序算法的性能主要是受三個方面影響
??????? 1)?時間性能。排序是數據處理中經常執行的一種操作，往往屬于系統的核心部分，因此排序算法的時間開銷是衡量其好壞的最重要的標志。在內排序中，主要進行兩種操作：比較和移動。比較指關鍵字之間的比較，這是要做排序最起碼的操作。移動指記錄從一個位置移動到另一個位置，事實上，移動可以通過改為記錄的存儲方式來予以避免（這個我們在講解具體的算法時再談）。總之，高效率的內排序算法應該是具有盡可能少的關鍵字比較次數和盡可能少的記錄移動次數。
??????? 2)?輔助空間。評價排序算法的另一個主要標準是執行算法所需要的輔助存儲空間。輔助存儲空間是除了存放待排序所占用的存儲空間之外，執行算法所需要的其他存儲空間。
??????? 3)?算法的復雜性。注意這里指的是算法本身的復雜度，而不是指算法的時間復雜度。顯然算法過于復雜也會影響排序的性能。
??????? 根據排序過程中借助的主要操作，我們把內排序分為：插入排序、交換排序、選擇排序和歸并排序?？梢哉f，這些都是比較成熟的排序技術，已經被廣泛地應用于許許多多的程序語言或數據庫當中，甚至它們都已經封裝了關于排序算法的實現代碼。因此，我們學習這些排序算法的目的更多原因并不是為了去在現實中編程排序算法，而是通過學習來提高我們編寫算法的能力，以便于去解決更多復雜和靈活的應用性問題。
本章一共要講解七種排序的算法，按照算法的復雜度分為兩大類，冒泡排序、簡單選擇排序和直接插入排序屬于簡單算法，而希爾排序、堆排序、歸并排序、快速排序屬于改進算法。后面我們將依次講解。

9.2.4?排序用到的結構與函數
??????? 為了講清楚排序算法的代碼，我先提供一個用于排序用的順序表結構，此結構也將用于之后我們要講的所有排序算法。

#define MAXSIZE 10 /* 用于要排序數組個數最大值，可根據需要修改 */ typedef struct {int r[MAXSIZE+1]; /* 用于存儲要排序數組，r[0]用作哨兵或臨時變量 */int length; /* 用于記錄順序表的長度 */ }SqList;

??????? 另外，由于排序最最常用到操作是數組兩元素的交換，我們將它寫成函數，在之后的講解中會大量的用到。

/* 交換L中數組r的下標為i和j的值 */void swap(SqList *L,int i,int j) { int temp=L->r[i]; L->r[i]=L->r[j]; L->r[j]=temp; }

??????? 好了，說了這么多，我們來看第一個排序算法。

出處：http://www.cnblogs.com/cj723/archive/2011/04/14/2016029.html

總結

以上是生活随笔為你收集整理的《大话数据结构》第9章 排序 9.2 排序的基本概念与分类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。