寫程式的基本功-排序演算法(Sorting Algorithm)
插入排序法(Insertion Sort)
插入排序，顧名思義就是將未排序的數字插入到已排序數列中的適當位置。
圖解插入排序法
假設現在有個陣列：[69,81,30,38,9,2,47,61,32,79] 要如何將它遞增排列呢？
首先先將[索引0]做為一個已排序好的數列並用粗體字表示，當然，一開始只有一個數。從[索引1]開始搬移，81比69大，故排在69的右邊。
此時已排序數列為[索引0~1]，接著搬移[索引2]的資料。30比81小，又比69小，所以30要搬到69的左邊。也就是說，30右邊的索引值都要往右移動一個位置。
此時已排序數列變為[索引0~2]，接著搬移[索引3]的資料。38比81小，又比69小，但比30大，所以38要搬到30的右邊和69的左邊。
再來一樣的方式將後面的索引資料搬移進已排序數列內。
搬完後整個陣列的內容都變成已排序數列啦！
插入排序法程式碼(Java)
public static int[] exchange_sort(int[] ori_arr, boolean isIncrease){ //交換排序（Exchange sort）
int[] arr=ori_arr.clone(); //將arr陣列位址指向新複製出來的ori_arr陣列。確保原始陣列資料不會改變。
int len=arr.length; //取得陣列長度
for(int i=0;i<len-1;i++){
for(int k=i+1;k<len;k++){
if((isIncrease&&arr[i]>arr[k])||(!isIncrease&&arr[i]<arr[k])){ //遞增遞減判斷
int buffer=arr[i];
arr[i]=arr[k];
arr[k]=buffer;
}
}
}
return arr;
} |
氣泡排序法(Bubble Sort)
氣泡排序法應該是最常見的排序方法吧！因為它簡單、易懂、容易撰寫。所謂「氣泡」，顧名思義就是它的排列方式如同氣泡一般將最大或最小的元素移動到陣列最右端，移動到最後，排序就完成啦！
圖解氣泡排序法
假設現在有個陣列：[69,81,30,38,9,2,47,61,32,79] 要如何將它遞增排列呢？
首先判斷[索引0]和[索引1]的元素數值大小，69小於81，不移動。
接著判斷[索引1]和[索引2]的元素數值大小，81大於30，將81和30的位置調換。
再來判斷[索引2]和[索引3]的元素值大小，81大於38，要調換位置。
81大於9，再調換。
81大於2，再調換。
聰明的你可以從圖中一看就知道81為此陣列中的最大值。因此它將會被移動到[索引9]的位置。
當81移動到[索引9]的位置時，[索引9]中的資料即表示此陣列的最大值。重複進行將[索引0]值移動到右邊索引的動作時，就不要再動右端到已經擺好的索引位置(以粗體字表示)。
完成所有的移動後，陣列的內容就被排序好了！
氣泡排序法程式碼(Java)
public static int[] selection_sort(int[] ori_arr, boolean isIncrease){ //選擇排序（Selection sort）
int[] arr=ori_arr.clone(); //將arr陣列位址指向新複製出來的ori_arr陣列。確保原始陣列資料不會改變。
int len=arr.length; //取得陣列長度
for(int i=0;i<len-1;i++){
int temp=i; //儲存最大或是最小值所指向的索引位置
for(int k=i+1;k<len;k++){
if((isIncrease&&arr[temp]>arr[k])||(!isIncrease&&arr[temp]<arr[k])){ //遞增遞減判斷
temp=k;
}
}
if(i!=temp){ //若索引未改變，則交換陣列值
int buffer=arr[i];
arr[i]=arr[temp];
arr[temp]=buffer;
}
}
return arr;
} |
