一，概述
許多將要討論到的算法直接適用于某些特殊的數(shù)據(jù)結(jié)構(gòu)。對于大多數(shù)數(shù)據(jù)結(jié)構(gòu)來說，都需要知道如何
插入一條新的數(shù)據(jù)
尋找某一條特定的數(shù)據(jù)項(xiàng)
刪除某一特定的數(shù)據(jù)項(xiàng)
1，數(shù)據(jù)結(jié)構(gòu)的特征：
數(shù)據(jù)結(jié)構(gòu) 優(yōu)點(diǎn) 缺點(diǎn)
數(shù)組 插入快，如果有下標(biāo)，可以非?？斓拇嫒?nbsp; 查找慢，刪除慢，大小固定
有序數(shù)組 比無序的數(shù)組查找快 刪除和插入慢，大小固定
棧 提供后進(jìn)先出方式的存取 存取其他項(xiàng)很慢
隊(duì)列 提供先進(jìn)先出方式的存取 存取其他項(xiàng)很慢
鏈表 插入快，刪除快 查找慢
二叉樹 查找，插入，刪除都快（如果樹保持平衡） 刪除算法復(fù)雜
紅-黑樹 查找，插入，刪除都快。數(shù)總是平衡的 算法復(fù)雜
2-3-4 樹 查找，插入，刪除都快。樹總是平衡的 算法復(fù)雜
類似的樹對磁盤存儲(chǔ)有用。
哈希表 如果關(guān)鍵字已知?jiǎng)t存取極快。插入快 刪除慢，如果不知道關(guān)鍵字則存取很慢，對
存儲(chǔ)空間是用不充分。
堆 插入，刪除快，對最大數(shù)據(jù)項(xiàng)的存取很快 對其他數(shù)據(jù)項(xiàng)存取很慢
圖 對現(xiàn)實(shí)世界建模 有些算法慢且復(fù)雜
二 ，數(shù)組
數(shù)組是應(yīng)用最廣泛的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。他被植入到大部分編成語言中，由于數(shù)組十分易懂，所以它被用來作為介紹數(shù)據(jù)結(jié)構(gòu)的起步點(diǎn)，并展示面向?qū)ο缶幊痰臄?shù)據(jù)結(jié)構(gòu)之間的相互關(guān)系。
使用二分法可以大大提高檢索速度，減少查詢次數(shù)。
二分法所需要的比較次數(shù)
范圍 次數(shù)
10 4
100 7
1000 10
10000 14
100000 17
1000000 20
10000000 24
100000000 27
1000000000 30
根據(jù)上面的二分法查詢次數(shù)，我們還可以推斷出來一個(gè)方程式：
r = 2*2....s;(s表示步數(shù)（次數(shù)），乘2的次數(shù)，即2的冪)， r表示范圍。
例如:如果是已知步數(shù)s,通過這個(gè)方程就可以得出范圍r,如: 如果s是6,則范圍應(yīng)該是64;
同樣可以根據(jù)對數(shù)來計(jì)算其相應(yīng)的次數(shù).
大O表示法:
在計(jì)算機(jī)算法中,我們使用一種粗略的度量算法效率的方法稱作"大O"表示法.
在比較算法時(shí)似乎應(yīng)該說一些類似"算法A比算法B快兩倍"之類的話，但實(shí)際上這些陳述并沒有多大意義。這是由于當(dāng)數(shù)據(jù)項(xiàng)個(gè)數(shù)變化時(shí)，對應(yīng)的比例也會(huì)發(fā)生根本改變。
用大O表示法表示運(yùn)行時(shí)間
算法 大O表示法表示的運(yùn)行時(shí)間
線性查找 O(N)
二分查找 O(logN)
無序數(shù)組的插入 O(1)
有序數(shù)組的插入 O(N)
無序數(shù)組的刪除 O(N)
有序數(shù)組的刪除 O(N)
上面的顯示了時(shí)間與數(shù)據(jù)項(xiàng)個(gè)數(shù)的大O關(guān)系。通過它我們可以比較不同的大O值（非常主觀）
：O(1)是優(yōu)秀，O(logN)是良好， O(N) 還可以，O(N的平方)則差了一些。
三,簡單排序
一旦建立了一個(gè)重要的數(shù)據(jù)庫后,就可能根據(jù)某些需求對數(shù)據(jù)進(jìn)行不同方式排序.比如對姓名按字母序排序,對學(xué)生按年級排序,對顧客按郵政編碼排序,對國內(nèi)銷售品按價(jià)格排序,等.
對數(shù)據(jù)進(jìn)行排序有可能是檢索的一個(gè)初始步驟.正如在第二章"數(shù)組"中看到的那樣,二分查找法比線性查找法要快的多,然而它只能應(yīng)用于有序的數(shù)據(jù).
冒泡排序
冒泡排序算法運(yùn)行起來非常慢,但在概念上他是排序算法中最健的,因此冒泡排序算法在剛開始研究排序技術(shù)時(shí)是一個(gè)非常好的算法.
冒泡算法要遵循的規(guī)則(一組數(shù)按照從小到大的順序排序 從左到右)
1,比較兩個(gè)數(shù).
2,如果左邊的值大,則兩個(gè)數(shù)交換位置(如果左邊的值不大那么不改變位置) .
3,向右移動(dòng)一個(gè)位置,比較下面兩個(gè)數(shù).
這樣一直比下去,一直比到最右端,那么最大的數(shù)就可以比較出來了.
冒泡排序的java代碼:
package sort;
/** *//**
* 冒泡排序
* @author jason
*
*/
public class BubbleSort
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayBub arr; // reference to array
arr = new ArrayBub(maxSize); // create the array
arr.insert(77); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // display items
arr.bubbleSort(); // bubble sort them
arr.display(); // display them again
} // end main()
}
class ArrayBub {
private long[] a; // ref to array a
private int nElems; // number of data items
// --------------------------------------------------------------
public ArrayBub(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
// --------------------------------------------------------------
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
// --------------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
// --------------------------------------------------------------
public void bubbleSort()
{
int out, in;
for(out=nElems-1; out>1; out--) // outer loop (backward)
for(in=0; in<out; in++) // inner loop (forward)
if( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
} // end bubbleSort()
// --------------------------------------------------------------
private void swap(int one, int two)
{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
// --------------------------------------------------------------
} // end class ArrayBub上面的代碼中為了清晰起見,使用了一個(gè)獨(dú)立的swap()方法來執(zhí)行交換操作,實(shí)際上使用一個(gè)獨(dú)立的swap()方法不一定好,因?yàn)榉椒ㄕ{(diào)用會(huì)增加一些額外的消耗.最好還是將交換方法直接放到程序中,這樣可以提高一些速度.
通過上面的程序,我們可以看到,比較執(zhí)行的次數(shù)
為: 9+8+7+6+5+4+3+2+1=45
公式為: N*(N-1)/2
因?yàn)閮蓚€(gè)數(shù)值只有在需要時(shí)才交換,所以交換的次數(shù)少于比較的次數(shù).如果數(shù)據(jù)是隨機(jī)的那么大概有一半數(shù)據(jù)需要交換.
冒泡排序運(yùn)行需要時(shí)間可以認(rèn)為：O(N平方)這個(gè)級別算法速度很慢。
選擇排序：
選擇排序改進(jìn)了冒泡排序，將交換次數(shù)從O(N平方)減少到O(N),但是比較次數(shù)仍為 O(N平方).然而,選擇排序仍然為大記錄的排序提出一個(gè)非常重要的改進(jìn),因?yàn)檫@些大量的記錄需要在內(nèi)存中移動(dòng),這就是交換的時(shí)間和比較時(shí)間相比起來,交換時(shí)間更為重要.(一般來說,在java語言中不是這種情況,java中只是改變引用位置,而實(shí)際對象的位置并沒有發(fā)生改變.)
選擇算法要遵循的規(guī)則(一組數(shù)按照從小到大的順序排序 從左到右)
1,從當(dāng)前所有數(shù)中選擇一個(gè)最小的 ,放在第一位(換位),然后從第二個(gè)開始同樣選擇最小的.
開始向右移動(dòng),選擇對小的放在第二位,以此這樣操作。
就可以得到排序的效果。
選擇排序的程序代碼 ：
package sort;
/** *//**
* 選擇排序
* @author jason
*
*/
public class BubbleSort
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayBub arr; // reference to array
arr = new ArrayBub(maxSize); // create the array
arr.insert(77); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // display items
arr.bubbleSort(); // bubble sort them
arr.display(); // display them again
} // end main()
}
class ArrayBub {
private long[] a; // ref to array a
private int nElems; // number of data items
// --------------------------------------------------------------
public ArrayBub(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
// --------------------------------------------------------------
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
// --------------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
// --------------------------------------------------------------
public void bubbleSort()
{
int out, in;
for(out=nElems-1; out>1; out--) // outer loop (backward)
for(in=0; in<out; in++) // inner loop (forward)
if( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
} // end bubbleSort()
// --------------------------------------------------------------
private void swap(int one, int two)
{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
// --------------------------------------------------------------
} // end class ArrayBub
插入排序
在大多數(shù)情況下，插入排序是比上面兩種排序算法要好的一種，雖然算法仍然要O(N平方)的時(shí)間，但在一般情況下，它要比冒泡排序快一倍，比選擇排序還要快一點(diǎn)。盡管它比冒泡排序算法和選擇算法都更麻煩一些，但它也并不很復(fù)雜。他經(jīng)常被用在較復(fù)雜的排序算法的最后階段，例如快速排序。
插入算法原理：
插入算法要遵循的規(guī)則(一組數(shù)按照從小到大的順序排序 從左到右)
插入排序，從第一位開始，如果第二位小于第一位，那么第一位和第二位換位，第一位與第二位有正確的順序，
這時(shí)排序好的第二位與第三位比較，如果第三位小于第二位，那么拿出第三位的值，并且把第二位移到第三位上，
然后比較這個(gè)臨時(shí)值（原來的第三位）與第一位比較，如果第一位也大于第三位,那么同樣,第一位移到原來第二位的位置
這個(gè)臨時(shí)值就占據(jù)了第一位,如果一位的值小于臨時(shí)值(原來的第三位),則第一位不變,第二位為臨時(shí)值,以此類推
就是插入算法的原理.
插入算法就是對一個(gè)有序的序列,進(jìn)行插入操作.
插入排序代碼:
package sort;
/** *//**
*
* @author jason
*
*/
class ArrayIns
{
private long[] a; // ref to array a
private int nElems; // number of data items
//--------------------------------------------------------------
public ArrayIns(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
//--------------------------------------------------------------
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
//--------------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
//--------------------------------------------------------------
public void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++) // out is dividing line
{
long temp = a[out]; // remove marked item
in = out; // start shifts at out
while(in>0 && a[in-1] >= temp) // until one is smaller,
{
a[in] = a[in-1]; // shift item to right
--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
} // end insertionSort()
//--------------------------------------------------------------
} // end class ArrayIns
////////////////////////////////////////////////////////////////
class InsertSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array
arr.insert(77); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // display items
arr.insertionSort(); // insertion-sort them
arr.display(); // display them again
} // end main()
} // end class InsertSortApp