資料局結構——排序演算法
一、複習要點
排序是使用最頻繁的一類演算法。排序分內排序與外排序。內排序演算法主要分5大類，有12個演算法。
在插入排序類中討論了直接插入排序、二分法插入排序、表插入排序和shell排序演算法；在交換排序類中討論了起泡排序和快速排序演算法；在選擇排序類中討論了簡單選擇排序、錦標賽排序和堆排序演算法；在歸併排序類中討論了迭代的兩路歸併排序和遞迴的表歸併排序演算法；在多排序碼排序類中討論了最低位優先的鍊錶基數排序演算法。其中，不穩定的排序方法有shell排序、簡單選擇排序、快速排序和堆排序；適合於待排序物件數目n比較大的排序方法有快速排序、堆排序、歸併排序和基數排序；排序碼比較次數不受物件排序碼初始排列影響的排序方法有折半插入排序、簡單選擇排序、錦標賽排序、兩路歸併排序和基數排序，其中，當排序碼的初始排列接近有序時，直接插入排序和起泡排序等增長很快，而快速排序則變成慢速排序。
外排序是基於外存的排序方法。由於外存以順序訪問的效率最高，以歸併排序最為適合。因此，外排序以k路平衡歸併為主。
在k個物件排序碼中選取最小排序碼，採用了敗者樹。這是一種高效的選擇演算法。此外，還討論了初始歸併段生成的方法，最佳歸併樹等問題。
本章複習的要點是：
1、基本知識點
要求理解排序的基本概念，包括什麼是排序，排序的穩定性，排序的效能分析，如時間代價（物件排序碼的比較次數和物件的移動次數）和空間代價（附加物件個數）。掌握插入排序（直接插入排序；折半插入排序；鍊錶插入排序）、交換排序（起泡排序；快速排序）、選擇排序（直接選擇排序；鍊錶選擇排序；錦標賽排序；堆排序）、迭代的歸併排序等內排序的方法及其效能分析方法。理解基數排序方法及其效能分析方法。
理解多路平衡歸併等外排序方法及敗者樹構造方法。理解生成初始歸併段及敗者樹構造方法。理解最佳歸併樹的建立方法。
2、演算法設計
插入排序：直接插入排序演算法、折半插入排序演算法、鍊錶插入排序演算法
交換排序：起泡排序演算法，快速排序的遞迴演算法和用棧實現的非遞迴演算法
選擇排序：直接選擇排序演算法，鍊錶選擇排序演算法，堆排序演算法
歸併排序：兩路歸併演算法，迭代的歸併排序演算法；遞迴的鍊錶歸併排序演算法和用佇列實現的非遞迴鍊錶歸併排序演算法
其它排序演算法：計數排序演算法，奇偶排序演算法
二、難點和重點
1、基本概念：排序碼、初始排序碼排列、排序碼比較次數、資料移動次數、穩定性、附加儲存、內部排序、外部排序
2、插入排序
當待排序的排序碼序列已經基本有序時，用直接插入排序最快
3、選擇排序
用直接選擇排序在乙個待排序區間中選出最小的資料時，與區間第乙個資料對調，而不是順次後移。這導致方法不穩定。
當在n個資料(n很大)中選出最小的5 8個資料時，錦標賽排序最快
錦標賽排序的演算法中將待排序的資料個數n補足到2的k次冪2k-1 < n 2k
在堆排序中將待排序的資料組織成完全二叉樹的順序儲存。
4、交換排序
快速排序是乙個遞迴的排序方法
當待排序排序碼序列已經基本有序時，快速排序顯著變慢。
5、二路歸併排序
歸併排序可以遞迴執行
歸併排序需要較多的附加儲存。可以採用一種「推拉法」實現歸併排序，演算法的時間複雜度為o (n)、空間複雜度為o(1)
歸併排序對待排序排序碼的初始排列不敏感，排序速度較穩定
6、外排序
多路平衡歸併排序的過程、i/o緩衝區個數的配置
外排序的時間分析、利用敗者樹進行多路平衡歸併
利用置換選擇方法生成不等長的初始歸併段
最佳歸併樹的構造及wpl的計算
三、教材中習題的解析
9-1 什麼是內排序? 什麼是外排序? 什麼排序方法是穩定的? 什麼排序方法是不穩定的?
【解答】
內排序是排序過程中參與排序的資料全部在記憶體中所做的排序，排序過程中無需進行內外存資料傳送，決定排序方法時間效能的主要是資料排序碼的比較次數和資料物件的移動次數。外排序是在排序的過程中參與排序的資料太多，在記憶體中容納不下，因此在排序過程中需要不斷進行內外存的資訊傳送的排序。決定外排序時間效能的主要是讀寫磁碟次數和在記憶體中總的記錄物件的歸併次數。
不穩定的排序方法主要有希爾排序、直接選擇排序、堆排序、快速排序。不穩定的排序方法往往是按一定的間隔移動或交換記錄物件的位置，從而可能導致具有相等排序碼的不同物件的前後相對位置在排序前後顛倒過來。其他排序方法中如果有資料交換，只是在相鄰的資料物件間比較排序碼，如果發生逆序(與最終排序的順序相反的次序)才交換，因此具有相等排序碼的不同物件的前後相對位置在排序前後不會顛倒，是穩定的排序方法。
但如果把演算法中判斷逆序的比較「>(或<)」改寫成「≥(或≤)」，也可能造成不穩定。
9-2 設待排序的排序碼序列為, 試分別寫出使用以下排序方法每趟排序後的結果。並說明做了多少次排序碼比較。
(1) 直接插入排序2) 希爾排序(增量為5,2,13) 起泡排序
(4) 快速排序5) 直接選擇排序6) 錦標賽排序
(7) 堆排序8) 二路歸併排序9) 基數排序
【解答】
(1) 直接插入排序
(2) 希爾排序(增量為5,2,1)
希爾(shell)本人採取的增量序列為 n/2, n/2/2, n/2/2/2, …,1。一般地，增量序列可採用nα, nαα, nααα, …, 1。大量實驗表明，取α=0.
45454的增量序列比取其他的增量序列的優越性更顯著。計算 0.45454n 的乙個簡單方法是用整數算術計算(5*n-1)/11。
需要注意，當< 1/2時，增量序列可能不以1結束，需要加以判斷和調整。
(3) 起泡排序
(4) 快速排序
左子串行遞迴深度為1，右子串行遞迴深度為3。
(5) 直接選擇排序
資料結構實驗 排序
排序實驗 常用排序方法實現 實驗目的 1 熟悉常用的內部排序方法 插入排序 選擇排序 交換排序 基數排序和歸併排序 2 通過實驗，掌握排序的思路和方法，並能分析常用的排序方法的時間複雜度和穩定性。實驗要求 1 在vc 或tc環境下實現基本功能 2 先完成基本功能，基本功能為必做內容，有多餘時間的同學...
資料結構查詢排序實驗
實驗五 查詢和排序 班級 b09513 學號 200940 姓名 一 實驗目的 1 掌握查詢的不同方法，並能用高階語言實現查詢演算法。2 熟練掌握順序表和有序表的順序查詢和二分查詢方法。3 掌握排序的不同方法，並能用高階語言實現排序演算法。4 熟練掌握順序表的選擇排序 氣泡排序和直接插入排序演算法的...
資料結構演算法排序總結
姓名 周燕學號 1204012032 班級 12計本 2 班 這個學期在老師的帶領下我們學習了資料結構與演算法這門課程。在本次資料結構與演算法的學習中最令我深刻的是關於幾種排序演算法的學習，所以在這裡我想對我本學期所學習的這幾種排序演算法做乙個比較詳細的總結。首先我們要對排序有乙個了解，排序是將乙個...