八大排序算法總結(jié)

1. 冒泡排序

• 思想：元素兩兩進行比較，然后交換位置拉盾，通過兩次層循環(huán)把數(shù)據(jù)排序

• 優(yōu)點：數(shù)據(jù)量較小的時候桨菜，算法效率較高

• 缺點：

  1. 時間復(fù)雜度為O(n^2)豁状，當(dāng)數(shù)據(jù)量較大的時候捉偏，效率低下
  2. 可以看到，外層循環(huán)每一次結(jié)束后泻红，實際上是將一個相對最大（最胸睬荨）的數(shù)挑出來了，其他的數(shù)據(jù)雖然相對有序谊路，但依然是無序的讹躯，需要再次比較，因此交換位置其實沒有必要缠劝，我們只需要把最大（最谐碧荨）值的角標(biāo)記下來，當(dāng)一次循環(huán)結(jié)束后惨恭，把制定位置的元素進行交換位置就可以了秉馏。這種排序算法就是選擇排序；
  3. 我們可以將整個數(shù)組分成若干個小數(shù)組脱羡，對每個數(shù)組分別進行排序萝究，然后把排好序的數(shù)組在合并起來，因為小數(shù)組的排序性能消耗較小锉罐，因此可以提高效率帆竹，這種排序算法就是快速排序，這實際上是分治思想（分而治之）脓规；

• 使用場景：當(dāng)數(shù)據(jù)的個數(shù)在[0 , 2^3]之間時栽连，可以使用冒泡排序，因為在該種情況下侨舆，實際上進行不了幾次比較秒紧；

• 注意事項：

  • 兩處優(yōu)化：
    • 1. 隨著比較的趟數(shù)增加，數(shù)據(jù)會逐漸有序起來态罪，而且數(shù)組后面的元素是有序的噩茄，因此這部分?jǐn)?shù)據(jù)可以退出排序，因此內(nèi)層循環(huán)可以通過控制要比較的元素的個數(shù)來達到這個目的复颈，即j < array.length - 1 - i绩聘；
    • 2. 當(dāng)比較的趟數(shù)還沒有結(jié)束且數(shù)據(jù)已經(jīng)是有序的時候沥割，就不需要通過排序了，這個時候直接結(jié)束循環(huán)即可凿菩，那么可以通過一個標(biāo)記flag來達到這個目的机杜，如果內(nèi)層循環(huán)在一次循環(huán)過程中，里面的if判斷語句沒有執(zhí)行衅谷，就表示數(shù)據(jù)已經(jīng)是有序的椒拗，因此就可以跳出循環(huán)了。

• 代碼實現(xiàn)

    public void bubbleSort(int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException();
        }
  
        //外層控比較的趟數(shù)
        for (int i = 0; i < array.length - 1; i++) {//有多少個元素就需要比較多少趟
            //內(nèi)層控制比較的次數(shù)获黔，每一次循環(huán)結(jié)束都會有一個最大（最惺纯痢）值出現(xiàn)在數(shù)組的最后一個角標(biāo)的位置
            //因此這個元素可以退出排序，從而減少內(nèi)層循環(huán)的次數(shù)
            boolean flag = true;
            for (int j = 0; j < array.length - 1 - i; j++) {
                //從小到大排序
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = false;
                }
            }
            //如果整個內(nèi)層循環(huán)里面的比較都沒有執(zhí)行玷氏，就表明所有的數(shù)字就是有序的堵未，可以不用再進行排序了，直接跳出循環(huán)
            if (flag) {
                break;
            }
        }
    }
  

2. 快速排序

• 思想：對冒泡排序的優(yōu)化盏触，

  • 基本思想:通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠稚罚渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可以分別對這兩部分記錄繼續(xù)進行排序赞辩，以達到整個序列有序雌芽。
  • 典型的分治思想，因為有遞歸調(diào)用辨嗽，所以是二叉樹的前序遍歷世落；
  • 分治思想：將一個大的問題分解成幾個小問題，然后對各個小問題各個擊破召庞，最后將所有子問題合并岛心，最終得到母問題的解。因此遞歸也是分治思想篮灼。但需要注意的是忘古，這里不是分類討論的思想；

• 優(yōu)點：數(shù)據(jù)量大且是線性結(jié)構(gòu)時诅诱，效率較高髓堪；

• 缺點：

  1. 算法不穩(wěn)定，有大量重復(fù)數(shù)據(jù)時娘荡，性能不好干旁；
  2. 單向鏈?zhǔn)浇Y(jié)構(gòu)處理性能不好（一般來說，鏈?zhǔn)蕉疾皇褂每焖倥判颍?/li>

• 使用場景：數(shù)據(jù)量大并且是線性結(jié)構(gòu)（數(shù)組）炮沐，當(dāng)時鏈?zhǔn)浇Y(jié)構(gòu)時不要使用這種排序算法争群，JDK中Arrays里面的排序算法就是快速排序，Collections.sort(int[] arr)實際上調(diào)用的就是Arrays里面的排序算法大年。

• 實現(xiàn)步驟：

  1. 先進行一次快速排序换薄，將數(shù)組分割成兩部分玉雾，使得左邊的數(shù)比指定位置的數(shù)小，右邊的數(shù)比指定的位置的數(shù)大轻要；
     1. 任取一個位置的元素（一般都選待排數(shù)組的第一個元素）作為樞軸复旬，同時給待排數(shù)組的第一個元素標(biāo)記為low稀蟋，最后一個元素標(biāo)記為high搬泥，設(shè)樞軸記錄的關(guān)鍵字pivotKey缴淋；
     2. 將所有關(guān)鍵字比樞軸小的記錄都安置在他的位置之前封锉，將所有關(guān)鍵字比樞軸大的記錄都排在他的位置之后，（由此可以將該“樞軸”記錄最后所落得位置i作為分界線吞歼，使待排數(shù)組分成兩個子數(shù)組）漠魏；
        • 具體做法：
          1. 首先從high所指位置起向前搜索浩淘，找到第一個關(guān)鍵字小于pivotKey的記錄咳焚，并且和樞軸記錄互相交換洽损；
          2. 然后從low所指位置起向后搜索庞溜，找到第一個關(guān)鍵字大于pivotKey的記錄革半，然后和樞軸記錄互相交換；
          3. 重復(fù)第一第二步流码，直至low=high為止又官；
  2. 完成第一步后，分別對左邊的數(shù)組和右邊的數(shù)組遞歸進行排序漫试；

• 代碼實現(xiàn)

    public void quickSort(int[] arr, int begin, int end) {
        if (end - begin <= 0) {
            return;
        }
        //從右相左開始
        boolean isFromRight = true;
        int low = begin;
        int high = end;
        int pivotKey = arr[begin];
        //先從high開始
        L1:
        while (high > low) {
            //從右往左開始
            if (isFromRight) {
                for (int i = high; i > low; i--) {
                    //要求：pivotKey關(guān)鍵字右邊的數(shù)都比pivotKey大
                    if (arr[i] <= pivotKey) {
                        //如果右邊的比pivotKey小六敬，就交換位置,注意這里不是交換兩個元素
                        arr[low++] = arr[i];
                        high = i;
                        //交換之后，從相反的順序開始
                        isFromRight = !isFromRight;
                        continue L1;
                    }
                }
                //只有當(dāng)右邊的數(shù)都比pivotKey大的時候驾荣，才會走到這里來
                high = low;
            } else {
                for (int i = low; i < high; i++) {
                    if (arr[i] >= low) {
                        arr[high--] = arr[i];
                        low = i;
                        isFromRight = !isFromRight;
                        continue L1;
                    }
                }
                low = high;
            }
        }
        //第一次快速排序結(jié)束外构，將最后找到的值放入中間，即pivotKey
        arr[low]=pivotKey;//因為此時low已經(jīng)等于high播掷，所以寫誰都一樣
  
        //對左邊的數(shù)組進行排序
        quickSort(arr,begin,low-1);
        //對右邊的數(shù)組進行排序
        quickSort(arr,high+1,end);
    }
  

3. 選擇排序

• 思想

• 優(yōu)點

• 缺點

• 使用場景

• 代碼實現(xiàn)

3. 歸并排序

4. 希爾排序

6. 插入排序

7. 堆排序

8. 基數(shù)排序（鏈?zhǔn)交鶖?shù)排序）

9. 二分查找算法