|
1、冒泡排序 Bubble Sort
最簡單的排序方法是冒泡排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，并時刻注意兩個相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個相鄰元素的順序不對，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“最輕”的元素就浮到了最高位置；處理二遍之后，“次輕”的元素就浮到了次高位置。在作第二遍處理時，由于最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經(jīng)過前面i-1遍的處理，它們已正確地排好序。這個算法可實現(xiàn)如下。
算法如下：
public static void maopaoSort(int []a){
int i,j,k; for(i=a.length-1;i>0;i--){ for(j=i-1;j>0;j--){ if(a[i]<a[j]){ k=a[i]; a[i]=a[j]; a[j]=k; } 2、選擇排序 Selection Sort
選擇排序的基本思想是：對待排序的記錄序列進行n-1遍的處理，第1遍處理是將L[1..n]中最小者與L[1]交換位置，第2遍處理是將L[2..n]中最小者與L[2]交換位置，......，第i遍處理是將L[i..n]中最小者與L[i]交換位置。這樣，經(jīng)過i遍處理之后，前i個記錄的位置就已經(jīng)按從小到大的順序排列好了。
當然，實際操作時，也可以根據(jù)需要，通過從待排序的記錄中選擇最大者與其首記錄交換位置，按從大到小的順序進行排序處理。 算法如下：
/**
*選擇排序
*@paramsrc待排序的數(shù)組
*/
void doChooseSort(int[] src)
{
int len=src.length;
int temp;
for(int i=0;i<len;i++)
{
temp=src[i];
int j;
int samllestLocation=i;//最小數(shù)的下標
for(j=i+1;j<len;j++)
{
if(src[j]<temp)
{
temp=src[j];//取出最小值
samllestLocation=j;//取出最小值所在下標
}
}
src[samllestLocation]=src[i];
src[i]=temp;
printResult(i,src);
}
}
3、插入排序 Insertion Sort
插入排序的基本思想是，經(jīng)過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]騆[1..i]已排好序，第i遍處理就結束了；否則交換L[i]與L[i-1]的位置，繼續(xù)比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時為止。
簡言之,插入排序就是每一步都將一個待排數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)中的適當位置，直到全部插入完畢。插入排序方法分直接插入排序和折半插入排序兩種，這里只介紹直接插入排序，折半插入排序留到“查找”內容中進行。 圖1演示了對4個元素進行直接插入排序的過程，共需要(a),(b),(c)三次插入。  圖1 對4個元素進行插入排序
在下面的插入排序算法中，為了寫程序方便我們可以引入一個哨兵元素L[0]，它小于L[1..n]中任一記錄。所以，我們設元素的類型ElementType中有一個常量-∞，它比可能出現(xiàn)的任何記錄都小。如果常量-∞不好事先確定，就必須在決定L[i]是否向前移動之前檢查當前位置是否為1，若當前位置已經(jīng)為1時就應結束第i遍的處理。另一個辦法是在第i遍處理開始時，就將L[i]放入L[0]中，這樣也可以保證在適當?shù)臅r候結束第i遍處理。下面的算法中將對當前位置進行判斷。
算法如下：
/**
*插入排序(WHILE循環(huán)實現(xiàn))
*@paramsrc待排序數(shù)組
*/
void doInsertSort1(int[] src)
{
int len=src.length;
for(int i=1;i<len;i++)
{
int temp=src[i];
int j=i;
while(src[j-1]>temp)
{
src[j]=src[j-1];
j--;
if(j<=0)
break;
}
src[j]=temp;
printResult(i+1,src);
}
}
/**
*插入排序(FOR循環(huán)實現(xiàn))
*@paramsrc待排序數(shù)組
*/
void doInsertSort2(int[] src)
{
int len=src.length;
for(int i=1;i<len;i++)
{
int j;
int temp=src[i];
for(j=i;j>0;j--)
{
if(src[j-1]>temp)
{
src[j]=src[j-1];
}else//如果當前的數(shù)，不小前面的數(shù)，那就說明不小于前面所有的數(shù)，
//因為前面已經(jīng)是排好了序的，所以直接通出當前一輪的比較
break;
}
src[j]=temp;
printResult(i,src);
}
}
|
|
|
