冒泡排序

• 算法規(guī)則： 由于算法每次都將一個(gè)最大的元素往上冒，我們可以將待排序集合(0...n)看成兩部分，一部分為(k..n)的待排序unsorted集合，另一部分為(0...k)的已排序sorted集合，每一次都在unsorted集合從前往后遍歷，選出一個(gè)數(shù)，如果這個(gè)數(shù)比其后面的數(shù)大，則進(jìn)行交換。完成一輪之后，就肯定能將這一輪unsorted集合中最大的數(shù)移動(dòng)到集合的最后，并且將這個(gè)數(shù)從unsorted中刪除，移入sorted中。冒泡排序的時(shí)間復(fù)雜度為O(n^2)。

• 代碼實(shí)現(xiàn)(java)

public void bubbleSort(int[] data){
    //這里從數(shù)組最后面開(kāi)始遍歷
    for (int i = data.length - 1; i > 0; --i) {
        //在這里體現(xiàn)出 “將每一趟排序選出來(lái)的最大的數(shù)從sorted中移除”
        for (int j = 0; j < i; j++) {
            //保證在相鄰的兩個(gè)數(shù)中比較選出最大的并且進(jìn)行交換(冒泡過(guò)程)
            if (data[j] > data[j + 1]) {
                int temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }
}

并歸排序

• 算法規(guī)則： 像快速排序一樣，由于歸并排序也是分治算法，因此可使用分治思想：
  1.申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
  2.設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
  3.比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
  4.重復(fù)步驟3直到某一指針到達(dá)序列尾
  5.將另一序列剩下的所有元素直接復(fù)制到合并序列尾
  空間復(fù)雜度為O(n)，時(shí)間復(fù)雜度為O(nlogn)。
• 代碼實(shí)現(xiàn)(java)

public void mergeSort(int[] a, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
        //左邊
        mergeSort(a, low, mid);
        //右邊
        mergeSort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
}

private void merge(int[] a, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    //指向左邊的指針
    int i = low;
    //指向右邊的指針
    int j = mid + 1;
    int k = 0;
    //把較小的數(shù)先移到新數(shù)組中
    while (i <= mid && j <= high) {
        if (a[i] > a[j]) {
            temp[k++] = a[j++];
        } else {
            temp[k++] = a[i++];
        }
    }
    //左邊剩余的數(shù)據(jù)加入得到新數(shù)組
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    //右邊剩余的數(shù)據(jù)加入到新數(shù)組
    while (j <= high) {
        temp[k++] = a[j++];
    }
    for (int l = 0; l < temp.length; l++) {
        a[l + low] = temp[l];
    }
}

快速排序

• 算法規(guī)則： 本質(zhì)來(lái)說(shuō)，快速排序的過(guò)程就是不斷地將無(wú)序元素集遞歸分割，一直到所有的分區(qū)只包含一個(gè)元素為止。
  由于快速排序是一種分治算法，我們可以用分治思想將快排分為三個(gè)步驟：
  1.分：設(shè)定一個(gè)分割值，并根據(jù)它將數(shù)據(jù)分為兩部分
  2.治：分別在兩部分用遞歸的方式，繼續(xù)使用快速排序法
  3.合：對(duì)分割的部分排序直到完成
  快速排序是不穩(wěn)定的，其時(shí)間平均時(shí)間復(fù)雜度是O(nlgn)。

• 代碼實(shí)現(xiàn)(java)

    public static int dividerAndChange(int[] args, int start, int end) {
        //參照值
        int pivot = args[start];
        while (start < end) {
            //首先從右向左查找,直到找到比參數(shù)小的第一個(gè)數(shù),然后交換位置
            while (start < end && pivot <= args[end]) {
                end--;
            }
            if (start < end) {
                //開(kāi)始交換位置
                args[start] = args[end];
                start++;
            }
            //從左往右找，找到比參數(shù)大的就交換位置
            while (start < end && pivot > args[start]) {
                start++;
            }
            if (start < end) {
                //開(kāi)始交換位置
                args[end] = args[start];
                end--;
            }
        }
        args[start] = pivot;
        System.out.println("start:" + start + ",end:" + end);
        return start;
    }
    
    public static void quickSort(int[] args, int start, int end) {
        if (end - start > 1) {
            int mid = dividerAndChange(args, start, end);
            //對(duì)左邊數(shù)組排序
            quickSort(args, start, mid);
            //對(duì)右邊數(shù)組排序
            quickSort(args, mid + 1, end);
        }
    }

選擇排序

• 算法規(guī)則： 將待排序集合(0...n)看成兩部分，在起始狀態(tài)中，一部分為(k..n)的待排序unsorted集合，另一部分為(0...k)的已排序sorted集合,在待排序集合中挑選出最小元素并且記錄下標(biāo)i，若該下標(biāo)不等于k，那么 unsorted[i] 與 sorted[k]交換 ，一直重復(fù)這個(gè)過(guò)程，直到unsorted集合中元素為空為止。選擇排序的時(shí)間復(fù)雜度為O(n^2)

• 代碼實(shí)現(xiàn)(java)

public void selectionSort(int[] args){
    for (int i = 0; i < args.length - 1; i++) {
        int k = i;
        for (int j = k + 1; j < args.length; j++) {
            //循環(huán)遍歷,找到最小值的下標(biāo)
            if (args[j] < args[k]) {
                k = j;
            }
        }
        if (k != i) {
            //交換args[i]和args[k]
            int temp = args[i];
            args[i] = args[k];
            args[k] = temp;
        }
    }
}

插入排序

• 算法規(guī)則：插入排序不是通過(guò)交換位置而是通過(guò)比較找到合適的位置插入元素來(lái)達(dá)到排序的目的的。相信大家都有過(guò)打撲克牌的經(jīng)歷，特別是牌數(shù)較大的。在分牌時(shí)可能要整理自己的牌，牌多的時(shí)候怎么整理呢？就是拿到一張牌，找到一個(gè)合適的位置插入。這個(gè)原理其實(shí)和插入排序是一樣的。舉個(gè)栗子，對(duì)5,3,8,6,4這個(gè)無(wú)序序列進(jìn)行簡(jiǎn)單插入排序，首先假設(shè)第一個(gè)數(shù)的位置時(shí)正確的，想一下在拿到第一張牌的時(shí)候，沒(méi)必要整理。然后3要插到5前面，把5后移一位，變成3,5,8,6,4.想一下整理牌的時(shí)候應(yīng)該也是這樣吧。然后8不用動(dòng)，6插在8前面，8后移一位，4插在5前面，從5開(kāi)始都向后移一位。注意在插入一個(gè)數(shù)的時(shí)候要保證這個(gè)數(shù)前面的數(shù)已經(jīng)有序。簡(jiǎn)單插入排序的時(shí)間復(fù)雜度也是O(n^2)。

    /**
    * 插入排序
    * @param args
    * @return
    */
   public static int[] insertSort(int[] args) {
       if (args.length == 0) {
           return null;
       }

       // 默認(rèn)數(shù)組的第一個(gè)數(shù)字已經(jīng)排好序
       // 這里把第二個(gè)數(shù)字,作為拿來(lái)比較的數(shù)字.假設(shè)第一個(gè)數(shù)字位置已經(jīng)確定.然后將二個(gè)數(shù)字和第一個(gè)數(shù)字比較
       for (int i = 1; i < args.length; i++) {
           int k = i;
           //這里將未排序的第一個(gè)數(shù)字拿出來(lái)
           int target = args[i];
           /*for (k = i - 1; k >= 0 && target < args[k]; k--) {
               args[k + 1] = args[k];
           }*/
           //這里循環(huán)比較,將未排序的第一個(gè)數(shù)和前面已排序的數(shù)組循環(huán)比較
           while (k >= 0 && target < args[k - 1]) {
               args[k] = args[k - 1];
               k--;
           }
           //這里重新設(shè)置參照值.
           args[k] = target;
       }
       return args;
   }