一，概述
許多將要討論到的算法直接適用于某些特殊的數據結構。對于大多數數據結構來說，都需要知道如何
插入一條新的數據
尋找某一條特定的數據項
刪除某一特定的數據項
1，數據結構的特征：
數據結構 優點 缺點
數組 插入快，如果有下標，可以非常快的存取 查找慢，刪除慢，大小固定
有序數組 比無序的數組查找快 刪除和插入慢，大小固定
棧 提供后進先出方式的存取 存取其他項很慢
隊列 提供先進先出方式的存取 存取其他項很慢
鏈表 插入快，刪除快 查找慢
二叉樹 查找，插入，刪除都快（如果樹保持平衡） 刪除算法復雜
紅-黑樹 查找，插入，刪除都快。數總是平衡的 算法復雜
2-3-4 樹 查找，插入，刪除都快。樹總是平衡的 算法復雜
類似的樹對磁盤存儲有用。
哈希表 如果關鍵字已知則存取極快。插入快 刪除慢，如果不知道關鍵字則存取很慢，對
存儲空間是用不充分。
堆 插入，刪除快，對最大數據項的存取很快 對其他數據項存取很慢
圖 對現實世界建模 有些算法慢且復雜
二 ，數組
數組是應用最廣泛的數據存儲結構。他被植入到大部分編成語言中，由于數組十分易懂，所以它被用來作為介紹數據結構的起步點，并展示面向對象編程的數據結構之間的相互關系。
使用二分法可以大大提高檢索速度，減少查詢次數。
二分法所需要的比較次數
范圍 次數
10 4
100 7
1000 10
10000 14
100000 17
1000000 20
10000000 24
100000000 27
1000000000 30
根據上面的二分法查詢次數，我們還可以推斷出來一個方程式：
r = 2*2....s;(s表示步數（次數），乘2的次數，即2的冪)， r表示范圍。
例如:如果是已知步數s,通過這個方程就可以得出范圍r,如: 如果s是6,則范圍應該是64;
同樣可以根據對數來計算其相應的次數.
大O表示法:
在計算機算法中,我們使用一種粗略的度量算法效率的方法稱作"大O"表示法.
在比較算法時似乎應該說一些類似"算法A比算法B快兩倍"之類的話，但實際上這些陳述并沒有多大意義。這是由于當數據項個數變化時，對應的比例也會發生根本改變。
用大O表示法表示運行時間
算法 大O表示法表示的運行時間
線性查找 O(N)
二分查找 O(logN)
無序數組的插入 O(1)
有序數組的插入 O(N)
無序數組的刪除 O(N)
有序數組的刪除 O(N)
上面的顯示了時間與數據項個數的大O關系。通過它我們可以比較不同的大O值（非常主觀）
：O(1)是優秀，O(logN)是良好， O(N) 還可以，O(N的平方)則差了一些。
三,簡單排序
一旦建立了一個重要的數據庫后,就可能根據某些需求對數據進行不同方式排序.比如對姓名按字母序排序,對學生按年級排序,對顧客按郵政編碼排序,對國內銷售品按價格排序,等.
對數據進行排序有可能是檢索的一個初始步驟.正如在第二章"數組"中看到的那樣,二分查找法比線性查找法要快的多,然而它只能應用于有序的數據.
冒泡排序
冒泡排序算法運行起來非常慢,但在概念上他是排序算法中最健的,因此冒泡排序算法在剛開始研究排序技術時是一個非常好的算法.
冒泡算法要遵循的規則(一組數按照從小到大的順序排序 從左到右)
1,比較兩個數.
2,如果左邊的值大,則兩個數交換位置(如果左邊的值不大那么不改變位置) .
3,向右移動一個位置,比較下面兩個數.
這樣一直比下去,一直比到最右端,那么最大的數就可以比較出來了.
冒泡排序的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上面的代碼中為了清晰起見,使用了一個獨立的swap()方法來執行交換操作,實際上使用一個獨立的swap()方法不一定好,因為方法調用會增加一些額外的消耗.最好還是將交換方法直接放到程序中,這樣可以提高一些速度.
通過上面的程序,我們可以看到,比較執行的次數
為: 9+8+7+6+5+4+3+2+1=45
公式為: N*(N-1)/2
因為兩個數值只有在需要時才交換,所以交換的次數少于比較的次數.如果數據是隨機的那么大概有一半數據需要交換.
冒泡排序運行需要時間可以認為：O(N平方)這個級別算法速度很慢。
選擇排序：
選擇排序改進了冒泡排序，將交換次數從O(N平方)減少到O(N),但是比較次數仍為 O(N平方).然而,選擇排序仍然為大記錄的排序提出一個非常重要的改進,因為這些大量的記錄需要在內存中移動,這就是交換的時間和比較時間相比起來,交換時間更為重要.(一般來說,在java語言中不是這種情況,java中只是改變引用位置,而實際對象的位置并沒有發生改變.)
選擇算法要遵循的規則(一組數按照從小到大的順序排序 從左到右)
1,從當前所有數中選擇一個最小的 ,放在第一位(換位),然后從第二個開始同樣選擇最小的.
開始向右移動,選擇對小的放在第二位,以此這樣操作。
就可以得到排序的效果。
選擇排序的程序代碼 ：
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
插入排序
在大多數情況下，插入排序是比上面兩種排序算法要好的一種，雖然算法仍然要O(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