常見排序算法分類

常見排序算法可以分為兩大類：

• 非線性時(shí)間比較類排序：通過比較來決定元素間的相對(duì)次序融击，由于其時(shí)間復(fù)雜度不能突破O(nlogn)筑公，因此稱為非線性時(shí)間比較類排序。如：快速排序尊浪、歸并排序匣屡、堆排序、冒泡排序等拇涤。在排序的最終結(jié)果里捣作，元素之間的次序依賴于它們之間的比較。每個(gè)數(shù)都必須和其他數(shù)進(jìn)行比較鹅士，才能確定自己的位置券躁。

• 線性時(shí)間非比較類排序：不通過比較來決定元素間的相對(duì)次序，它可以突破基于比較排序的時(shí)間下界掉盅，以線性時(shí)間運(yùn)行也拜，因此稱為線性時(shí)間非比較類排序。如：計(jì)數(shù)排序趾痘、基數(shù)排序慢哈、桶排序。非比較排序是通過確定每個(gè)元素之前永票，應(yīng)該有多少個(gè)元素來排序卵贱。針對(duì)數(shù)組arr，計(jì)算arr之前有多少個(gè)元素侣集，則唯一確定了arr在排序后數(shù)組中的位置键俱。

常見算法的復(fù)雜度分析

參考這里：所謂穩(wěn)定性是指待排序的序列中有兩元素相等,排序之后它們的先后順序不變.假如為A1,A2.它們的索引分別為1,2.則排序之后A1,A2的索引仍然是1和2.（相同的記錄在排序前后相對(duì)次序不發(fā)生改變，那么就是穩(wěn)定的排序）

對(duì)于不穩(wěn)定的 排序算法 世分，只要舉出一個(gè)實(shí)例编振，即可說明它的不穩(wěn)定性；而對(duì)于穩(wěn)定的排序算法罚攀，必須對(duì)算法進(jìn)行分析從而得到穩(wěn)定的特性党觅。需要注意的是雌澄， 排序算法是否為穩(wěn)定的是由具體算法決定的 ，不穩(wěn)定的算法在某種條件下可以變?yōu)榉€(wěn)定的算法杯瞻，而穩(wěn)定的算法在某種條件下也可以變?yōu)椴环€(wěn)定的算法镐牺。例如，對(duì)于如下冒泡排序算法魁莉，原本是穩(wěn)定的排序算法睬涧，如果將記錄交換的條件改成a[j]>=a[j+1]，則兩個(gè)相等的記錄就會(huì)交換位置旗唁。

穩(wěn)定性的意義：

1畦浓、如果只是簡(jiǎn)單的進(jìn)行數(shù)字的排序，那么穩(wěn)定性將毫無意義检疫。
2讶请、如果排序的內(nèi)容僅僅是一個(gè)復(fù)雜對(duì)象的某一個(gè)數(shù)字屬性，那么穩(wěn)定性依舊將毫無意義（所謂的交換操作的開銷已經(jīng)算在算法的開銷內(nèi)了屎媳，如果嫌棄這種開銷夺溢，不如換算法好了？）
3烛谊、如果要排序的內(nèi)容是一個(gè)復(fù)雜對(duì)象的多個(gè)數(shù)字屬性风响，但是其原本的初始順序毫無意義，那么穩(wěn)定性依舊將毫無意義丹禀。
4状勤、除非要排序的內(nèi)容是一個(gè)復(fù)雜對(duì)象的多個(gè)數(shù)字屬性，且其原本的初始順序存在意義双泪，那么我們需要在二次排序的基礎(chǔ)上保持原有排序的意義持搜，才需要使用到穩(wěn)定性的算法，例如要排序的內(nèi)容是一組原本按照價(jià)格高低排序的對(duì)象攒读，如今需要按照銷量高低排序朵诫，使用穩(wěn)定性算法辛友，可以使得想同銷量的對(duì)象依舊保持著價(jià)格高低的排序展現(xiàn)薄扁，只有銷量不同的才會(huì)重新排序。（當(dāng)然废累，如果需求不需要保持初始的排序意義邓梅，那么使用穩(wěn)定性算法依舊將毫無意義）。

• 穩(wěn)定排序算法：冒泡排序邑滨、插入排序日缨、歸并排序、（計(jì)數(shù)排序掖看、桶排序與基數(shù)排序）
• 不穩(wěn)定排序算法：希爾排序匣距、選擇排序面哥、堆排序與快速排序

復(fù)雜度分析：

• 數(shù)據(jù)結(jié)構(gòu)和算法本身解決的是“快”和“省”的問題，衡量算法執(zhí)行效率的指標(biāo)就包括復(fù)雜度
• 復(fù)雜度分析包括時(shí)間復(fù)雜度和空間復(fù)雜度分析毅待，時(shí)間復(fù)雜度是指算法執(zhí)行的時(shí)間與數(shù)據(jù)規(guī)模的關(guān)系尚卫，空間復(fù)雜度是指算法占用的空間與數(shù)據(jù)規(guī)模的關(guān)系

為什么進(jìn)行復(fù)雜度分析？如何分析尸红？

• 為什么分析復(fù)雜度：通過測(cè)試吱涉、統(tǒng)計(jì)、監(jiān)控外里，可以的得到算法執(zhí)行的時(shí)間和占用的內(nèi)存大小怎爵，但是測(cè)試結(jié)果非常依賴測(cè)試環(huán)境，測(cè)試結(jié)果受數(shù)據(jù)規(guī)模的影響很大盅蝗；我們需要一個(gè)不依賴測(cè)試環(huán)境和數(shù)據(jù)規(guī)模就可以粗略估算算法執(zhí)行效率的方法

大O時(shí)間復(fù)雜度表示法：表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)鳖链，又稱漸進(jìn)時(shí)間復(fù)雜度。

大O空間復(fù)雜度表示法：表示代碼執(zhí)行所占的內(nèi)存空間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)墩莫，又稱漸進(jìn)空間復(fù)雜度 ps：給出隨著增長(zhǎng)規(guī)模的下界撒轮，具體流程：https://www.cnblogs.com/zxhyJack/p/10596735.html

• 大O復(fù)雜度表示法

算法的執(zhí)行效率，粗略地講就是算法的執(zhí)行時(shí)間贼穆。下面的代碼是求1题山，2，3...n累加的和故痊。

cal(int n) {
  int sum = 0;
  int i = 1;
  for (; i <= n; ++i) {
    sum += i;  // 兩步操作
  }
  return sum;
}

從CPU的角度顶瞳，這段代碼的操作是，讀數(shù)據(jù) -> 運(yùn)算 -> 寫數(shù)據(jù)愕秫，如果每一個(gè)操作都是unit_time慨菱，第二行和第三行是一個(gè)unit_time，而第四行和第五行的for循環(huán)是2n個(gè)unit_time戴甩，加上return操作符喝。時(shí)間復(fù)雜度就是2n+3，一般計(jì)算的時(shí)候會(huì)把常量省略甜孤，所以這個(gè)程序的時(shí)間復(fù)雜度就是n协饲。所以就可以推斷出，所以代碼的執(zhí)行時(shí)間T(n)與每行代碼的的執(zhí)行次數(shù)成正比缴川。

引出重要概念：所有代碼的執(zhí)行時(shí)間 T(n) 與每行代碼的執(zhí)行次數(shù) n 成正比茉稠，即T(n) = O(f(n))

• 復(fù)雜度分析法則

  • 單段代碼，看循環(huán)的次數(shù)把夸。
  • 多段代碼而线，看代碼循環(huán)量級(jí)。
  • 嵌套代碼求乘積，比如遞歸和多重循環(huán)膀篮。
  • 多個(gè)規(guī)模求加法嘹狞，方法中并行的兩個(gè)循環(huán)。

• 常用的復(fù)雜度級(jí)別

  • 多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長(zhǎng)誓竿，算法的執(zhí)行時(shí)間和空間占用刁绒，按照多項(xiàng)式的比例增長(zhǎng)，包括烤黍，O(1)(常數(shù)階)知市、O(logn)(對(duì)數(shù)階)、O(n)(線性階)速蕊、O(nlogn)(線性對(duì)數(shù)階)嫂丙、O(n^{2)(平方階)、O(n}3)(立方階)规哲。
  • 非多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長(zhǎng)跟啤，算法的執(zhí)行時(shí)間和空間占用暴增，這列算法性能極差唉锌。包括隅肥，O(2^n)(指數(shù)階)、O(n!)(階乘階)

• 復(fù)雜度分析的四個(gè)概念

  • 最壞情況時(shí)間復(fù)雜度：代碼在最壞情況下執(zhí)行的時(shí)間復(fù)雜度袄简。
  • 最好情況時(shí)間復(fù)雜度：代碼在最理想情況下執(zhí)行的時(shí)間復(fù)雜度腥放。
  • 平均時(shí)間復(fù)雜度：用代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值表示。
  • 均攤時(shí)間復(fù)雜度：在代碼執(zhí)行的所有復(fù)雜度情況中絕大部分是低級(jí)別的復(fù)雜度绿语，個(gè)別情況是高級(jí)別復(fù)雜度且發(fā)生具有時(shí)序關(guān)系時(shí)秃症，可以將個(gè)別高級(jí)別復(fù)雜度均攤到低級(jí)別復(fù)雜度上。基本上均攤結(jié)果就等于低級(jí)別復(fù)雜度吕粹。

ps：區(qū)分平均時(shí)間復(fù)雜度和均攤時(shí)間復(fù)雜度

• 平均時(shí)間復(fù)雜度：代碼在不同情況下復(fù)雜度出現(xiàn)量級(jí)差別种柑，則用代碼所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值表示。
• 均攤時(shí)間復(fù)雜度：兩個(gè)條件滿足時(shí)使用：1）代碼在絕大多數(shù)情況下是低級(jí)別復(fù)雜度匹耕，只有極少數(shù)情況是高級(jí)別復(fù)雜度聚请，如hashmap查找元素時(shí)間復(fù)雜度 O(1)；2）低級(jí)別和高級(jí)別復(fù)雜度出現(xiàn)具有時(shí)序規(guī)律稳其。均攤結(jié)果一般都等于低級(jí)別復(fù)雜度驶赏。

1、冒泡排序

基本思想：每次此循環(huán)確定未排序的數(shù)組的最大值（每輪遍歷固定一個(gè)元素）欢际，出現(xiàn)逆序交換元素母市，通過比較元素的大小，將較大的數(shù)依次交換到最后面损趋。（或者每次尋找最小值，依次交換到最前邊）。

復(fù)雜度分析：時(shí)間復(fù)雜度O(N^2)浑槽，空間復(fù)雜度O(1)。

代碼實(shí)現(xiàn)：

public void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        // 優(yōu)化：設(shè)置標(biāo)志位
        int flag = 1;
        for (int j = 1; j < i; j++) {
            // 是穩(wěn)定排序桐玻，這里如果改成<=，那么就是不穩(wěn)定了
            if (arr[j] < arr[j - 1]) {
                // 出現(xiàn)逆序
                swap(arr, j, j - 1);  
                flag = 0;
            }
        }
        if (flag == 1) {
            // 已經(jīng)有序铣卡，直接退出
            return;
        }
    }
}
private void swap(int[] arr, int i, int j) {
   if (i == j) return;
   arr[i] ^= arr[j];
   arr[j] ^= arr[i];
   arr[i] ^= arr[j];
}

優(yōu)化思路：可以設(shè)置一個(gè)哨兵偏竟，如果一輪從前到后的比較沒有出現(xiàn)交換，那么這個(gè)數(shù)組已經(jīng)是有序數(shù)組了踊谋，那么后面再比較就沒有意義了，可以直接退出轿衔。

2睦疫、選擇排序

基本思想：在未排序序列中找到最小元素害驹，存放到排序序列起始位置。再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素蛤育，然后放到已排序序列的末尾裙秋。以此類推，直到所有元素均排序完畢缨伊。（或者每次在未排序的數(shù)組中找最大值摘刑，加入排序序列）

ps：類似雙指針中minIndex維護(hù)排序數(shù)組的最后一個(gè)元素。

復(fù)雜度分析：時(shí)間復(fù)雜度O(N^2)刻坊，空間復(fù)雜度O(1)枷恕。

代碼實(shí)現(xiàn)：

public void selectSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;  // 初始化最小值索引
        for (int j = i + 1; j < arr.length; i++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;  // 更新最小值索引
        }
        swap(arr, i, minIndex)
    }
}
private void swap(int[] arr, int i, int j) {
   if (i == j) return;
   arr[i] ^= arr[j];
   arr[j] ^= arr[i];
   arr[i] ^= arr[j];
}

3、插入排序

基本思想：通過構(gòu)建有序序列谭胚，對(duì)于未排序數(shù)據(jù)徐块，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入灾而『兀可以理解為玩撲克牌時(shí)的理牌；

ps：兩層for循環(huán)都是正向遍歷旁趟，插入時(shí)從已經(jīng)有序末尾依次進(jìn)行比較交換昼激。

復(fù)雜度分析：時(shí)間復(fù)雜度O(N^2)，空間復(fù)雜度O(1)。

注意：如果數(shù)組基本有序橙困，那么插入排序會(huì)更好瞧掺。因?yàn)椴迦肱判蛎看问沁x擇一個(gè)位置插入到有序的新數(shù)組中，如果數(shù)據(jù)基本有序的情況下凡傅，每次尋找插入位置的時(shí)間復(fù)雜度就基本上是O(1)了辟狈，那么總體的時(shí)間復(fù)雜度就可以是o(n)。

代碼實(shí)現(xiàn)：

public void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 1; i < arr.length; i++) {
        for (int j = i - 1; j > 0 && arr[j] > arr[j + 1]; j--) {
            // 從后向前遍歷已經(jīng)排序數(shù)組夏跷，尋找插入位置
            swap(arr, j, j + 1);  
        }
    }
}
private void swap(int[] arr, int i, int j) {
   if (i == j) return;
   arr[i] ^= arr[j];
   arr[j] ^= arr[i];
   arr[i] ^= arr[j];
}

優(yōu)化：進(jìn)行二分插入槽华，時(shí)間復(fù)雜度O(nlogn)硼莽。

4偏螺、希爾排序

基本思想：希爾排序是插入排序的一種高效率的實(shí)現(xiàn)套像，也叫縮小增量排序夺巩。先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序柳譬，待整個(gè)序列中的記錄基本有序時(shí)再對(duì)全體記錄進(jìn)行一次直接插入排序。

問題：增量的序列取法制跟？

關(guān)于取法，沒有統(tǒng)一標(biāo)準(zhǔn)聊记，但最后一步必須是1；因?yàn)椴煌娜》ㄉ婕皶r(shí)間復(fù)雜度不一樣踩身，具體了解可以參考《數(shù)據(jù)結(jié)構(gòu)與算法分析》；一般以length/2為算法峭弟。（再此以gap=gap*3+1為公式）

復(fù)雜度分析：時(shí)間復(fù)雜度O(N^3/2 )，最壞時(shí)間復(fù)雜度O(N^2)情臭，空間復(fù)雜度O(1)俯在。

代碼實(shí)現(xiàn)：

private static void sort(int[] array) {
    int n = array.length;
    int h = 1;
    while (h < n / 3) { //動(dòng)態(tài)定義間隔序列
          h = 3 * h + 1;
    }
     while (h >= 1) {
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && (array[j] < array[j - h]); j -= h) {
                int temp = array[j];
                array[j] = array[j - h];
                array[j-h]= temp;
            }
        }
        h /= 3;
    }
}

5跷乐、歸并排序

基本思想：將已有序的子序列合并，得到完全有序的序列浅侨；即先使每個(gè)子序列有序如输，再使子序列段間有序挨决。若將兩個(gè)有序表合并成一個(gè)有序表脖祈，稱為2-路歸并盖高。它使用了遞歸分治的思想席纽。簡(jiǎn)言之润梯，先遞歸的分解數(shù)組纺铭，再合并有序數(shù)組舶赔。

復(fù)雜度分析：時(shí)間復(fù)雜度O(NlogN)，空間復(fù)雜度O(N)疚鲤。

代碼實(shí)現(xiàn)：

public static void mergeSort(int[] arr) {  // 主函數(shù)
    if (arr == null || arr.length < 2) {
        return;
    }
    mergeSort(arr, 0, arr.length - 1);
}
//1.遞歸分解數(shù)組
public static void mergeSort(int[] arr, int l, int r) {  
    if (l == r) return;
    int m = l + ((r - l) >> 1);  //注：算數(shù)運(yùn)算符優(yōu)先級(jí)大于移位揩悄！
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);

    merge(arr, l, m, r);
}
//2.合并成有序數(shù)組
public static void merge(int[] arr, int l, int m, int r) {  
    int[] help = new int[r - l + 1];  
    int index = 0;
    int p1 = l, p2 = m + 1;

    while (p1 <= m && p2 <= r) {
        help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= m) {  //p2越界
        help[index++] = arr[p1++];
    }
    while (p2 <= r) {  //p1越界
        help[index++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[l + i] = help[i];   //遍歷臨時(shí)數(shù)組，拷貝到原數(shù)組（一定注意拷貝到原數(shù)組的下標(biāo)５磐Α０桶铩ｉ偶搿）
    }
}

優(yōu)化點(diǎn)：（1）已經(jīng)有序用押，直接返回蜻拨，不用合并（2）用同一個(gè)tmp數(shù)組（3）位運(yùn)算（4）小區(qū)間進(jìn)行插入排序

class Solution {

    // 列表大小大于或等于該值收夸，將優(yōu)先使用歸并排序卧惜，否則使用插入排序
    private static final int INSERTION_SORT_THRESHOLD = 7;

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        int[] tmp = new int[n];

        mergeSort(nums, 0, n - 1, tmp);
        return nums;
    }

    private void mergeSort(int[] nums, int left, int right, int[] tmp) {
        if (right - left <= INSERTION_SORT_THRESHOLD) {
            insertionSort(nums, left, right);
            return;
        }

        // int mid = left + (right - left) / 2;
        int mid = left + right >>> 1;
        mergeSort(nums, left, mid, tmp);
        mergeSort(nums, mid + 1, right, tmp);
        // 如果子區(qū)間本身有序手幢，則無需合并
        if (nums[mid] <= nums[mid + 1]) {
            return;
        }

        merge(nums, left, mid, right, tmp);
    }

    // 區(qū)間[left, right]進(jìn)行插入排序
    private void insertionSort(int[] nums, int left, int right) {
        for (int i = left + 1; i <= right; ++i) {
            // 待插入的元素
            int tmp = nums[i];
            int j = i;
            while (j > left && nums[j - 1] > tmp) {
                // 移動(dòng)數(shù)組元素找到插入位置
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = tmp;
        }
    }

    private void merge(int[] nums, int left, int mid, int right, int[] tmp) {
        System.arraycopy(nums, left, tmp, left, right - left + 1);

        int i = left;
        int j = mid + 1;

        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                nums[k] = tmp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = tmp[i];
                i++;
            } else if (tmp[i] <= tmp[j]) {
                // 注意寫成 < 就丟失了穩(wěn)定性（相同元素原來靠前的排序以后依然靠前）
                nums[k] = tmp[i];
                i++;
            } else {
                // tmp[i] > tmp[j]:先放較小的元素
                nums[k] = tmp[j];
                j++;
            }
        }
    }
}

6跺涤、隨機(jī)快速排序

基本思想：首先桶错，從數(shù)組中隨機(jī)挑出一個(gè)元素院刁，作為基準(zhǔn)值（pivot）退腥；然后，按照基準(zhǔn)進(jìn)行分區(qū)（partition）操作困鸥，最后澜术，遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序鸟废。

復(fù)雜度分析：時(shí)間復(fù)雜度O(NlogN)侮攀，空間復(fù)雜度O(N)兰英。

代碼實(shí)現(xiàn)：分區(qū)劃分的荷蘭國(guó)旗問題陨闹。

// 區(qū)域劃分：荷蘭國(guó)旗（三明治結(jié)構(gòu)）
public static int[] partition(int[] arr, int l, int r, int num) {
    int less = l - 1;
    int more = r + 1;
    while (l < more) {  //變量復(fù)用(l相當(dāng)于index)
        if (arr[l] < num) {
            swap(arr, ++less, l++);
        }else if (arr[l] > num) {
            swap(arr, l, --more);
        }else {
            l++;
        }
    }
    //返回等于區(qū)域
    return new int[] {less + 1, more - 1}; 
}
private void swap(int[] arr, int i, int j) {
   if (i == j) return;
   arr[i] ^= arr[j];
   arr[j] ^= arr[i];
   arr[i] ^= arr[j];
}

代碼實(shí)現(xiàn)：快速排序

public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
    if (l < r) {
        //優(yōu)化：取隨機(jī)數(shù)與最后一個(gè)數(shù)索引調(diào)換（做劃分值）
        swap(arr, l + (int)(Math.random() * (r - l + 1)), r);  
        int[] p = partition(arr, l, r);
        quickSort(arr, l, p[0] - 1);
        quickSort(arr, p[1] + 1, r);
    }
}
public static int[] partition(int[] arr, int l, int r) {
    int less = l - 1;
    int more = r;
    
    // 復(fù)用變量l，當(dāng)前遍歷位置
    while (l < more) {
        // 區(qū)間最右邊的元素做劃分值
        if (arr[l] < arr[r]) {
            swap(arr, ++less, l++); 
        } else if (arr[l] > arr[r]) {
            swap(arr, l, --more);
        } else {
            l++;
        }
    }
    // 用完元素君账，不要忘記歸位（劃分值）
    swap(arr, more, r);
    // 返回等于區(qū)域的邊界
    return new int[] {less + 1, more};
}

private void swap(int[] arr, int i, int j) {
   if (i == j) return;
   arr[i] ^= arr[j];
   arr[j] ^= arr[i];
   arr[i] ^= arr[j];
}

三數(shù)取中法優(yōu)化代碼：

/*函數(shù)作用：取待排序序列中l(wèi)ow乡数、mid净赴、high三個(gè)位置上數(shù)據(jù)玖翅，選取他們中間的那個(gè)數(shù)據(jù)作為樞軸*/  
int SelectPivotMedianOfThree(int arr[],int low,int high)  {  
    int mid = low + ((high - low) >> 1);//計(jì)算數(shù)組中間的元素的下標(biāo)  
    //使用三數(shù)取中法選擇樞軸  
    if (arr[mid] > arr[high]) {  
        swap(arr[mid],arr[high]);  
    }  
    if (arr[low] > arr[high]) {  
        swap(arr[low],arr[high]);  
    }  
    if (arr[mid] > arr[low]) {  
        swap(arr[mid],arr[low]);  
    }  
    //此時(shí)，arr[mid] <= arr[low] <= arr[high]  
    return arr[low];  
    //low的位置上保存這三個(gè)位置中間的值  
    //分割時(shí)可以直接使用low位置的元素作為樞軸审姓，而不用改變分割函數(shù)了  
} 

快排的優(yōu)化思路：

基準(zhǔn)值選饶隆：

• 隨機(jī)選取劃分基準(zhǔn)值pivot ：l + (int)(Math.random() * (r - l + 1))
• 三數(shù)取中法取劃分基準(zhǔn)值pivot酬姆，但處理不了重復(fù)數(shù)組

其他優(yōu)化：

• 對(duì)于小區(qū)間切換到插入排序(對(duì)于存在很多重復(fù)序列的情況辞色，分割成小區(qū)間)
• 在一次排序后相满，可以將與基準(zhǔn)值相等的數(shù)放在一起立美，在下次分割時(shí)可以不考慮這些數(shù)。(聚集相等的元素)

7碌更、堆排序

基本思想：堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)旭绒。

復(fù)雜度分析：時(shí)間復(fù)雜度O(NlogN)谆棱，空間復(fù)雜度O(1)。

代碼實(shí)現(xiàn)：

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        heapInsert(arr, i);  //0-i之間形成大根堆
    }
    int size = arr.length;
    swap(arr, 0, --size);
    while (size > 0) {
        heapify(arr, 0, size);
        swap(arr, 0, --size);
    }
}
//轉(zhuǎn)換為大根堆,添加元素
public static void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) {
       swap(arr, index, (index - 1) / 2);
       index = (index - 1) / 2;
    }
}
//使用異或當(dāng)(即位運(yùn)算交換兩個(gè)數(shù))i=j時(shí)可能會(huì)出錯(cuò)
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
//當(dāng)出現(xiàn)某個(gè)位置的數(shù)值改變?cè)趺凑{(diào)整
public static void heapify(int[] arr, int index, int heapSize) {
    int left = index * 2 + 1;
    while (left < heapSize) {
        //找最大值的下標(biāo) (算術(shù)運(yùn)算符的優(yōu)先級(jí)大于關(guān)系運(yùn)算符)
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        //左右孩子的最大值和父節(jié)點(diǎn)比較
        largest = arr[largest] > arr[index] ? largest : index;
        if (index == largest) {
            break;
        }
        swap(arr, index, largest);
        index = largest;
        left = index * 2 + 1;
    }
}

8个从、計(jì)數(shù)排序

基本思想：將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中嗦锐。 作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)碳默。

• 找出待排序的數(shù)組中最大和最小的元素缘眶；
• 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)该抒，存入數(shù)組C的第i項(xiàng)顶燕；
• 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）犯助；
• 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)剂买，每放一個(gè)元素就將C(i)減去1瞬哼。

復(fù)雜度分析：時(shí)間復(fù)雜度O(N + K)坐慰，空間復(fù)雜度O(N + K)结胀。

代碼實(shí)現(xiàn)：

/**
 * 輸入數(shù)組的元素都是介于0..k之間的
 * @param data 待排序數(shù)組
 * @param k 最大元素
 * @return 排序結(jié)果
 */
public static int[] countingSort(int[] data, int k) {
    // 存放臨時(shí)數(shù)據(jù)的數(shù)組tmp，初始元素都是0秸抚；k為數(shù)組中最大元素
    int[] tmp = new int[k + 1];

    // 計(jì)算數(shù)組中每個(gè)元素i出現(xiàn)的次數(shù)歹垫，存入數(shù)組tmp中的第i項(xiàng)排惨，即原數(shù)組中的元素值為tmp數(shù)組中的下標(biāo)
    for (int i = 0; i <= data.length - 1; i++) {
        tmp[data[i]]++;
    }
    // 計(jì)算數(shù)組中小于等于每個(gè)元素的個(gè)數(shù),即從tmp中的第一個(gè)元素開始暮芭，每一項(xiàng)和前一項(xiàng)相加
    for (int j = 1; j <= k; j++) {
        tmp[j] = tmp[j] + tmp[j - 1];
    }
    // result數(shù)組用來來存放排序結(jié)果
    int[] result = new int[data.length];
    for (int i = data.length - 1; i >= 0; i--) {
        result[tmp[data[i]] - 1] = data[i];
        tmp[data[i]]--;
    }
    return result;
}

9蠢沿、桶排序

基本思想：桶排序是計(jì)數(shù)排序的升級(jí)版舷蟀。它利用了函數(shù)的映射關(guān)系扫步，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定河胎。桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布游岳，將數(shù)據(jù)分到有限數(shù)量的桶里胚迫，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排）访锻。

• 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；
• 遍歷輸入數(shù)據(jù)龟虎，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去遣总；
• 對(duì)每個(gè)不是空的桶進(jìn)行排序；
• 從不是空的桶里把排好序的數(shù)據(jù)拼接起來古涧。

復(fù)雜度分析：時(shí)間復(fù)雜度O(N + K)，最壞時(shí)間復(fù)雜度O(N^2)算芯，空間復(fù)雜度O(N + K)熙揍。

代碼實(shí)現(xiàn)：

public static void bucketSort(double array[]) {
    int length = array.length;
    ArrayList arrList[] = new ArrayList[length];
    for (int i = 0; i < length; i++) {
        //0.7到0.79放在第8個(gè)桶里,編號(hào)7；第一個(gè)桶放0到0.09
        int temp = (int) Math.floor(10 * array[i]);
        if (null == arrList[temp])
            arrList[temp] = new ArrayList();
        arrList[temp].add(array[i]);
    }
    // 對(duì)每個(gè)桶中的數(shù)進(jìn)行插入排序
    for (int i = 0; i < length; i++) {
        if (null != arrList[i]) {
            Collections.sort(arrList[i]);
        }
    }
    int count = 0;
    for (int i = 0; i < length; i++) {
        if (null != arrList[i]) {
            Iterator iter = arrList[i].iterator();
            while (iter.hasNext()) {
                Double d = (Double) iter.next();
                array[count] = d;
                count++;
            }
        }
    }
}

10、基數(shù)排序

基本思想：基數(shù)排序是按照低位先排序饺汹，然后收集兜辞；再按照高位排序逸吵，然后再收集；依次類推压语，直到最高位啸罢。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序胎食，再按高優(yōu)先級(jí)排序扰才。最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前厕怜。

• 取得數(shù)組中的最大數(shù)衩匣，并取得位數(shù)；
• arr為原始數(shù)組粥航，從最低位開始取每個(gè)位組成radix數(shù)組琅捏；
• 對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；

復(fù)雜度分析：時(shí)間復(fù)雜度O(N * K)，空間復(fù)雜度O(N + K)。

代碼實(shí)現(xiàn)：

private static void radixSort(int[] array,int radix, int distance) {
    int length = array.length;
    int[] temp = new int[length];
    int[] count = new int[radix];
    int divide = 1;

    for (int i = 0; i < distance; i++) {

        System.arraycopy(array, 0,temp, 0, length);
        Arrays.fill(count, 0);

        for (int j = 0; j < length; j++) {
            int tempKey = (temp[j]/divide)%radix;
            count[tempKey]++;
        }

        for (int j = 1; j < radix; j++) {
            count [j] = count[j] + count[j-1];
        }
        for (int j = length - 1; j >= 0; j--) {
            int tempKey = (temp[j]/divide)%radix;
            count[tempKey]--;
            array[count[tempKey]] = temp[j];
        }
        divide = divide * radix;
    }
}

應(yīng)用場(chǎng)景分析：

（1）若數(shù)據(jù)規(guī)模較小（如n <= 50），可以使用簡(jiǎn)單的直接插入排序或者直接選擇排序（不穩(wěn)定）窍仰。
（2）若文件的初始狀態(tài)基本有序，排序關(guān)鍵字移動(dòng)次數(shù)較少族沃，則應(yīng)選用直接插入或冒泡排序?yàn)橐耍?br> （3）若文件初始狀態(tài)隨機(jī)分布漓糙，則應(yīng)選用快速排序?yàn)橐俗肀睿骄鶗r(shí)間復(fù)雜度O(nlogn)；
（4）若數(shù)據(jù)規(guī)模較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlogn)的排序方法：快速排序、堆排序或歸并排序；

• 快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；雖然可能退化為O(N^2)，但這種概率很小缘屹。
  ps：堆排序每次取一個(gè)最大值和堆底部的數(shù)據(jù)交換犁享，重新篩選堆凤巨，把堆頂?shù)腦調(diào)整到位伸刃，有很大可能是依舊調(diào)整到堆的底部（堆的底部X顯然是比較小的數(shù)，才會(huì)在底部），然后再次和堆頂最大值交換凄吏，再調(diào)整下來蚤吹，可以說堆排序做了許多無用功拱她。堆排序過程里的交換跟快排過程里的交換雖然都是常量時(shí)間，但是常量時(shí)間差很多柱锹。
• 堆排序所需的輔助空間少于快速排序宙彪，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況。堆排序和快速排序都是不穩(wěn)定的乃戈。
• 若要求排序穩(wěn)定韵卤，則可選用歸并排序（外部排序）月而。從單個(gè)記錄起進(jìn)行兩兩歸并的排序算法并不值得提倡，通趁愠眨可以將它和直接插入排序結(jié)合在一起使用。推薦：先利用直接插入排序求得較長(zhǎng)的有序子文件，然后再兩兩歸并之榜配。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定的屎蜓，所以改進(jìn)后的歸并排序仍是穩(wěn)定的。