八大排序方法

分類：

1. 內部排序:

指將需要處理的所有資料都加載到內部存盤器中進行排序，

1. 外部排序法：

資料量過大，無法全部加載到記憶體中，需要借助外部存盤進行排序，

性能比較

交換排序

冒泡排序

冒泡排序（Bubble Sorting）的基本思想是：通過對待排序序列從前向后（從下標較小的元素開始）,依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前移向后部，就象水底下的氣泡一樣逐漸向上冒，

倆倆比較，小的換在前，大的換在后面，依次向后回圈這個程序

優化

因為排序的程序中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，因此要在排序程序中設定一個標志flag判斷元素是否進行過交換，從而減少不必要的比較，(這里說的優化，可以在冒泡排序寫好后，在進行)

//  // 將前面額冒泡排序演算法，封裝成一個方法
    public static void bubbleSort(int[] arr) {
        // 冒泡排序 的時間復雜度 O(n^2), 自己寫出
        int temp = 0; // 臨時變數
        boolean flag = false; // 標識變數，表示是否進行過交換
        for (int i = 0; i < arr.length - 1; i++) {

            for (int j = 0; j < arr.length - 1 - i; j++) {
                // 如果前面的數比后面的數大，則交換
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            //System.out.println("第" + (i + 1) + "趟排序后的陣列");
            //System.out.println(Arrays.toString(arr));

            if (!flag) { // 在一趟排序中，一次交換都沒有發生過
                break;
            } else {
                flag = false; // 重置flag!!!, 進行下次判斷
            }
        }
    }

快速排序

快速排序（Quicksort）是對冒泡排序的一種改進，

基本思想是：通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列，

程序
對6 1 2 7 9 3 4 5 10 8 進行排序

1. 首先哨兵j開始出動，因為此處設定的基準數是最左邊的數，所以需要讓哨兵j先出動，這一點非常重要，哨兵j一步一步地向左挪動（即j–-），直到找到一個小于6的數停下來，接下來哨兵i再一步一步向右挪動（即i++），直到找到一個數大于6的數停下來，最后哨兵j停在了數字5面前，哨兵i停在了數字7面前，
   

2. 交換哨兵i和哨兵j所指向的元素的值，交換之后的序列如下， 6 1 2 5 9 3 4 7 10 8
   

3. 到此，第一次交換結束，接下來開始哨兵j繼續向左挪動（再友情提醒，每次必須是哨兵j先出發），他發現了4（比基準數6要小，滿足要求）之后停了下來，哨兵i也繼續向右挪動的，他發現了9（比基準數6要大，滿足要求）之后停了下來，此時再次進行交換，交換之后的序列如下： 6 1 2 5 4 3 9 7 10 8

4. 當i和j指向的數相等時，交換基準數與該該數，到此第一輪“探測”結束，此時以基準數6為分界點，6左邊的數都小于等于6，6右邊的數都大于等于6，
5. 回顧剛才的程序，其實哨兵j的使命就是要找小于基準數的數，而哨兵i的使命就是要找大于基準數的數，直到i和j碰頭為止，

6. 通過上面的步驟，使基準數6已經歸位，它正好處在序列的第6位，此時我們已經將原來的序列，以6為分界點拆分成了兩個序列，左邊的序列是“3 1 2 5 4”，右邊的序列是“9 7 10 8”，
7. 接下來還需要分別處理這兩個序列，使6左邊和右邊的序列有序，只要模擬剛才的方法分別處理6左邊和右邊的序列即可，
8. 首先處理6左邊的序列現，左邊的序列是“3 1 2 5 4”，將這個序列以3為基準數進行調整，使得3左邊的數都小于等于3，3右邊的數都大于等于3，
9. 因為j往又右挪到動，i往左挪到，會在2的時候碰面，所以2會與3進行互動，調整完畢之后的序列的順序應該是：“ 2 1 3 5 4”，現在3已經歸位，
10. 接下來需要處理3左邊的序列“2 1”和右邊的序列“5 4”，對序列“2 1”以2為基準數進行調整，處理完畢之后的序列為“1 2”，到此2已經歸位，序列“1”只有一個數，也不需要進行任何處理，至此我們對序列“2 1”已全部處理完畢，得到序列是“1 2”，序列“5 4”的處理也仿照此方法，最后得到的序列如下：1 2 3 4 5 6 9 7 10 8
11. 對于序列“9 7 10 8”也模擬剛才的程序，直到不可拆分出新的子序列為止，最終將會得到這樣的序列，如下：1 2 3 4 5 6 7 8 9 10
12. 到此，排序完全結束，我們可以發現，快速排序的每一輪處理其實就是將這一輪的基準數歸位，直到所有的數都歸位為止，排序就結束了，下面是整個演算法的處理程序，
    

快速排序之所比較快，因為相比冒泡排序，每次交換是跳躍式的，每次排序的時候設定一個基準點，將小于等于基準點的數全部放到基準點的左邊，將大于等于基準點的數全部放到基準點的右邊，這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數之間進行交換，交換的距離就大的多了，因此總的比較和交換次數就少了，速度自然就提高了，當然在最壞的情況下，仍可能是相鄰的兩個數進行了交換，因此快速排序的最差時間復雜度和冒泡排序是一樣的都是O(N2)，它的平均時間復雜度為O(NlogN)，

代碼

//方法1：便于理解
public static void quickSort2(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;//起始位
        j=high;
        //temp就是基準位
        temp = arr[low];
        while (i<j) {
            //先看右邊，依次往左遞減
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左邊，依次往右遞增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果滿足條件則交換
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //最后將基準為與i和j相等位置的數字交換
        arr[low] = arr[i];
        arr[i] = temp;
        //遞回呼叫左半陣列
        quickSort(arr, low, j-1);
        //遞回呼叫右半陣列
        quickSort(arr, j+1, high);
    }



    public static void quickSort(int[] arr,int left, int right) {
        int l = left; //左下標
        int r = right; //右下標
        //pivot 中軸值
        int pivot = arr[(left + right) / 2];
        int temp = 0; //臨時變數，作為交換時使用
        //while回圈的目的是讓比pivot 值小放到左邊
        //比pivot 值大放到右邊
        while( l < r) { 
            //在pivot的左邊一直找,找到大于等于pivot值,才退出
            while( arr[l] < pivot) {
                l += 1;
            }
            //在pivot的右邊一直找,找到小于等于pivot值,才退出
            while(arr[r] > pivot) {
                r -= 1;
            }
            //如果l >= r說明pivot 的左右兩的值，已經按照左邊全部是
            //小于等于pivot值，右邊全部是大于等于pivot值
            if( l >= r) {
                break;
            }
            
            //交換
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            
            //如果交換完后，發現這個arr[l] == pivot值 相等 r--， 前移
            if(arr[l] == pivot) {
                r -= 1;
            }
            //如果交換完后，發現這個arr[r] == pivot值 相等 l++， 后移
            if(arr[r] == pivot) {
                l += 1;
            }
        }
        
        // 如果 l == r, 必須l++, r--, 否則為出現堆疊溢位
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左遞回
        if(left < r) {
            quickSort(arr, left, r);
        }
        //向右遞回
        if(right > l) {
            quickSort(arr, l, right);
        }
        
        
    }

選擇排序

選擇排序：每趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排序的記錄序列末尾，直到全部排序結束為止，

簡單選擇排序

1. 從第一個元素i開始，默認該元素已經被排序；
2. 取出下一個元素j，在已經排序的元素序列中從后往前掃描
3. 如果下一個元素j，小于之前已經被排序完的序列的最后一個元素i，則將元素j移動到i的前面
4. 重復步驟3，直到之前已經排序完的元素都比小于或者等于下一個元素j
5. 將元素j插入到步驟4所找到的那個元素之后
6. 重復2到5步驟

舉例：對 9 1 2 5 7 4 8 6 3 5進行簡單選擇排序
通過下面的排序可以發現，是將未排序的部分的最小值取出來，與未排序好的第一個數進行交換

所以排序后為：1 2 3 4 5 5 6 7 8 9

堆排序

堆是具有以下性質的完全二叉樹

• 每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；
• 每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆，
  

堆排序是將堆中的結點按照寬度優先將其進行編號，將這種邏輯結構映射到陣列中

• 下圖為大頂堆的映射
  

堆排序基本思想：

1. 將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點，
2. 將其與末尾元素進行交換，此時末尾就為最大值，
3. 然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值，
4. 反復執行123，便能得到一個有序序列了

將4 6 8 5 9進行堆排序

• 第一步：將給出的無序序列構成一個大頂堆（一般升序采用大頂堆，降序采用小頂堆)
  1.將無序序列構建為二叉樹，按照寬度優先進行構建
  
  2. 從最后一個非葉子結點6開始，從左至右，從下至上進行調整，
  
  3.找到第二個非葉節點4，由于[4,9,8]中9元素最大，4和9交換，
  
  4.交換導致了子根[4,5,6]結構混亂，繼續調整，[4,5,6]中6最大，交換4和6，無需序列構已經造成了一個大頂堆，
  

• 第二步：將堆頂元素與末尾元素進行交換，使末尾元素最大，然后繼續調整堆，再將堆頂元素與末尾元素交換，得到第二大元素，如此反復進行交換、重建、交換，
  1.將堆頂元素9和末尾元素4進行交換
  
  2.重新調整結構，使其繼續滿足堆定義
  
  3.再將堆頂元素8與末尾元素5進行交換，得到第二大元素8.
  
  4.按照123步驟，繼續進行調整，交換，如此反復進行，最終使得整個序列有序
  

堆排序參考鏈接

插入排序

插入排序：每一趟將一個待排序的記錄，按照其關鍵字的大小插入到有序佇列的合適位置里，知道全部插入完成

直接插入排序

直接插入排序：是一種最簡單的插入排序

其基本操作是：將一條記錄插入到已排好的有序表中，從而得到一個新的、記錄數量增1的有序表，

步驟：

1. 設陣列為a[0…n-1]
2. 初始時，a[0]自動生成一個有序區，無序區為：a[1...n-1]，此時i=1，令i為有序區和無序的標記，即i是無序區的第一個數字
3. 有序區的最后一個(a[i-1])與無序區的第一個(a[i])，進行比較，
4. 如果a[i-1]>a[i]，則將a[i]插入到有序區的最后一個，
5. 如果a[i-1]<a[i]，就a[i]插入到有序區最后一個數字的前面，然后a[i]這個數再與其前一位的陣列進行比較，再執行4和5這兩個步驟，直到i==n-1；

舉例說明：對 9 1 2 5 7 4 8 6 3 5進行直接插入排序
通過比較這些步驟可以發現，插入排序是將未排序的部分的第一個數字，與已排序部分的最后一個數字進行比較，如果小于就在已排序部分進行比較，如果大于就直接放在已排序部分的最后一個

希爾排序

希爾排序也是一種插入排序，它是簡單插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序

基本思想：該方法實質上是一種分組插入方法

把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，演算法便終止，

基本步驟：

1. 將無序陣列劃分為group = length/2個組，對這些組進行直接插入排序
2. 將組劃分為group1 = group/2，再對其進行直接插入排序，依次回圈，到groupn
3. 直到groupn/2 == 1時，這是最后的一次直接插入排序，排序過后的結果便為排序后的陣列

   注：為了方便理解，所以才用組來敘述，其實應該是叫做增量，也被稱為希爾增量，那些個陣列組其實就是增量序列

例題演示：

參考鏈接

歸并排序

基數排序

三大查找方法

順序查找演算法

順序查找的基本思想：

1. 從表的一端開始，順序掃描表，依次將掃描到的結點關鍵字和給定值（假定為a）相比較，
2. 若當前結點關鍵字與a相等，則查找成功；
3. 若掃描結束后，仍未找到關鍵字等于a的結點，則查找失敗，
4. 說白了就是，從頭到尾，一個一個地比，找著相同的就成功，找不到就失敗，
5. 很明顯的缺點就是查找效率低， 適用于線性表的順序存盤結構和鏈式存盤結構，

public static int sequentialSearch(int[] a, int key) {
    for ( int i = 0; i < a.length; i++) {
        if (a[i] == key)
        return i;
    }
    return - 1;
}

順序表查找優化

因為每次回圈時都需要對i是否越界，即是否小于等于n作判斷，事實上，還可以有更好一點的辦法，設定一個哨兵，可以解決不需要每次讓i與n作比較，看下面的改進后的順序查找演算法代碼，

public static int sequentialSearch2(int[] a, int key) {
    int index = a.length - 1;
    a[ 0] = key; // 將下標為0的陣列元素設定為哨兵
    while (a[index] != key) {
        index--;
    }
    return index;
}

折半查找

折半查找(Binary Search)技術，又稱為二分查找，它的前提是線性表中的記錄必須是關鍵碼有序(通常從小到大有序)，線性表必須采用順序存盤，

折半查找的基本思想是:

1. 在有序表中，取中間記錄作為比較物件，
2. 若給定值與中間記錄的關鍵字相等，則查找成功;
3. 若給定值小于中間記錄的關鍵字，則在中間記錄的左半區繼續查找;
4. 若給定值大于中間記錄的關鍵字，則在中間記錄的右半區繼續查找，
5. 不斷重復上 述程序，直到查找成功，或所有查找區域無記錄，查找失敗為止，

public static int binarySearch(int[] a, int key) {
    int low, mid, high;
    low = 0; // 最小下標
    high = a.length - 1; // 最大小標
    while (low < high) {
        mid = (high + low) / 2; // 折半下標
        if (key > a[mid]) {
            low = mid + 1; // 關鍵字比 折半值 大，則最小下標 調成 折半下標的下一位
        } else if (key < a[mid]) {
            high = mid - 1; // 關鍵字比 折半值 小，則最大下標 調成 折半下標的前一位
        } else {
            return mid; // 當 key == a[mid] 回傳 折半下標
        }
    }
    return -1;
}

最終我們折半演算法的時間復雜度為O(logn)，它顯然遠遠好于順序查找的O(n)時間復雜度了，

二分查找特別適用于那種一經建立就很少改動而又經常需要查找的線性表，

分塊查找

又稱索引順序查找，這是順序查找的一種改進方法，用于在分塊有序表中進行查找 ，

主表：存盤資料的表，長度n；

索引表：將主表分塊，每塊長s，找出每塊中的關鍵字最大值，并且保存該塊中所有資料在主表中的索引

（1）分塊：將n個資料元素“按塊有序”劃分為m塊，

每一塊中的結點不必有序，但塊與塊之間必須“按塊有序”；即第1塊中任一元素的關鍵字都必須小于第2塊中任一元素的關鍵字；而第2塊中任一元素又都必須小于第3塊中的任一元素，每個塊中元素不一定是有序的，

（2）根據查找值，和索引表中關鍵字（每塊中的最大關鍵字）比較，通過對分查找/順序查找，找到該值所在的塊范圍；

（3）在相應塊中，找到該值在主表中的位置，

平均查找長度ASL<=O(log2(n/s))+s/2 （先對分查找，或順序查找）