一、插入排序

1、直接插入

直接插入排序類似于撲克牌，分為兩塊，一塊是排完序的，一塊是沒有進行排序的。
例如下面四個元素的數(shù)組，| 的左邊的有序的，右邊是無序的。

3 | 1 4 2
1 3 | 4 2
1 3 4 | 2
1 2 3 4 |

默認左邊第一個數(shù)是有序的排序的時候從 | 的右邊取一個數(shù)，如果比左邊的小則交換，一直交換到數(shù)組下標(biāo)為1。
i 代表 | ，j代表從 | 右邊取出的元素
代碼實現(xiàn)：

public int[] insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        for (int j = i; j > 0; j--) {
            if (a[j - 1] > a[j]) {
                int temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
            }
        }
   }
   return a;
}

這種算法有缺陷，每次對比都要交換元素
改進：

  public int[] insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int temp = a[i];
            int j = i - 1;
            for (; j >= 0 && a[j] > temp; j--) {
                a[j + 1] = a[j];
            }
            a[j + 1] = temp;
        }
        return a;
    }

使用插入排序為一列數(shù)字進行排序的過程

二、選擇排序

1、直接選擇

首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序的示例動畫。紅色表示當(dāng)前最小值，黃色表示已排序序列，藍色表示當(dāng)前位置。

  public void selectionSort(int[] a){
        for(int i=0;i<a.length;i++){
            int min = i;
            for(int j = i+1;j<a.length;j++){
                if(a[min]>a[j]){
                    min = j;
                }
            }
            int temp = a[min];
            a[min] = a[i];
            a[i] = temp;
        }
    }

三、交換排序

1、冒泡排序

冒泡排序是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。
3. 針對所有的元素重復(fù)以上的步驟，除了最后一個。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

 public void bubbleSort(int[] a) {  
     for(int i = 0;i<a.length-1;i++){
            for(int j=0;j<a.length-i-1;j++){
                if(a[j]>a[j+1]){
                    swap(a,j,j+1);
                }
            }
        }
 }   

2、快速排序

排序數(shù)組時，將數(shù)組劃分成兩個較小的部分，然后遞歸排序他們。

在一個元素55處劃分，把小于55的放在左邊，大于55的放在右邊。

然后在分別遞歸左邊和右邊的數(shù)組，即可完成排序

    public int[] qSort(int[] a, int start, int end) {
        if (a == null||a.length == 0) {
            return null;
        }
        if (start >= end) {
            return a;
        }
        int middel = partition(a, start, end);
        qSort(a, start, middel - 1);
        qSort(a, middel+1, end);
        return a;
    }
    public int partition(int[] data, int low, int high) {
        int temp = data[low]; // 軸記錄
        while (low < high) {
            while (low < high && data[high] >= temp) {
                --high;
            }
            data[low] = data[high];             //交換比樞軸小的記錄到左端
            while (low < high && data[low] <= temp) {
                ++low;
            }
            data[high] = data[low];           //交換比樞軸小的記錄到右端
        }
        //掃描完成，樞軸到位
        data[low] = temp;
        //返回的是樞軸的位置
        return low;
    }