java線性搜索,精確線性搜索方法

本文目錄一覽：

• 1、java線性查找演算法的平均次數為什麼是n/2
• 2、常見查找和排序演算法
• 3、java 線性查找和二分查找的區別
• 4、java中的散列碼

java線性查找演算法的平均次數為什麼是n/2

平均次數是(n+1)/2，不是n/2。

被查找的數是第1個數，則需用第1個數和被查找的數比較，要比較1次。

被查找的數是第2個數，則需用第1個數、第2個數和被查找的數比較，要比較2次。

…

被查找的數是第n個數，則需用第1個數、第2個數、…、第n個數和被查找的數比較，要比較n次。

平均次數為(1+2+…+n)/n=(n+1)/2。

常見查找和排序演算法

查找成功最多要n 次，平均（n+1）/2次， 時間複雜度為O(n) 。

優點：既適用順序表也適用單鏈表，同時對表中元素順序無要求，給插入帶來方便，只需插入表尾即可。

缺點：速度較慢。

改進：在表尾設置一個崗哨，這樣不用去循環判斷數組下標是否越界，因為最後必然成立。

適用條件：

二分查找的判定樹不僅是二叉排序樹，而且是一棵理想平衡樹。 時間複雜度為O(lbn) 。

循環實現

遞歸實現

待排序的元素需要實現 Java 的 Comparable 介面，該介面有 compareTo() 方法，可以用它來判斷兩個元素的大小關係。

從數組中選擇最小元素，將它與數組的第一個元素交換位置。再從數組剩下的元素中選擇出最小的元素，將它與數組的第二個元素交換位置。不斷進行這樣的操作，直到將整個數組排序。

選擇排序需要 ~N2/2 次比較和 ~N 次交換，==它的運行時間與輸入無關==，這個特點使得它對一個已經排序的數組也需要這麼多的比較和交換操作。

從左到右不斷 交換相鄰逆序的元素 ，在一輪的循環之後，可以讓未排序的最大元素上浮到右側。

在一輪循環中，如果沒有發生交換，那麼說明數組已經是有序的，此時可以直接退出。

每次都 將當前元素插入到左側已經排序的數組中 ，使得插入之後左側數組依然有序。

對於數組 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交換相鄰元素，令逆序數量減少 1，因此插入排序需要交換的次數為逆序數量。

==插入排序的時間複雜度取決於數組的初始順序，如果數組已經部分有序了，那麼逆序較少，需要的交換次數也就較少，時間複雜度較低==。

對於大規模的數組，插入排序很慢，因為它只能交換相鄰的元素，每次只能將逆序數量減少 1。希爾排序的出現就是為了解決插入排序的這種局限性，它通過交換不相鄰的元素，每次可以將逆序數量減少大於 1。

希爾排序使用插入排序對間隔 h 的序列進行排序。通過不斷減小 h，最後令 h=1，就可以使得整個數組是有序的。

希爾排序的運行時間達不到平方級別，使用遞增序列 1, 4, 13, 40, … 的希爾排序所需要的比較次數不會超過 N 的若干倍乘於遞增序列的長度。後面介紹的高級排序演算法只會比希爾排序快兩倍左右。

歸併排序的思想是將數組分成兩部分，分別進行排序，然後歸併起來。

歸併方法將數組中兩個已經排序的部分歸併成一個。

將一個大數組分成兩個小數組去求解。

因為每次都將問題對半分成兩個子問題，這種對半分的演算法複雜度一般為 O(NlogN)。

先歸併那些微型數組，然後成對歸併得到的微型數組。

取 a[l] 作為切分元素，然後從數組的左端向右掃描直到找到第一個大於等於它的元素，再從數組的右端向左掃描找到第一個小於它的元素，交換這兩個元素。不斷進行這個過程，就可以保證左指針 i 的左側元素都不大於切分元素，右指針 j 的右側元素都不小於切分元素。當兩個指針相遇時，將切分元素 a[l] 和 a[j] 交換位置。

快速排序是原地排序，不需要輔助數組，但是遞歸調用需要輔助棧。

快速排序最好的情況下是每次都正好將數組對半分，這樣遞歸調用次數才是最少的。這種情況下比較次數為 CN=2CN/2+N，複雜度為 O(NlogN)。

最壞的情況下，第一次從最小的元素切分，第二次從第二小的元素切分，如此這般。因此最壞的情況下需要比較 N2/2。為了防止數組最開始就是有序的，在進行快速排序時需要隨機打亂數組。

因為快速排序在小數組中也會遞歸調用自己，對於小數組，插入排序比快速排序的性能更好，因此在小數組中可以切換到插入排序。

最好的情況下是每次都能取數組的中位數作為切分元素，但是計算中位數的代價很高。一種折中方法是取 3 個元素，並將大小居中的元素作為切分元素。

對於有大量重複元素的數組，可以將數組切分為三部分，分別對應小於、等於和大於切分元素。

三向切分快速排序對於有大量重複元素的隨機數組可以在線性時間內完成排序。

快速排序的 partition() 方法，會返回一個整數 j 使得 a[l..j-1] 小於等於 a[j]，且 a[j+1..h] 大於等於 a[j]，此時 a[j] 就是數組的第 j 大元素。

可以利用這個特性找出數組的第 k 大的元素。

該演算法是線性級別的，假設每次能將數組二分，那麼比較的總次數為 (N+N/2+N/4+..)，直到找到第 k 個元素，這個和顯然小於 2N。

堆中某個節點的值總是大於等於其子節點的值，並且堆是一顆完全二叉樹。

堆可以用數組來表示，這是因為堆是完全二叉樹，而完全二叉樹很容易就存儲在數組中。位置 k 的節點的父節點位置為 k/2，而它的兩個子節點的位置分別為 2k 和 2k+1。這裡不使用數組索引為 0 的位置，是為了更清晰地描述節點的位置關係。

在堆中，當一個節點比父節點大，那麼需要交換這個兩個節點。交換後還可能比它新的父節點大，因此需要不斷地進行比較和交換操作，把這種操作稱為上浮。

類似地，當一個節點比子節點來得小，也需要不斷地向下進行比較和交換操作，把這種操作稱為下沉。一個節點如果有兩個子節點，應當與兩個子節點中最大那個節點進行交換。

將新元素放到數組末尾，然後上浮到合適的位置。

從數組頂端刪除最大的元素，並將數組的最後一個元素放到頂端，並讓這個元素下沉到合適的位置。

把最大元素和當前堆中數組的最後一個元素交換位置，並且不刪除它，那麼就可以得到一個從尾到頭的遞減序列，從正向來看就是一個遞增序列，這就是堆排序。

一個堆的高度為logN，因此在堆中插入元素和刪除最大元素的複雜度都為 logN。

對於堆排序，由於要對 N 個節點進行下沉操作，因此複雜度為 NlogN。

堆排序是一種原地排序，沒有利用額外的空間。

現代操作系統很少使用堆排序，因為它無法利用局部性原理進行緩存，也就是數組元素很少和相鄰的元素進行比較和交換。

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。作為一種線性時間複雜度的排序，==計數排序要求輸入的數據必須是有確定範圍的整數==。

當輸入的元素是 n 個 0 到 k 之間的整數時，它的==運行時間是 O(n + k)==。計數排序不是比較排序，排序的速度快於任何比較排序演算法。由於用來計數的數組C的長度取決於待排序數組中數據的範圍（等於待排序數組的最大值與最小值的差加上1），這使得計數排序對於數據範圍很大的數組，需要大量時間和內存。比較適合用來排序==小範圍非負整數數組的數組==。

桶排序是計數排序的升級版。它利用了函數的映射關係，高效與否的關鍵就在於這個映射函數的確定。為了使桶排序更加高效，我們需要做到這兩點：

同時，對於桶中元素的排序，選擇何種比較排序演算法對於性能的影響至關重要。

當輸入數據均勻分配到每一個桶時最快，當都分配到同一個桶時最慢。

實間複雜度N*K

快速排序是最快的通用排序演算法，它的內循環的指令很少，而且它還能利用緩存，因為它總是順序地訪問數據。它的運行時間近似為 ~cNlogN，這裡的 c 比其它線性對數級別的排序演算法都要小。

使用三向切分快速排序，實際應用中可能出現的某些分布的輸入能夠達到線性級別，而其它排序演算法仍然需要線性對數時間。

java 線性查找和二分查找的區別

一 線性查找

定義：在一列給定的值中進行搜索，從一端開始逐一檢查每個元素，直到找到所需元素的過程。

線性查找又稱為順序查找。如果查找池是某種類型的一個表，比如一個數組，簡單的查找方法是從表頭開始，一次將每一個值與目標元素進行比較。最後，或者查找到目標，或者達到表尾，而目標不存在於組中，這個方法稱為線性查找。

二 折半查找

定義：二分查找又稱折半查找，它是一種效率較高的查找方法。

【二分查找要求】：1.必須採用順序存儲結構 2.必須按關鍵字大小有序排列。

【優缺點】折半查找法的優點是比較次數少，查找速度快，平均性能好;其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。

【演算法思想】首先，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。

重複以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

【演算法複雜度】假設其數組長度為n，其演算法複雜度為o（log（n））

折半查找法也稱為二分查找法，它充分利用了元素間的次序關係，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如 果xa[n/2]，則我們只要在數組a的左半部繼續搜索x（這裡假設數組元素呈升序排列）。如果xa[n/2]，則我們只要在數組a的右 半部繼續搜索x。

java中的散列碼

首先，你要弄明白原因，你要明白兩點：

1、你得有一定的彙編功底，了解堆和棧關係。

2、你得明白，java對像類和封裝類在內存是怎麼存儲的。

1首先解答為什麼(a == b)－”不相等”

對像類和封裝類，在內存中這樣存儲的：

a.當new一個對像類時，就會在堆中開闢一塊空間，然後，會把這個空間的地指向你new 的這個句柄，這個句柄就會放在棧中，（棧）就像個列表，CPU會向棧發送指令進行操作。（棧像一本書的目錄，堆像書中的詳細章節）棧中存放的對像的具體物理地址。

== ：比的是棧中的東西，a棧的內容是c8（散列碼是不分正負的，內存表是1－－－11001000）

b棧的容易是c8（就是數字200的16進位，內存表是0－－－11001000）

因為（1－－－11001000）！＝（0－－－11001000）所以在堆中要分兩段存儲，比如堆地址為

00001000存放（1－－－11001000）為a，

堆地址為

00002000存放（0－－－11001000）為b,==比較的是00001000和00002000，所以不想等。

(String是比較特殊的對像，不是基本類型)

如果：String c = “abc”;

String d = “abc”;

它沒有new 在定義d = “abc”;的時候，因為堆中已經有”abc”了就直接把它的地址負給了d，所以

c和d的棧中存儲的都是”abc”在堆中二進位地址碼。所以不管是c==d還是c.equals(d)都是相等的。

equals:比較的是棧地址指向的堆中的內容是否想等。針對所有對像都有效。

比較的是（1－－－11001000）和（0－－－11001000）所表示的內容c8，所以想等。

這是有點不太好說清楚，不知道你明白了沒有。