線性查找，肯定是以線性的方式，在集合或數組中查找某個元素。本篇包括：
通過代碼來理解線性查找
什麼叫"線性"?還是在代碼中體會吧。
首先需要一個集合或數組，如何得到呢？就生成一個固定長度的隨機數組吧。然後輸入一個查找key，如果找到就返回元素的索引，沒找到就返回-1，就這麼簡單。
class Program{private static int[] arr;private static Random r = new Random();static void Main(string[] args){SeedData(10);ShowArray();Console.WriteLine("\n");Console.WriteLine("請輸入要查找的整型數");var temp = Convert.ToInt32(Console.ReadLine());Console.WriteLine("您要查找的{0}所在的位置是{1}", temp, LinearSearch(temp));Console.ReadKey();}//線性查找private static int LinearSearch(int key){for (int i = 0; i < arr.Length; i++){if (arr[i] == key) return i; //找到就返回索引}return -1;//如果沒找到就返回-1}//數組的種子數據private static void SeedData(int size){arr = new int[size];for (int i = 0; i < size; i++){arr[i] = r.Next(1, 100);}}//打印數組的所有元素private static void ShowArray(){foreach (var item in arr){Console.Write(item + " ");}}}
以上，我們自己可以定義什麼叫"線性查找"了。就是說，當我們輸入一個查找的key，是按順序依次查找集合中的每個元素(實際是通過循環遍歷)，如果找不到就返回一個值，比如-1，如果找到就返回該元素的索引位置。
時間復雜度
線性查找只是查找的一種最簡單的算法，還有其它相對復雜的算法。如何來衡量各種算法的效率呢，答案是用"時間復雜度"來衡量的。任何的概念來源於實踐，並不是憑空產生的，"時間復雜度"也一樣。
□ O(1)
假設一個數組中有10個元素，需要比較第一個元素是否等於第二個元素，算法只需要運行一次就可以得出結果。如果數組中有100個元素呢？算法還是運行一次就得到結果。於是，人們就想：算法的運行和數組大小沒有關系，就把這種算法叫做"常量運行時間"吧。但還不夠直觀，用什麼圖形表示呢？人們想出就用O(1)來表示吧。
O(1)雖然很直觀，但很容易產生歧義。有些人認為：只有算法運行一次，並且運行的次數不隨數組大小改變，就可以用O(1)表示了。這是很明顯的"望文生義"。O(1)更准確的解釋是：算法的運行次數是一個常量，不會隨著數組大小而改變。
□ O(n)
生活的精彩來自多樣性。假設一個數組中還是10個元素，需要比較第一個元素是否等於數組中任何其它元素，算法需要運行9次。如果數組中有100個元素呢，算法需要運行99次，也就是n-1次，算法運行的次數隨著n的不同而發生改變。人們把這種算法寫成O(n)，1可以忽略不計，讀成"n階"。
□ O(n²)
假設還有一種算法，需要比較數組中的任何元素於其它元素是否相等。第一個元素，需要和後面n-1個元素比較，第二個元素需要和除了第一個元素之外的其後面n-2個元素比較......也就是：(n-1) + (n-2) + ... + 2 + 1,這個公式用筆在紙上簡單推算一下，還可以提煉為n²/2-n/2，隨著n的增大，常量因子可以忽略，寫成O(n²),稱為"平方運行時間",讀成"n²階"。
當n是幾萬，O(n²)算法在今天每秒運行幾十億次的個人計算機上，不會有明顯的性能影響。但如果n變成幾百萬，就要求幾萬億次計算，這樣可能要幾個小時來執行。更有甚者，如果n變成幾十億，計算需要幾十年來完成。所以，每種算法都有它的適用范圍。
現在，可以稍微完整地定義"時間復雜度"了，它是一個函數，定量描述了算法的運行時間。時間復雜度是在最壞情況下的時間復雜度。
常見的時間復雜度有：
● O(1), 常數階，比如Hash表的查找
● O(log2n)，對數階，比如二分查找
● O(n)，線性階
● O(nlog2n)，線性對數階，比如快速排序的平均復雜度
● O(n^2)，平方階，比如冒泡排序
● O(n^3)，立方階，比如求最短路徑的Floyd算法
● O(n^k)，k次方階
● O(2^n)，指數階，比如漢諾塔
什麼是算法
是解決特定問題求解步驟的描述。在計算機中表現為指令的有限序列，並且每條指令表示一個或多個操作。
sum = 1 + 2 + 3 + ... + 100sum = 100 + 99 + 98+ ... + 12*sum = 101*100 = 10100sum = 5050
以上就是針對1到100求和的算法。對，是在18世紀，一個德國的小村莊，一個叫高斯的小孩想出來的，就這麼神奇！
冒泡排序是穩定的，算法時間復雜度是O(n ^2)。
2.2 選擇排序（Selection Sort）
選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將L[i..n]中最小者與L[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。
選擇排序是不穩定的，算法復雜度是O(n ^2 )。
2.3 插入排序 （Insertion Sort）
插入排序的基本思想是，經過i-1遍處理後,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，使得L[1..i] 又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤ L[i]，則L[1..i]已排好序，第i遍處理就結束了；否則交換L[i]與L[i-1]的位置，繼續比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時為止。圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。
直接插入排序是穩定的，算法時間復雜度是O(n ^2) 。
2.4 堆排序
堆排序是一種樹形選擇排序，在排序過程中，將A[n]看成是完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
堆排序是不穩定的，算法時間復雜度O(nlog n)。
2.5 歸並排序
設有兩個有序（升序）序列存儲在同一數組中相鄰的位置上，不妨設為A[l..m]，A[m+1..h]，將它們歸並為一個有序數列，並存儲在A[l..h]。
其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。
2.6 快速排序
快速排序是對冒泡排序的一種本質改進。它的基本思想是通過一趟掃描後，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。快速排序通過一趟掃描，就能確保某個數（以它為基准點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基准點的左右只有一個元素為止。
快速排序是不穩定的，最理想情況算法時間復雜度O(nlog2n)，最壞O(n ^2)。
2.7 希爾排序
在直接插入排序算法中，每次插入一個數，使有序序列只增加1個節點，並且對插入下一個數沒有提供任何幫助。如果比較相隔較遠距離（稱為 增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除多個元素交換。D.L.shell於1959年在以他名字命名的排序算法中實現了這一思想。算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。
希爾排序是不穩定的，其時間復雜度為O(n ^2)。
排序類別
時間復雜度
空間復雜度
穩定
1
插入排序
O(n2)
1
√
2
希爾排序
O(n2)
1
×
3
冒泡排序
O(n2)
1
√
4
選擇排序
O(n2)
1
×
5
快速排序
O(Nlogn)
O(logn)
×
6
堆排序
O(Nlogn)
1
×
7
歸並排序
O(Nlogn)
O(n)
√...余下全文>>
折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這裡假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的應用極其廣泛，而且它的思想易於理解，但是要寫一個正確的二分搜索算法也不是一件簡單的事。第一個二分搜索算法早在1946年就出現了，但是第一個完全正確的二分搜索算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索算法。問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體算法是很直觀的，我們可用C++描述如下：
template<class Type>
int BinarySearch(Type a[],const Type& x,int n)
{
int left=0;
int right=n-1;
while(left<=right){
int middle=(left+right)/2;
if (x==a[middle]) return middle;
if (x>a[middle]) left=middle+1;
else right=middle-1;
}
return -1;
}
模板函數BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜索數組的大小減少一半,因此整個算法在最壞情況下的時間復雜度為O(log n)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目了然。
選擇排序
基本思想是：每次選出第i小的記錄，放在第i個位置（i的起點是0，按此說法，第0小的記錄實際上就是最小的，有點別扭，不管這麼多了）。當i＝N－1時就排完了。
直接選擇排序
直選排序簡單的再現了選擇排序的基本思想，第一次尋找最小元素的代價是O(n)，如果不做某種特殊處理，每次都使用最簡單的尋找方法，自然的整個排序的時間復雜度就是O(n2)了。
冒泡法
為了在a[1]中得到最大值，我們將a[1]與它後面的元素a[2]，a[3]，...，a[10]進行比較。首先比較a[1]與a[2]，如果a[1]<a[2]，則將a[1]與a[2]交換，否則不交換。這樣在a[1]中得到的是a[1]與a[2]中的大數。然後將a[1]與a[3]比較，如果a[1]<a[3]，則將a[1]與a[3]交換，否則不交換。這樣在a[1]中得到的是a[1]，a[2]，a[3]中的最大值，...。如此繼續，最後a[1]與a[10]比較，如果a[1]<a[10]，則將a[1]與a[10]交換，否則不交換。這樣在a[1]中得到的數就是數組a的最大值（一共進行了9次比較）。
為了在a[2]中得到次大值，應將a[2]與它後面的元素a[3]，a[4]，...，a[10]進行比較。這樣經過8次比較，在a[2]是將得到次大值。
如此繼......余下全文>>
