前面三篇博文分别實作了快速排序：排序算法之快速排序java實作、堆排序：排序算法之堆排序java實作和歸并排序：排序算法之歸并排序java實作。
本篇博文主要分析常用的幾種排序算法。
首先來看一下各個排序算法的複雜度，如下圖所示（圖檔來自百度圖檔）
1、插入排序
插入排序（Insert Sort），每步将一個待排序的對象，按其排序碼大小，茶如道前面已經排好序的一組對象的适當位置上個，直到對象全部插入為止。根據插入點查找方式的不同，有這樣幾個方法：直接插入排序、折半插入排序、希爾排序。
1）直接插入排序（穩定）
直接插入排序的基本思想是：順序地把待排序的資料元素按其值的大小 插入到已排序資料元素子集合的适當位置，直到子集合大小和集合大小相同時為止。
直接插入排序過程如下圖所示（圖檔來自百度圖檔）：
直接插入排序java實作：
package sort;
public class InsertSort {
public static void main(String[] args) {
int[] a = {53, 27, 36, 15, 69, 42};
d_insertSort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
public static void d_insertSort(int[] a){ //直接插入排序
for(int i=1; i<a.length; i++){
int j = i-1;
int key = a[i];
while(j>=0 && a[j]>key){
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}
}
輸出：15 27 36 42 53 69
2）希爾（Shell）排序（不穩定）
希爾排序的基本思想是：把待排序的資料元素分成若幹個小組，對同一小組内的資料元素用直接插入法排序；小組的個數逐次縮小；當完成了所有資料元素都在一個組内的排序後排序過程結束。希爾排序又稱縮小增量排序。
希爾排序過程如下圖所示（圖檔來自百度圖檔）：
希爾排序java實作（略）
2、選擇排序
1）直接選擇排序（不穩定）
直接選擇排序的算法思想是：首先找到最小元素，将其放入a[0]中，然後找到剩下的n-1個元素中最小元素，将其放入a[1]中，重複此過程，直到找到第二大元素，将其放入a[n-2]中。
直接選擇排序過程如下圖所示：
直接選擇排序java實作：
package sort;
public class SelectionSort {
public static void main(String[] args) {
int[] a = {53, 27, 36, 15, 69, 42};
d_selectionSort(a);
for(int i=0; i<a.length; i++){
System.out.print(a[i] + " ");
}
}
public static void d_selectionSort(int[] a){
for(int i=0; i<a.length-1; i++){
int k = i;
for(int j=i+1; j<a.length; j++){ //查找最小的元素
if(a[j] < a[k])
k = j;
}
if(k!=i){//交換
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
}
}
輸出：15 27 36 42 53 69
2）堆排序（不穩定）
堆排序在前面的一篇博文中以詳細介紹： 排序算法之堆排序java實作，這裡不再重複。
3、交換排序
1）冒泡排序（穩定）
冒泡排序的基本思想是：設數組a中存放了n個元素，循環進行n-1趟如下排序過程：第1趟時，依次比較相鄰兩個資料元素a[i]和a[i+1](i=0,1,2,...,n-2)，若為逆序，則交換兩個元素，否則不交換，這樣數組最大的資料元素将被放在a[n-1]中。第二趟時，循環次數減1，操作步驟和第一趟類似，如此循環重複，直到a[0]放置最小的元素。就像水底的氣泡一樣逐漸向上冒。
冒泡排序過程如下圖所示（網絡圖檔）：
冒泡排序java實作：
package sort;
public class BubbleSort {
public static void main(String[] args) {
int[] a = {53, 27, 36, 15, 69, 42};
bubbleSort(a);
for(int i=0; i<a.length; i++){
System.out.print(a[i] + " ");
}
}
static void bubbleSort(int[] a){
for(int i=0; i<a.length-1; i++){ //n-1趟排序
for(int j=0; j<a.length-i-1; j++){ //對無序序列0~length-i-1進行排序
if(a[j]>a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
}
輸出：15 27 36 42 53 69
2）快速排序（不穩定）
快速排序在前面的一篇博文中已較長的描述： 排序算法之快速排序java實作，這裡不再重複
歸并排序（穩定）：排序算法之歸并排序java實作