選擇操作的實現演算法有

A. 數據結構中有哪些基本演算法

數據結構中最基本的演算法有：查找、排序、快速排序，堆排序，歸並排序，，二分搜索演算法
等等。

1、用的最多也是最簡單的數據結構是線性表。

2、有前途的又難數據結構是圖 。

3、常用的80％演算法是排序和查找。

B. 資料庫系統原理的作品目錄

第1篇基礎篇
第1章資料庫系統概述
1.1資料庫、資料庫管理系統和資料庫系統
1.2資料庫系統的特點與功能
1.2.1信息完整、功能通用
1.2.2程序與數據獨立
1.2.3數據抽象
1.2.4支持數據的不同視圖
1.2.5控制數據冗餘
1.2.6支持數據共享
1.2.7限制非授權的存取
1.2.8提供多種用戶界面
1.2.9表示數據之間的復雜聯系
1.2.10完整性約束
1.2.11數據恢復
1.3資料庫系統的用戶
1.3.1資料庫管理員
1.3.2資料庫設計者
1.3.3最終用戶
1.3.4系統分析員和應用程序員
1.3.5與資料庫系統有關的其他人員
1.4數據抽象
1.4.1數據抽象與資料庫的三種模式
1.4.2數據獨立性
1.5數據模型
1.5.1基於對象的數據模型
1.5.2基於記錄的數據模型
1.5.3物理數據模型
1.5.4資料庫模式和資料庫實例
1.6資料庫語言
1.7資料庫管理系統的結構
1.8資料庫技術的發展
1.8.1第一代資料庫系統
1.8.2第二代資料庫系統
1.8.3第三代資料庫系統
1.8.4Internet時代的資料庫技術
習題1
本章參考文獻
第2章關系資料庫系統
2.1關系數據模型
2.1.1數據結構
2.1.2完整性約束規則
2.2關系運算
2.2.1關系代數
2.2.2元組關系演算
2.2.3域關系演算
2.3關系運算的安全性
2.4關系代數、元組關系演算、域關系演算的等價性
2.5關系資料庫查詢語言
2.5.1ISBL語言
2.5.2QUEL語言
2.5.3QBE語言
2.6標准關系資料庫查詢語言SQL
2.6.1數據定義
2.6.2數據查詢
2.6.3數據更新
2.6.4視圖定義
2.6.5安全性機制
2.6.6嵌入式SQL語言
習題2
本章參考文獻
第3章資料庫的安全性與完整性
3.1安全性
3.1.1資料庫安全性與資料庫管理員
3.1.2系統保護機制
3.1.3授權機制
3.1.4統計資料庫的安全性
3.1.5資料庫加密技術
3.1.6資料庫操作跟蹤審計
3.2完整性
3.2.1完整性約束的類型
3.2.2顯式約束的定義
3.2.3完整性約束的驗證
習題3
本章參考文獻
第2篇設計篇
第4章資料庫設計概述與需求分析
4.1資料庫的設計概述
4.1.1資料庫的設計問題
4.1.2資料庫的生命周期
4.1.3資料庫的設計過程
4.2需求分析
4.2.1應用領域的調查分析
4.2.2定義資料庫系統支持的信息與應用
4.2.3定義資料庫操作任務
4.2.4定義數據項
4.2.5預測現行系統的未來改變
習題4
本章參考文獻
第5章概念資料庫設計
5.1概述
5.2實體聯系模型
5.2.1實體和屬性
5.2.2實體型、鍵屬性和屬性的值域
5.2.3資料庫實例
5.2.4實體間的聯系
5.2.5弱實體
5.2.6實體聯系圖
5.3擴展的實體聯系模型
5.3.1子類、超類、演繹和歸納
5.3.2演繹和歸納的性質
5.3.3范疇與范疇化
5.3.4EER圖
5.4概念設計的方法與策略
5.4.1概念設計的方法
5.4.2概念設計的策略
5.5視圖綜合設計方法
5.5.1局部概念模式設計
5.5.2全局概念模式合成
5.6事務的設計
習題5
本章參考文獻
第6章邏輯資料庫設計
6.1形成初始關系資料庫模式
6.2關系資料庫設計理論
6.2.1問題的提出
6.2.2函數依賴
6.2.3數據依賴的公理系統
6.2.4關系模式的規范形式
6.2.5多值依賴與第四範式
6.2.6連接依賴與第五範式
6.3關系模式規范化方法
6.3.1無損連接性和函數依賴保持性
6.3.2關系模式分解演算法
6.4關系模式的優化
6.5完整性和安全性約束的定義
6.6邏輯資料庫的性能估計
習題6
本章參考文獻
第7章物理資料庫設計
7.1影響物理資料庫設計的因素分析
7.2為關系模式選擇存取方法
7.2.1索引存取方法的選擇
7.2.2Hash存取方法的選擇
7.2.3聚集存取方法的選擇
7.3物理存儲結構的設計
習題7
本章參考文獻
第3篇實現篇
第8章物理存儲結構
8.1資料庫存儲設備
8.1.1磁碟存儲器
8.1.2磁碟緩沖處理技術
8.1.3磁碟的調度策略
8.1.4磁碟容錯技術
8.1.5第三級存儲器
8.2文件和文件記錄
8.3無序文件
8.4有序文件
8.5Hash文件
8.5.1簡單Hash方法
8.5.2動態Hash方法
8.5.3可擴展的Hash方法
8.6索引文件
8.6.1主索引
8.6.2聚集索引
8.6.3輔助索引
8.6.4多級索引
8.7B樹與B+樹索引結構
8.7.1索引樹結構
8.7.2B樹索引結構
8.7.3B+樹索引結構
8.8多維索引
8.8.1柵格文件
8.8.2KD樹
8.8.3R樹
8.8.4點陣圖索引
習題8
本章參考文獻
第9章資料庫管理系統的數據字典
9.1關系資料庫管理系統的數據字典
9.2資料庫管理系統軟體模塊對數據字典的存取
習題9
第10章關系代數操作的實現演算法
10.1查詢處理的過程
10.2選擇操作的實現演算法
10.3笛卡兒積的實現演算法
10.4連接操作的實現演算法
10.5投影操作的實現演算法
10.6集合的並、交、差的實現演算法
習題10
本章參考文獻
第11章查詢優化技術
11.1問題的提出
11.2啟發式關系代數優化方法
11.2.1關系代數等價變換規律
11.2.2啟發式代數優化規則
11.2.3啟發式代數優化演算法
11.3啟發式關系演算優化方法
11.3.1多重自然連接的優化處理
11.3.2查詢的超圖表示
11.3.3超圖消解演算法
11.4基於復雜性估計的查詢優化方法
11.5語義查詢優化方法
11.6查詢優化的遺傳演算法
習題11
本章參考文獻
第12章事務處理技術之一：並發控制技術
12.1並發控制概述
12.1.1單用戶和多用戶資料庫系統
12.1.2並發控制的必要性
12.2事務模型
12.2.1事務中的讀寫操作
12.2.2事務的原子性
12.2.3事務的狀態
12.2.4事務的性質
12.3事務調度與可串列性
12.3.1事務的調度
12.3.2調度的可串列性
12.3.3調度的可串列性測試
12.4基於鎖的並發控制協議
12.4.1鎖的概念
12.4.2兩段鎖協議
12.4.3資料庫圖協議
12.5時間印協議
12.6其他並發控制技術
12.6.1實現並發控制的驗證技術
12.6.2多版本並發控制技術
12.6.3多種並發控制的粒度
12.7插入和刪除操作
12.7.1刪除操作對並發控制的影響
12.7.2插入操作對並發控制的影響
12.7.3插入元組現象
習題12
本章參考文獻
第13章事務處理技術之二：資料庫恢復技術
13.1資料庫恢復的必要性
13.2使用日誌的資料庫恢復技術
13.2.1資料庫系統日誌
13.2.2推遲更新技術
13.2.3即時更新技術
13.3緩沖技術
13.3.1日誌緩沖技術
13.3.2資料庫緩沖技術
13.4檢測點
13.5影子頁面技術
13.6永久存儲器中信息丟失後的資料庫恢復
13.7資料庫恢復與並發控制技術的結合
13.7.1事務的嵌套撤銷
13.7.2調度的可恢復性
習題13
本章參考文獻
第14章其他事務處理技術
14.1死鎖處理
14.1.1預防死鎖協議
14.1.2死鎖的檢測和恢復技術
14.2高性能事務處理系統
14.2.1主存資料庫
14.2.2事務的成批提交技術
14.3長事務處理技術
14.3.1可串列性概念不適於長事務處理
14.3.2嵌套事務技術
14.3.3補救事務技術
14.3.4實時資料庫系統
習題14
本章參考文獻
第4篇專題篇
第15章新一代資料庫系統及應用
15.1新一代資料庫應用
15.1.1工程設計與製造
15.1.2辦公自動化系統
15.1.3決策支持系統
15.1.4科學與統計數據管理
15.1.5異構多資料庫應用
15.1.6人工智慧應用
15.1.7其他的新一代資料庫應用
15.2新一代資料庫系統的特點和熱點問題
15.3新一代資料庫系統
習題15
本章參考文獻
第16章擴展的關系資料庫系統
16.1基於邏輯的關系資料庫系統
16.1.1邏輯數據模型
16.1.2查詢的計算策略
16.1.3查詢結構
16.1.4否定
16.1.5非遞歸查詢
16.1.6遞歸查詢
16.2基於嵌套關系模型的關系資料庫系統
16.2.1文檔檢索實例
16.2.2嵌套關系模式的定義
16，2.3嵌套關系查詢語言
16.3專家資料庫系統
習題16
本章參考文獻
第17章面向對象與對象關系資料庫系統
17.1面向對象程序設計方法
17.2面向對象數據模型
17.2.1對象的結構
17.2.2類和類層次
17.2.3多重繼承性
17.2.4對象的標識
17.2.5對象的嵌套
17.3面向對象資料庫的物理組織
17.4面向對象資料庫的查詢
17.5面向對象資料庫模式的修改
習題17
本章參考文獻
第18章分布式資料庫系統
18.1概述
18.1.1計算機網路
18.1.2分布式資料庫和分布式資料庫系統
18.1.3分布式資料庫的結構
18.2分布式資料庫設計
18.2.1數據的重復存儲
18.2.2數據的分片存儲
18.2.3數據的組合存儲
18.2.4命名和局部自治性
18.3分布式資料庫查詢處理
18.3.1分布式資料庫管理系統概述
18.3.2分布式查詢處理
18.4分布式資料庫系統中的事務處理
18.4.1分布式事務處理器的結構
18.4.2分布式系統恢復技術
18.4.3分布式並發控制技術
18.4.4分布式死鎖處理技術
習題18
本章參考文獻
第19章並行資料庫技術
19.1支持並行資料庫的並行結構
19.2關系資料庫系統的固有並行性
19.3實現關系查詢並行化的數據流圖方法
19.4並行資料庫的物理組織
19.4.1一維數據劃分方法
19.4.2多維數據劃分方法
19.4.3傳統物理存儲結構的並行化
19.5新的並行數據操作演算法
19，5.1基於嵌套循環的並行連接演算法
19.5.2基於Sort-Merge的並行連接演算法
19.5.3基於Hash的並行連接演算法
19.5.4數據分布的均勻性與並行連接演算法
19.5.5數據的初始劃分與並行連接演算法
19.6查詢優化技術
19.6.1基於左線性樹的查詢優化演算法
19.6.2基於右線性樹的查詢優化演算法
19.6.3基於片段式右線性樹的查詢優化演算法
19.6.4基於濃密樹的查詢優化演算法
19.6.5基於操作森林的查詢優化演算法
習題19
本章參考文獻
第5篇新技術篇
第20章資料庫技術的研究進展
20.1影響資料庫技術發展的因素
20.2近10年出現的資料庫新技術和新問題
本章參考文獻
第21章數據倉庫與聯機分析處理技術
21.1什麼是數據倉庫
21.2數據倉庫系統的結構
21.3數據倉庫的多維數據模型
21.3.1多維數據集合
21.3.2多維數據集合的關系表示方法
21.3.3多維數據集合上的操作
21.4數據倉庫系統的實現技術
2l，4.1數據倉庫的存儲方法
21.4.2數據倉庫的索引技術
21.4.3數據操作演算法
21.4.4查詢處理技術
21.5數據倉庫工具
21.6數據倉庫設計
本章參考文獻
第22章數據挖掘技術
22.1數據挖掘的基本概念
22.2關聯規則挖掘方法
22.3分類方法
22.4聚類方法
22.5相似性搜索技術
22.6Web挖掘技術
本章參考文獻
第23章Web信息檢索與Web數據管理技術
23.1Web信息檢索技術
23.1.1搜索引擎技術
23.1.2分類技術
23.1.3元搜索
本節參考文獻
23.2Web數據集成技術
23.2.1數據集成的演變
23.2.2傳統的多資料庫系統技術
23.2.3Web數據集成方法
本節參考文獻
23.3XML資料庫技術
本節參考文獻
第24章其他資料庫新技術
24.1多媒體資料庫技術
本節參考文獻
24.2時態資料庫技術
本節參考文獻
24.3空間資料庫技術
本節參考文獻
24.4移動資料庫技術
本節參考文獻
24.5主動資料庫系統
本節參考文獻
24.6數據流技術
本節參考文獻
……

C. 軟體編程經常用的演算法都有哪些

排序演算法 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為：
計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。
記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。
一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。
當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。
排列演算法列表
在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）
不實用的排序演算法
Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體
排序的演算法
排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。
插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的：
首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。
從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重復2號步驟，直至原數列為空。
插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
冒泡排序
冒泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重復2號步驟，直至再也不能交換。
冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設數組內存放了n個待排數字，數組下標從1開始，到n結束。
i=1
從數組的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間復雜度也是O(n²)的。
快速排序
現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。
堆排序
堆排序與前面的演算法都不同，它是這樣的：
首先新建一個空列表，作用與插入排序中的"有序列表"相同。
找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重復2號步驟，直至原數列為空。
堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。
看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。
平均時間復雜度
插入排序 O(n2)
冒泡排序 O(n2)
選擇排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
歸並排序 O(n log n)
基數排序 O(n)
希爾排序 O(n1.25)
冒泡排序
654
比如說這個，我想讓它從小到大排序，怎麼做呢？
第一步：6跟5比，發現比它大，則交換。564
第二步：5跟4比，發現比它大，則交換。465
第三步：6跟5比，發現比它大，則交換。456

D. 鏈表選擇排序的C語言演算法實現

common.h
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
linklist.h
#include common.h
typedef int ElemType;
typedef struct Node /*結點類型定義*/
{
ElemType data;
struct Node * next;
}Node, *LinkList; /* LinkList為結構指針類型*/
void CreateFromTail(LinkList L)
{
Node *r, *s;
char c;
int flag =1; /*設置一個標志，初值為1，當輸入$時，flag為0，建表結束*/
r=L; /*r指針動態指向鏈表的當前表尾，以便於做尾插入，其初值指向頭結點*/
while(flag) /*循環輸入表中元素值，將建立新結點s插入表尾*/
{
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL; /*將最後一個結點的next鏈域置為空，表示鏈表的結束*/
}
}
} 尾插法創建鏈表程序
/*_*====尾插法創建鏈表，返回鏈表頭指針====*_*/
LinkList CreateFromTail2()
{
LinkList L;
Node *r, *s;
int c;
int flag =1;
L=(Node * )malloc(sizeof(Node));
L->next=NULL;
r=L;
while(flag)
{
scanf(%d,&c);
if(c!=-1)
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL;
}
}
return L;
} void linkSort(LinkList l)
{
Node *p,*q,*m,*n;
Node *temp1,*temp2;
if(l->next==NULL)
printf(NO LINKLIST!!!);
else
{
p=l;q=l->next;
while(q->next!=NULL)
{
m=p->next;
n=q->next;
temp1=m;
while(temp1->next!=NULL)
{
if(temp1->next->data<q->data && temp1->next->data<n->data)
{
m=temp1;n=temp1->next;
}
temp1=temp1->next;
}/*_*====此循環用於找到基準(q)以後的序列的最小的節點=====*_*/
if(m!=p->next || (m==p->next && m->data>n->data))
{
p->next=n;
p=n;
m->next=q;
m=q;
q=q->next;
n=n->next;
p->next=q;
m->next=n;
}/*_*======此條件用於交換兩個節點*_*/
else
{
p=p->next;
q=q->next;
}/*_*======此條件用於沒有找到最小值時的p，q後移操作*_*/
}/*_*=====外循環用於從前往後掃描，通過移動p,q指針實現=======*_*/
temp2=l->next;
printf(List after sorting is: );
while(temp2!=NULL)
{
printf(%5d,temp2->data);
temp2=temp2->next;
}
}
printf( );
} void main()
{
Node *temp3;
LinkList l;
printf( =====(end by -1)====== press enter after input the nember each time: );
l=CreateFromTail2();
temp3=l->next;
if(temp3==NULL)
printf(NO LINKLIST!!!);
else
{
printf(List before sorting is: );
while(temp3!=NULL)
{
printf(%5d,temp3->data);
temp3=temp3->next;
}
}
printf( );
linkSort(l);
}

E. 什麼叫演算法演算法有哪幾種表示方法

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。計算機科學家往往將「演算法」一詞的含義限定為此類「符號演算法」。「演算法」概念的初步定義：一個演算法是解決一個問題的進程。而並不需要每次都發明一個解決方案。

已知的演算法有很多，例如「分治法」、「枚舉測試法」、「貪心演算法」、「隨機演算法」等。

(5)選擇操作的實現演算法有擴展閱讀

演算法中的「分治法」

「分治法」是把一個復雜的問題拆分成兩個較為簡單的子問題，進而兩個子問題又可以分別拆分成另外兩個更簡單的子問題，以此類推。問題不斷被層層拆解。然後，子問題的解被逐層整合，構成了原問題的解。

高德納曾用過一個郵局分發信件的例子對「分治法」進行了解釋：信件根據不同城市區域被分進不同的袋子里；每個郵遞員負責投遞一個區域的信件，對應每棟樓，將自己負責的信件分裝進更小的袋子；每個大樓管理員再將小袋子里的信件分發給對應的公寓。

F. 數據結構有哪些基本演算法

數據結構是一門研究非數值計算的程序設計問題中的操作對象，以及它們之間的關系和操作等相關問題的學科。

可以理解為：程序設計 = 數據結構 + 演算法

數據結構演算法具有五個基本特徵：輸入、輸出、有窮性、確定性和可行性。

1、輸入：一個演算法具有零個或者多個輸出。以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定出了初始條件。後面一句話翻譯過來就是，如果一個演算法本身給出了初始條件，那麼可以沒有輸出。比如，列印一句話：NSLog(@"你最牛逼！");

2、輸出：演算法至少有一個輸出。也就是說，演算法一定要有輸出。輸出的形式可以是列印，也可以使返回一個值或者多個值等。也可以是顯示某些提示。

3、有窮性：演算法的執行步驟是有限的，演算法的執行時間也是有限的。

4、確定性：演算法的每個步驟都有確定的含義，不會出現二義性。

5、可行性：演算法是可用的，也就是能夠解決當前問題。

數據結果的基本演算法有：

1、圖搜索（廣度優先、深度優先）深度優先特別重要

2、排序

3、動態規劃

4、匹配演算法和網路流演算法

5、正則表達式和字元串匹配

6、三路劃分-快速排序

7、合並排序（更具擴展性，復雜度類似快速排序）

8、DF/BF 搜索 （要知道使用場景）

9、Prim / Kruskal （最小生成樹）

10、Dijkstra （最短路徑演算法）

11、選擇演算法

G. 操作系統的主要演算法都有哪些

一、進程(作業)調度演算法
l 先來先服務調度演算法（FCFS）：每次調度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執行。該進程一旦佔有了處理器，它就一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。特點：利於長進程，而不利於短進程。

l 短進程（作業）優先調度演算法(SPF)：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之佔有處理器並執行，直到該進程完成或因發生事件而阻塞，然後退出處理器，再重新調度。

l 時間片輪轉調度演算法 ：系統將所有的就緒進程按進入就緒隊列的先後次序排列。每次調度時把CPU分配給隊首進程，讓其執行一個時間片，當時間片用完，由計時器發出時鍾中斷，調度程序則暫停該進程的執行，使其退出處理器，並將它送到就緒隊列的末尾，等待下一輪調度執行。

l 優先數調度演算法 ：它是從就緒隊列中選擇一個優先權最高的進程，讓其獲得處理器並執行。

l 響應比高者優先調度演算法：它是從就緒隊列中選擇一個響應比最高的進程，讓其獲得處理器執行，直到該進程完成或因等待事件而退出處理器為止。特點：既照顧了短進程，又考慮了進程到達的先後次序，也不會使長進程長期得不到服務，因此是一個比較全面考慮的演算法，但每次進行調度時，都需要對各個進程計算響應比。所以系統開銷很大，比較復雜。

l 多級隊列調度演算法

基本概念：

作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)

作業平均周轉時間(T)＝周轉時間/作業個數

作業帶權周轉時間（Wi）＝周轉時間/運行時間

響應比＝（等待時間＋運行時間）/運行時間

二、存儲器連續分配方式中分區分配演算法
n 首次適應分配演算法（FF）：對空閑分區表記錄的要求是按地址遞增的順序排列的，每次分配時，總是從第1條記錄開始順序查找空閑分區表，找到第一個能滿足作業長度要求的空閑區，分割這個空閑區，一部分分配給作業，另一部分仍為空閑區。

n 循環首次適應演算法：每次分配均從上次分配的位置之後開始查找。

n 最佳適應分配演算法(BF)：是按作業要求從所有的空閑分區中挑選一個能滿足作業要求的最小空閑區，這樣可保證不去分割一個更大的區域，使裝入大作業時比較容易得到滿足。為實現這種演算法，把空閑區按長度遞增次序登記在空閑區表中，分配時，順序查找。

三、頁面置換演算法
l 最佳置換演算法（OPT) ：選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。

l 先進先出置換演算法（FIFO）：選擇最先進入內存的頁面予以淘汰。

l 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。

l 最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。

四、磁碟調度
n 先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置

n 最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題

n 掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。

n 循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。

H. 資料庫中select語句的具體實現演算法

select *
from student,sc
where student.sno=sc.sno(這個就是表屬性連接)

I. 進化演算法的框架

進化演算法是以達爾文的進化論思想為基礎，通過模擬生物進化過程與機制的求解問題的自組織、自適應的人工智慧技術。生物進化是通過繁殖、變異、競爭和選擇實現的；而進化演算法則主要通過選擇、重組和變異這三種操作實現優化問題的求解。如圖1： 1、t=0
2、初始化群體p(0)
3、評估初始化群體p(0)
4、while終止條件不滿足do
5、 重組操作：p(t)=r(p(t))
6、 變異操作：p(t)=m(p(t))
7、 評估操作：p(t)
8、 選擇操作：p(t+1)=s(p(t)UQ)
9、 t=t+1
10、end 圖1：進化演算法基本框架
其中r、m、s分別表示重組運算元、變異運算元、選擇運算元。

J. 十大經典排序演算法 C 語言實現[上]冒泡選擇插入希爾歸並

期中已到，期末將至。《演算法設計與分析》的「預習」階段藉此開始~。在眾多的演算法思想中，如果你沒有扎實的數據結構的功底，不知道棧與隊列，哈希表與二叉樹，不妨可以從排序演算法開始練手。縱觀各類排序演算法，常見的、經典的排序演算法將由此篇引出。

排序演算法的輸出必須遵守的下列兩個原則：

十大經典的排序演算法及其時間復雜度和穩定性如上表所示。判斷一個排序演算法是否穩定是看在相等的兩個數據排序演算法執行完成後是否會前後關系顛倒，如若顛倒，則稱該排序演算法為不穩定，例如選擇排序和快速排序。

接下來十個經典排序演算法的詳細探討缺少不了交換兩個整數值的掌握，這里回顧一下其中三種方交換法：用臨時變數交換兩個整數的值(SwapTwo_1)、不用第三方變數交換兩個整數的值(SwapTwo_2)、使用位運算交換兩個整數的值(SwapTwo_3)。其中用臨時變數交換兩個整數的值效率最高，後倆者只適用於內置整型數據類型的交換，並不高效。

先不說公司面試筆試，大學實驗室的納新題里最常有的就是冒泡排序。冒泡排序重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。由於它的簡潔，冒泡排序通常被用來對於程序設計入門的學生介紹演算法的概念。

[圖片上傳失敗...(image-93185f-1513765803581)]]( http://upload-images.jianshu.io/upload_images/2558748-990f8de3fbdbb50d.gif?imageMogr2/auto-orient/strip )

上圖可見，冒泡排序演算法的運作如下：

通俗來講，整個冒泡排序就是通過兩次循環，外層循環將此輪最大(小)值固定到此輪尾部，內層循環「冒泡」比較相鄰的兩個元素並決定是否交換位置。

從上圖也可理解冒泡排序如何將每一輪最大（小）值固定到此輪尾部：尾部總為有序狀態，前面無序狀態區根據大小規則冒泡向後方傳遞最值。

選擇排序首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。

上圖左下角和右上角可以分別看做排序序列起始位置(已排序區)和排序序列末尾(未排序區)，左下角一直穩定更新，但選擇排序不穩定，即排序後曾經相同的兩個元素的前後位置關系可能會發生顛倒。

插入排序的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用 in-place
排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間。

一般來說，插入排序都採用 in-place 在數組上實現。具體演算法描述如下：

如果比較操作的代價比交換操作大的話，可以採用二分查找法來減少比較操作的數目。該演算法可以認為是插入排序的一個變種，稱為二分查找插入排序。這里先不做涉及。

希爾排序按其設計者希爾（Donald Shell）的名字命名，該演算法由1959年公布。希爾排序也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後演算法再取越來越小的步長進行排序，演算法的最後一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。

步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。演算法最開始以一定的步長進行排序。然後會繼續以一定步長進行排序，最終演算法以步長為1進行排序。當步長為1時，演算法變為插入排序，這就保證了數據一定會被排序。

已知的最好步長序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,...)，這項研究也表明「比較在希爾排序中是最主要的操作，而不是交換。」用這樣步長序列的希爾排序比插入排序要快，甚至在小數組中比快速排序和堆排序還快，但是在涉及大量數據時希爾排序還是比快速排序慢。

歸並排序是創建在歸並操作上的一種有效的排序演算法，效率為 O(n log n)。1945年由約翰·馮·諾伊曼首次提出。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。

歸並操作（merge），也叫歸並演算法，指的是將兩個已經排序的序列合並成一個序列的操作。歸並排序演算法依賴歸並操作。

歸並排序用迭代法和遞歸法都可以實現，迭代法的演算法步驟為：

遞歸法的演算法步驟為：

這篇文章「十大經典排序演算法及其 C 語言實現【上】」引出了十大經典演算法的前五個並用 C 語言實踐：冒泡排序、選擇排序、插入排序、希爾排序和歸並排序，並作出了充足的圖文解釋。即將推出的「十大經典排序演算法及其 C 語言實現【下】」將對剩下五個經典演算法快速排序、堆排序、計數排序、桶排序、基數排序作出完善，盡請期待~。