一冤议、插入排序

1、直接插入

直接插入排序類似于撲克牌师坎，分為兩塊恕酸，一塊是排完序的，一塊是沒有進(jìn)行排序的胯陋。
例如下面四個(gè)元素的數(shù)組蕊温，| 的左邊的有序的袱箱，右邊是無序的。

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

默認(rèn)左邊第一個(gè)數(shù)是有序的排序的時(shí)候從 | 的右邊取一個(gè)數(shù)义矛，如果比左邊的小則交換发笔，一直交換到數(shù)組下標(biāo)為1。
i 代表 | 凉翻，j代表從 | 右邊取出的元素
代碼實(shí)現(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;
}

這種算法有缺陷了讨，每次對(duì)比都要交換元素
改進(jìn)：

  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;
    }

使用插入排序?yàn)橐涣袛?shù)字進(jìn)行排序的過程

二、選擇排序

1制轰、直接選擇

首先在未排序序列中找到最星凹啤（大）元素，存放到排序序列的起始位置垃杖，然后男杈，再從剩余未排序元素中繼續(xù)尋找最小（大）元素调俘，然后放到已排序序列的末尾伶棒。以此類推，直到所有元素均排序完畢脉漏。

選擇排序的示例動(dòng)畫苞冯。紅色表示當(dāng)前最小值，黃色表示已排序序列侧巨，藍(lán)色表示當(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司忱、冒泡排序

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

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大糊闽，就交換他們兩個(gè)梳玫。
2. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)右犹。在這一點(diǎn)提澎，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3. 針對(duì)所有的元素重復(fù)以上的步驟念链，除了最后一個(gè)盼忌。
4. 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟积糯，直到?jīng)]有任何一對(duì)數(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í)看成，將數(shù)組劃分成兩個(gè)較小的部分，然后遞歸排序他們跨嘉。

在一個(gè)元素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;
    }