一、冒泡排序
這種排序方式是最容易理解的，主體思想就是：
指針重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。
冒泡排序一次只比較兩個(gè)數(shù)字，并且這兩個(gè)數(shù)字是相鄰的。
從圖上我們可以看到，原數(shù)組為【30，8，15，18，12】。
第一次比較首先比較第0位和第一位，并且將結(jié)果大的數(shù)字往后移動(dòng)，也就是交換。第0位是40， 第1 位是8，40>8，所以我們將大的數(shù)字往后移動(dòng)。
同理，如果第0位<第1 位，我們就不進(jìn)行交換。
之后我們?cè)诒容^第1位和第2位的數(shù)字。將結(jié)果大的往后移動(dòng)。
就這樣，通過(guò)n-1次比較后（n為數(shù)組長(zhǎng)度），我們就將最大的數(shù)字移到了數(shù)組的最末端。
然后再繼續(xù)進(jìn)行第二輪比較，找出第二大的數(shù)字，往后以此類推。
一共需要比較的次數(shù)為： (n-1)+(n-2)+(n-3)+·····+1；
以java代碼方式實(shí)現(xiàn)：
public void bubblesort(int arrayVal[],int length) {
????? int i, j;
????? int temp;
????? for (i =0; i < length -1; i++) {
????? for (j = i +1; j < length; j++) {
??????????? if (arrayVal[i] > arrayVal[j]) {
?????????????????? //置換位置
? ? ? ? ? ? ? ??? temp = arrayVal[i];
????????????????? arrayVal[i] = arrayVal[j];
????????????????? arrayVal[j] = temp;
??????????????????? }
??????? ?? }
? ?? }
}
二、選擇排序
選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。
選擇排序就是對(duì)數(shù)組中的元素進(jìn)行比較選擇，然后直接放置在排序后的位置。
首先指針K先指向數(shù)組0號(hào)位置，K相當(dāng)于指明一個(gè)目標(biāo)位置。然后另一個(gè)指針min從K開(kāi)始，往后一次比較，找到最小的值，并存儲(chǔ)在min中，比較了一輪后，min中存儲(chǔ)的數(shù)就是整個(gè)數(shù)組中最小的數(shù)字。這是直接將min中的數(shù)字和K指向的數(shù)字交換即可。然后找到數(shù)組中第二小的數(shù)，讓他跟數(shù)組中第二個(gè)元素交換一下值，以此類推。
JAVA代碼實(shí)現(xiàn)：
public void selectionsort(int arrayVal[],int length) {
???? int i, j, max;
???? int temp;
???? for (j = length; j >1; j--) {
????????? max =0;//標(biāo)記最值位置
? ?? for (i =1; i < j; i++) {
???????? if (arrayVal[i] > arrayVal[max]) {
??????????????????? max = i;
???????? if (max != j -1) {
??????????????? temp = arrayVal[max];
??????????????? arrayVal[max] = arrayVal[j -1];
???????????????? arrayVal[j -1] = temp;
???????????????? }
?????????? }
???? }
}
}
三、插入排序
? ? 要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。
例如,已知待排序的一組記錄是：
1，3，5，8，2，1
加入之前的1，3，5，8已經(jīng)按照直接插入排序排序好了，現(xiàn)在我們需要對(duì)2進(jìn)行排序。 首先將2存在一個(gè)臨時(shí)變量temp中， 然后指針從2的前一位開(kāi)始判斷，如果前一位比2大，則將前一位往后移，以此類推，直到找到比2小的元素。這時(shí)將2插入進(jìn)去。
JAVA代碼實(shí)現(xiàn):
public static void StraightInsertSort(int[] a) {
int temp =0,j =0;
for(int i =1;i < a.length;i++){
temp = a[i]; j = i;
while(j >0 && a[j-1] >= temp){
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
四、 二分插入排序
將直接插入排序中尋找A[i]的插入位置的方法改為采用折半比較，即可得到折半插入排序算法。在處理A[i]時(shí)，A[0]……A[i-1]已經(jīng)按關(guān)鍵碼值排好序。所謂折半比較，就是在插入A[i]時(shí)，取A[i-1/2]的關(guān)鍵碼值與A[i]的關(guān)鍵碼值進(jìn)行比較，如果A[i]的關(guān)鍵碼值小于A[i-1/2]的關(guān)鍵碼值，則說(shuō)明A[i]只能插入A[0]到A[i-1/2]之間，故可以在A[0]到A[i-1/2-1]之間繼續(xù)使用折半比較；否則只能插入A[i-1/2]到A[i-1]之間，故可以在A[i-1/2+1]到A[i-1]之間繼續(xù)使用折半比較。如此擔(dān)負(fù)，直到最后能夠確定插入的位置為止。一般在A[k]和A[r]之間采用折半，其中間結(jié)點(diǎn)為A[k+r/2]，經(jīng)過(guò)一次比較即可排除一半記錄，把可能插入的區(qū)間減小了一半，故稱為折半。執(zhí)行折半插入排序的前提是文件記錄必須按順序存儲(chǔ)。
JAVA代碼實(shí)現(xiàn)：
public int getIndex(int arr[],int x){
int start=0;
int end=arr.length-1;
int min=0;
while(start<=end){
min=(start+end)/2;
if(x==arr[min]){
return min;
}else if(x
end=min-1;
}else if(x>arr[min){
start=min+1;
}
}
return -1;
}
