目錄

什么是排序??

什么是穩(wěn)定性??

交換排序的基本思想???

一、冒泡排序??

1、基本思想??

2、實(shí)現(xiàn)代碼??

?3、代碼優(yōu)化??

Ⅰ、 ??冒泡排序的優(yōu)化1

?Ⅱ、??冒泡排序的優(yōu)化2

4、優(yōu)缺點(diǎn)??

5、算法分析??

6、 應(yīng)用場景??

二、快速排序??

1、基本思想??

2、代碼實(shí)現(xiàn)（遞歸與非遞歸? 三種方法實(shí)現(xiàn)）??

?Ⅰ、??遞歸? hoare版本(左右指針法)

?Ⅱ、???挖坑法

Ⅲ、??前后指針法

Ⅳ、???非遞歸

?3、代碼優(yōu)化（三種優(yōu)化）??

Ⅰ、

Ⅱ、優(yōu)化三

4、優(yōu)缺點(diǎn)??

5、算法分析??

?6、應(yīng)用場景??

選擇排序的基本思想??

一、直接選擇排序??

1、基本思想??

?2、代碼實(shí)現(xiàn)??

3、代碼優(yōu)化??

?4、優(yōu)缺點(diǎn)??

5、算法分析??

?6、適應(yīng)場景??

?二、堆排序???

1、堆??

?2、基本思想??

?3、堆的存儲(chǔ)方式??

4、堆的shift up和shift down??

Ⅰ、shift up：向一個(gè)最大堆中添加元素??

Ⅱ、shift down：從一個(gè)最大堆中取出一個(gè)元素只能取出最大優(yōu)先級(jí)的元素，也就是根節(jié)點(diǎn)??

?5、堆的插入與刪除??

Ⅰ、插入??

?Ⅱ、刪除??

?6、建堆的時(shí)間復(fù)雜度??

?7、代碼（建大根堆小根堆，入隊(duì)出隊(duì)）??

8、總結(jié)??

插入排序

一、直接插入排序

1、 基本思想??

?2、代碼實(shí)現(xiàn)??

3、代碼優(yōu)化??

Ⅰ、??插入排序優(yōu)化（二分）

?Ⅱ、??插入排序優(yōu)化

?4、優(yōu)缺點(diǎn)??

5、總結(jié)??

二、希爾排序??

1、基本思路??

?2、代碼實(shí)現(xiàn)??

?3、代碼優(yōu)化??

Ⅰ、??希爾排序優(yōu)化（二分）

?Ⅱ、??

4、優(yōu)缺點(diǎn)??

?5、總結(jié)??

計(jì)數(shù)排序??

1、基本思想??

2、代碼實(shí)現(xiàn)??

?3、優(yōu)缺點(diǎn)??

4、算法分析??

?5、應(yīng)用場景??

歸并排序??

1、基本思路??

?2、代碼實(shí)現(xiàn)??

Ⅰ、??遞歸寫法

Ⅱ、??迭代寫法

3、代碼優(yōu)化??

Ⅰ、??對(duì)于短數(shù)組使用插入排序

總結(jié)??

??歸并排序解決海量數(shù)據(jù)的排序問題

八大排序總結(jié)??

1、初始數(shù)據(jù)集的排列順序?qū)λ惴ǖ男阅軣o影響的有:

2、每一次排序之后都能確定至少一個(gè)元素位置的排序方法包括：

3、不能至少確定一個(gè)元素的位置的方法包括：

4、請(qǐng)簡單介紹一下冒泡排序的原理和實(shí)現(xiàn)方式：

5、請(qǐng)介紹快速排序的實(shí)現(xiàn)方式以及時(shí)間復(fù)雜度

6、請(qǐng)介紹堆排序的原理和實(shí)現(xiàn)方式。

7、插入排序和選擇排序的區(qū)別是什么？

8、請(qǐng)介紹歸并排序的實(shí)現(xiàn)方式以及時(shí)間復(fù)雜度。

什么是排序??

所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。

什么是穩(wěn)定性??

假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序保持 不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn) 定的；否則稱為不穩(wěn)定的。

交換排序的基本思想???

交換排序是基于比較的排序算法，其主要思想是不斷比較相鄰兩個(gè)元素的大小，將較小的元素不斷交換到數(shù)組的前面，較大的元素不斷交換到數(shù)組的后面，直到整個(gè)數(shù)組有序?yàn)橹埂?/p>

一、冒泡排序??

1、基本思想??

冒泡排序的基本思想是通過比較相鄰的兩個(gè)元素的大小，將較小的元素不斷交換到數(shù)組的前面，較大的元素不斷交換到數(shù)組的后面。具體地，排序過程如下：

1. 比較相鄰的兩個(gè)元素，如果前一個(gè)元素比后一個(gè)元素大，則交換這兩個(gè)元素的位置。
2. 不斷重復(fù)第一步，直到將最大的元素交換到數(shù)組的最后一個(gè)位置。
3. 重復(fù)上述操作，每次將待排序的數(shù)組長度減一，直到整個(gè)數(shù)組有序?yàn)橹埂?/li>

2、實(shí)現(xiàn)代碼??

    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

?3、代碼優(yōu)化??

Ⅰ、 ??冒泡排序的優(yōu)化1

如果一次循環(huán)中沒有發(fā)生交換，則說明數(shù)組已經(jīng)有序，可以結(jié)束排序。

?優(yōu)化前：

import java.util.Arrays;

public class Main {
    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
                System.out.print("第 "+(i+1)+" 趟，第 "+(j+1)+" 次比較后的結(jié)果：");
                System.out.println(Arrays.toString(arr));
            }
        }
    }
    public static void main(String[] args) {
        int[] arr={2,9,7,15,49,10};
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
    }
}

?

可以看到上方的代碼打印，其實(shí)有不少循環(huán)過程未發(fā)生任何變化，且已排序完成，所以此時(shí)應(yīng)該提前退出循環(huán)。

優(yōu)化后：

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

?

?可以看到優(yōu)化之后明顯減少了排序的次數(shù)。

?Ⅱ、??冒泡排序的優(yōu)化2

記錄每一次循環(huán)中最后一次交換的位置lastIndex，在下一次循環(huán)中，只需要比較到lastIndex的位置即可，因?yàn)閘astIndex之后的元素已經(jīng)有序。

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    int lastIndex = 0;
    int k = n - 1;
    for (int i = 0; i < n - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < k; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
                lastIndex = j;
            }
        }
        if (!flag) {
            break;
        }
        k = lastIndex;
    }
}

4、優(yōu)缺點(diǎn)??

冒泡排序的主要優(yōu)點(diǎn)是代碼簡單易懂，實(shí)現(xiàn)方便，適用于小規(guī)模的數(shù)據(jù)排序。冒泡排序的主要缺點(diǎn)是時(shí)間復(fù)雜度較高，為 O(n2)，不適用于大規(guī)模數(shù)據(jù)的排序。

5、算法分析??

1、時(shí)間復(fù)雜度

在最壞情況下，即待排序的序列是逆序的情況下，冒泡排序需要比較和交換的次數(shù)最多。在這種情況下，冒泡排序的時(shí)間復(fù)雜度為O(n2)。在最好情況下，即待排序的序列已經(jīng)有序的情況下，冒泡排序只需要進(jìn)行一次遍歷，時(shí)間復(fù)雜度為O(n)。

因此，冒泡排序的平均時(shí)間復(fù)雜度為O(n2)。雖然冒泡排序的時(shí)間復(fù)雜度較高，但對(duì)于小規(guī)模的數(shù)據(jù)排序，冒泡排序仍然是一種簡單有效的排序算法。

2、空間復(fù)雜度

冒泡排序是一種原地排序算法，不需要額外的空間進(jìn)行排序。因此，冒泡排序的空間復(fù)雜度為O(1)。

3、穩(wěn)定性

冒泡排序是一種穩(wěn)定的排序算法。由于冒泡排序只會(huì)交換相鄰元素中大小關(guān)系不符合要求的元素，因此相同元素的相對(duì)位置不會(huì)發(fā)生變化，保證了冒泡排序的穩(wěn)定性。

6、 應(yīng)用場景??

1. 教學(xué)和學(xué)習(xí)：冒泡排序是一種很好理解的排序算法，可以作為初學(xué)者學(xué)習(xí)排序算法的入門算法，幫助理解算法的基本思想。

2. 小規(guī)模數(shù)組排序：對(duì)于小規(guī)模的待排序數(shù)組，冒泡排序的效率可能比較高，因?yàn)樗某?shù)因子較小。

3. 數(shù)據(jù)基本有序的排序：如果待排序數(shù)組中的元素已經(jīng)基本有序，即每個(gè)元素與它前后的元素相差不大，那么冒泡排序的效率會(huì)比較高，因?yàn)樗趯?duì)已排序的部分不會(huì)進(jìn)行比較和交換。

總的來說，冒泡排序在實(shí)際應(yīng)用中的使用場景較為有限，更多的是用于教學(xué)和算法實(shí)現(xiàn)方面。

二、快速排序??

快速排序是一種不穩(wěn)定的排序算法，其基本原理是通過選取一個(gè)基準(zhǔn)元素，將數(shù)組劃分為兩個(gè)子數(shù)組，分別對(duì)子數(shù)組進(jìn)行排序，最終實(shí)現(xiàn)整個(gè)數(shù)組的有序排列。快速排序的時(shí)間復(fù)雜度為O(nlogn)，是一種高效的排序算法。

1、基本思想??

快速排序的基本思想是：選擇一個(gè)基準(zhǔn)元素，將數(shù)組劃分為兩個(gè)子數(shù)組，比基準(zhǔn)元素小的元素放在左邊，比基準(zhǔn)元素大的元素放在右邊，然后分別對(duì)左右子數(shù)組進(jìn)行排序，最終實(shí)現(xiàn)整個(gè)數(shù)組的有序排列。具體地，排序過程如下：

1. 選擇一個(gè)基準(zhǔn)元素；
2. 將數(shù)組劃分為兩個(gè)子數(shù)組，比基準(zhǔn)元素小的元素放在左邊，比基準(zhǔn)元素大的元素放在右邊；
3. 分別對(duì)左右子數(shù)組進(jìn)行排序，重復(fù)上述操作；
4. 直到整個(gè)數(shù)組有序?yàn)橹埂?/li>

2、代碼實(shí)現(xiàn)（遞歸與非遞歸? 三種方法實(shí)現(xiàn)）??

?Ⅰ、??遞歸? hoare版本(左右指針法)

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int i = left, j = right;
    int pivot = arr[left]; // 選擇數(shù)組的第一個(gè)元素作為基準(zhǔn)

    while (i < j) {
        while (i < j && arr[j] >= pivot) j--; // 從右往左找到第一個(gè)小于pivot的數(shù)
        while (i < j && arr[i] <= pivot) i++; // 從左往右找到第一個(gè)大于pivot的數(shù)
        if (i < j) swap(arr, i, j); // 交換這兩個(gè)數(shù)
    }

    swap(arr, left, i); // 把基準(zhǔn)放到它正確的位置上，此時(shí)i=j

    quickSort(arr, left, i - 1); // 遞歸處理左半部分
    quickSort(arr, i + 1, right); // 遞歸處理右半部分
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

?網(wǎng)上一個(gè)經(jīng)典的hoare版快排GIF（一趟快排）

?Ⅱ、???挖坑法

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int i = left, j = right;
    int pivot = arr[left]; // 挖一個(gè)坑，選擇數(shù)組的第一個(gè)元素作為基準(zhǔn)

    while (i < j) {
        while (i < j && arr[j] >= pivot) j--; // 從右往左找到第一個(gè)小于pivot的數(shù)
        if (i < j) arr[i++] = arr[j]; // 把該數(shù)填到之前挖出來的坑中

        while (i < j && arr[i] <= pivot) i++; // 從左往右找到第一個(gè)大于pivot的數(shù)
        if (i < j) arr[j--] = arr[i]; // 把該數(shù)填到剛才挖出的坑中
    }

    arr[i] = pivot; // 將最初挖出來的坑填回去，此時(shí)i=j

    quickSort(arr, left, i - 1); // 遞歸處理左半部分
    quickSort(arr, i + 1, right); // 遞歸處理右半部分
}

Ⅲ、??前后指針法

第一種寫法：

public static void quickSort(int[] arr, int start, int end) {
    if (start >= end) return;

    int pivot = arr[start]; // 選擇數(shù)組的第一個(gè)元素作為基準(zhǔn)

    int i = start, j = end;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--; // 從右往左找到第一個(gè)小于pivot的數(shù)
        while (i < j && arr[i] <= pivot) i++; // 從左往右找到第一個(gè)大于pivot的數(shù)
        if (i < j) swap(arr, i, j); // 交換這兩個(gè)數(shù)
    }

    swap(arr, start, i); // 把基準(zhǔn)放到它正確的位置上，此時(shí)i=j

    quickSort(arr, start, i - 1); // 排序左半部分
    quickSort(arr, i + 1, end); // 排序右半部分
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

第二種寫法：

public static void quickSort(int[] arr, int start, int end) {
    if (start >= end) return;

    int pivot = arr[start]; // 選擇數(shù)組的第一個(gè)元素作為基準(zhǔn)

    int i = start + 1, j = start + 1; // i和j都從start+1開始
    while (j <= end) {
        if (arr[j] < pivot) {
            swap(arr, i, j);
            i++;
        }
        j++;
    }

    swap(arr, start, i - 1); // 把樞軸放到它正確的位置上

    quickSort(arr, start, i - 2); // 排序左半部分
    quickSort(arr, i, end); // 排序右半部分
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

第一種寫法中，i和j都從start開始，用兩個(gè)while循環(huán)找到需要交換的數(shù)，并且是在i和j相遇時(shí)才交換。

第二種寫法中，i和j都從start+1開始，只有當(dāng)arr[j]<pivot時(shí)才交換，交換后把i向前移動(dòng)一位，最終i停留的位置就是基準(zhǔn)的正確位置。?

Ⅳ、???非遞歸

public static void quickSort(int[] arr) {
    Stack<Integer> stack = new Stack<>();
    int left = 0, right = arr.length - 1;
    stack.push(left);
    stack.push(right);
    while (!stack.isEmpty()) {
        right = stack.pop();
        left = stack.pop();
        int pivot = partition(arr, left, right);
        // 將左子數(shù)組入棧
        if (left < pivot - 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        // 將右子數(shù)組入棧
        if (right > pivot + 1) {
            stack.push(pivot + 1);
            stack.push(right);
        }
    }
}

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        if (i < j) arr[i++] = arr[j];
        while (i < j && arr[i] <= pivot) i++;
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    return i;
}

使用一個(gè)Stack數(shù)據(jù)結(jié)構(gòu)來模擬遞歸過程，實(shí)現(xiàn)非遞歸的快速排序。我們首先將數(shù)組的左邊界和右邊界入棧，然后從棧中取出左邊界和右邊界，進(jìn)行劃分?jǐn)?shù)組的操作。劃分完成后，將左子數(shù)組和右子數(shù)組的邊界入棧，繼續(xù)進(jìn)行處理，直到棧為空。

非遞歸的快速排序算法的時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(logn)，效率與遞歸版本的快速排序相當(dāng)。

?3、代碼優(yōu)化（三種優(yōu)化）??

Ⅰ、

1. 優(yōu)化1：如果待排序數(shù)組的長度小于某個(gè)常數(shù)，可以使用插入排序來替代快速排序。因?yàn)閷?duì)于小規(guī)模的數(shù)據(jù)，插入排序的效率要高于快速排序。這個(gè)常數(shù)的取值可以根據(jù)實(shí)際情況進(jìn)行調(diào)整。

2. 優(yōu)化2：隨機(jī)選擇基準(zhǔn)點(diǎn)，避免數(shù)組已經(jīng)有序或近似有序的情況下時(shí)間復(fù)雜度退化。在實(shí)際應(yīng)用中，數(shù)組的分布情況是不可預(yù)知的，如果固定選擇第一個(gè)或最后一個(gè)元素作為基準(zhǔn)點(diǎn)，那么在一些特殊情況下，快速排序的效率會(huì)變得非常低。因此，我們可以隨機(jī)選擇一個(gè)元素作為基準(zhǔn)點(diǎn)，避免這種情況的發(fā)生。

   public static void quickSort(int[] arr, int left, int right) {
       // 遞歸終止條件
       if (left >= right) return;
       // 優(yōu)化1：如果待排序數(shù)組的長度小于某個(gè)常數(shù)，可以使用插入排序
       if (right - left + 1 <= 10) {
           insertionSort(arr, left, right);
           return;
       }
       int pivot = partition(arr, left, right);  // 劃分?jǐn)?shù)組
       quickSort(arr, left, pivot - 1);  // 遞歸處理左子數(shù)組
       quickSort(arr, pivot + 1, right);  // 遞歸處理右子數(shù)組
   }
   
   public static int partition(int[] arr, int left, int right) {
       // 優(yōu)化2：隨機(jī)選擇基準(zhǔn)點(diǎn)，避免數(shù)組已經(jīng)有序或近似有序的情況下時(shí)間復(fù)雜度退化
       int pivot = arr[left + new Random().nextInt(right - left + 1)];
       int i = left, j = right;
       while (i < j) {
           while (i < j && arr[j] >= pivot) j--;
           if (i < j) arr[i++] = arr[j];
           while (i < j && arr[i] <= pivot) i++;
           if (i < j) arr[j--] = arr[i];
       }
       arr[i] = pivot;
       return i;
   }
   
   public static void insertionSort(int[] arr, int left, int right) {
       for (int i = left + 1; i <= right; i++) {
           int temp = arr[i];
           int j = i - 1;
           while (j >= left && arr[j] > temp) {
               arr[j + 1] = arr[j];
               j--;
           }
           arr[j + 1] = temp;
       }
   }

???優(yōu)化后的快速排序算法的時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(logn)，效率比未優(yōu)化的快速排序算法更高。

Ⅱ、優(yōu)化三

使用三數(shù)取中法來選擇基準(zhǔn)元素。然后使用兩個(gè)指針 i 和 j 分別從左和右開始掃描數(shù)組，尋找需要交換的元素，最后將數(shù)組分成了兩部分進(jìn)行遞歸排序。

  public static void quicksort(int[] arr) {
            sort(arr, 0, arr.length-1);
        }

        private static void sort(int[] arr, int left, int right) {
            if (left >= right)
                return;

            // 選取樞軸元素
            int mid = left + (right - left) / 2;
            if (arr[right] < arr[left])
                swap(arr, left, right);
            if (arr[mid] < arr[left])
                swap(arr, mid, left);
            if (arr[right] < arr[mid])
                swap(arr, right, mid);

            int pivot = arr[mid];
            int i = left, j = right;
            while (true) {
                while (arr[i] < pivot)
                    i++;

                while (arr[j] > pivot)
                    j--;

                if (i >= j)
                    break;

                swap(arr, i, j);
                i++;
                j--;
            }

            sort(arr, left, i-1);
            sort(arr, i, right);
        }

        private static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

4、優(yōu)缺點(diǎn)??

快速排序的主要優(yōu)點(diǎn)是時(shí)間復(fù)雜度較低，為 O(nlogn)，適用于大規(guī)模數(shù)據(jù)的排序?？焖倥判虻闹饕秉c(diǎn)是不穩(wěn)定，可能會(huì)改變相同元素的相對(duì)位置。

5、算法分析??

1、時(shí)間復(fù)雜度

快速排序的時(shí)間復(fù)雜度為O(nlogn)，其中n為待排序數(shù)組的長度。最壞情況下，快速排序的時(shí)間復(fù)雜度為O(n^2)，但這種情況出現(xiàn)的概率很小，可以通過一些優(yōu)化措施來避免。

2、空間復(fù)雜度

快速排序的空間復(fù)雜度取決于遞歸棧的深度，在最壞情況下，遞歸棧的深度為O(n)，因此快速排序的空間復(fù)雜度為O(n)。但是，在一些實(shí)現(xiàn)中，可以使用非遞歸的方式來實(shí)現(xiàn)快速排序，從而避免遞歸棧帶來的空間開銷。

3、穩(wěn)定性

快速排序是一種不穩(wěn)定的排序算法。因?yàn)樵谂判蜻^程中，可能會(huì)交換相同元素的位置，從而導(dǎo)致相同元素的相對(duì)順序被改變。例如，對(duì)于數(shù)組[3, 2, 2, 1]，如果選擇第一個(gè)元素3作為基準(zhǔn)元素，那么經(jīng)過第一次劃分后，數(shù)組變成了[1, 2, 2, 3]，其中兩個(gè)2的相對(duì)順序被改變了。

?6、應(yīng)用場景??

1. 大規(guī)模數(shù)據(jù)排序：快速排序的時(shí)間復(fù)雜度為 O(nlogn)，在大規(guī)模數(shù)據(jù)排序時(shí)表現(xiàn)優(yōu)秀。

2. 數(shù)據(jù)重復(fù)性較少的排序：在排序的數(shù)據(jù)中，如果存在大量重復(fù)的元素，那么快速排序的效率會(huì)受到影響，因?yàn)檫@樣會(huì)增加比較和交換的次數(shù)。

3. 對(duì)數(shù)據(jù)隨機(jī)性要求不高的排序：由于快速排序的分區(qū)過程是基于一個(gè)基準(zhǔn)元素來完成的，因此如果待排序數(shù)據(jù)的分布比較隨機(jī)，那么快速排序的效率會(huì)很高。

??總的來說，快速排序是一種高效的排序算法，在數(shù)據(jù)量較大、數(shù)據(jù)分布比較隨機(jī)、重復(fù)性較少的場景中表現(xiàn)優(yōu)秀，是一種很好的排序算法選擇。

選擇排序的基本思想??

將排序序列分為有序區(qū)和無序區(qū)，每一趟排序從無序區(qū)中選出最小的元素放在有序區(qū)的最后，從而擴(kuò)大有序區(qū)，直到全部元素有序?yàn)橹埂?/p>

一、直接選擇排序??

1、基本思想??

第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R[1]~R[n-1]中選取最小值，與R[1]交換，....，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，.....，第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換，總共通過n-1次，得到一個(gè)按排序碼從小到大排列的有序序列。

??可以通過看下面GIF來簡單了解直接選擇排序的過程：

?

?2、代碼實(shí)現(xiàn)??

import java.util.Arrays;

public class Main {
    public static void selectSort(int[] arr){
        //防止arr數(shù)組為空或者arr只有一個(gè)數(shù)，不用進(jìn)行排序
        if (arr == null || arr.length < 2) {
            return;
        }
        /*每次要進(jìn)行比較的兩個(gè)數(shù)，的前面那個(gè)數(shù)的下標(biāo)*/
        for (int i = 0; i < arr.length - 1; i++) {
            //min變量保存該趟比較過程中，最小元素所對(duì)應(yīng)的索引，
            //先假設(shè)前面的元素為最小元素
            int min = i;
            /*每趟比較，將前面的元素與其后的元素逐個(gè)比較*/
            for (int j = i + 1; j < arr.length; j++) {
                //如果后面的元素小，將后面元素的索引極為最小值的索引
                if(arr[j] < arr[min]) {
                    min = j;
                }
            }
            //然后交換此次查找到的最小值和原始的最小值
            swap(arr, i, min);
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr={9, 8, 6, 29, 10, 7, 37, 48};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

3、代碼優(yōu)化??

選擇排序的優(yōu)化引入的二分的思想，前面是找到最小的值往前面放，現(xiàn)在在一趟循環(huán)中同時(shí)找到最大最小值，將最小值放入頭，最大值放入尾。

import java.util.Arrays;

public class Main {
    public static void SelectSort(int[] arr){
        // find the max and min num in an iteration
        int n = arr.length;
        for(int i = 0;i<n;i++){
            int min = i;
            int max = n-1;

            for(int j = i;j<n;j++){
                if (arr[j]<arr[min]){
                    min = j;
                }
                if (arr[j]>arr[max]){
                    max = j;
                }
            }
            swap(arr,i,min);
            // 防止i的位置為最大值，然后被最小值換了，所以檢查一下
            if (max == i){
                max = min;
            }
            swap(arr,n-1,max);

            n = n-1;

        }
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr={9, 8, 6, 29, 10, 7, 37, 48};
        SelectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

?4、優(yōu)缺點(diǎn)??

優(yōu)點(diǎn)：

1. 實(shí)現(xiàn)簡單，易于理解和編寫。

2. 內(nèi)存占用小，不需要額外的存儲(chǔ)空間。

3. 適用于小規(guī)模的數(shù)據(jù)排序。

缺點(diǎn)：

1. 時(shí)間復(fù)雜度較高，平均時(shí)間復(fù)雜度為O(n^2)，在數(shù)據(jù)規(guī)模較大時(shí)效率低下。

2. 排序過程中不穩(wěn)定，可能導(dǎo)致相同元素的相對(duì)位置發(fā)生變化。

3. 交換次數(shù)較多，對(duì)于大量的數(shù)據(jù)交換次數(shù)會(huì)增加，導(dǎo)致效率下降。

4. 不適用于鏈?zhǔn)浇Y(jié)構(gòu)，因?yàn)殒準(zhǔn)浇Y(jié)構(gòu)不支持隨機(jī)訪問。

5、算法分析??

1、時(shí)間復(fù)雜度

在插入排序中，當(dāng)待排序序列是有序時(shí)，是最優(yōu)的情況，只需當(dāng)前數(shù)跟前一個(gè)數(shù)比較一下就可以了，這時(shí)一共需要比較n- 1次，時(shí)間復(fù)雜度為O(n)。最壞的情況是待排序數(shù)組是逆序的，此時(shí)需要比較次數(shù)最多，總次數(shù)記為：1+2+3+…+N-1，所以，插入排序最壞情況下的時(shí)間復(fù)雜度為O(n^2)。平均來說，array[1…j-1]中的一半元素小于array[j]，一半元素大于array[j]。插入排序在平均情況運(yùn)行時(shí)間與最壞情況運(yùn)行時(shí)間一樣，是O(n^2)。

2、空間復(fù)雜度

不需要額外的空間進(jìn)行排序。因此空間復(fù)雜度為O(1)。

3、穩(wěn)定性：

不穩(wěn)定，因?yàn)榕判蛐蛄袨椋?，5，1）,第一趟排序之后（1，5，5），這可以很清楚的看到兩個(gè)5的相對(duì)位置發(fā)生了變化。

?6、適應(yīng)場景??

1. 數(shù)據(jù)規(guī)模較小，不超過幾千個(gè)元素。

2. 數(shù)據(jù)分布比較均勻，不存在大量相同的元素。

3. 內(nèi)存空間有限，不能使用其他高級(jí)排序算法。

4. 數(shù)據(jù)元素之間的比較操作比較簡單，可以快速進(jìn)行比較。

5. 對(duì)于穩(wěn)定性要求不高的場合，不需要保持相同元素的相對(duì)位置不變。

?二、堆排序???

1、堆??

堆一般指的是二叉堆通常是一個(gè)可以被看做一棵完全二叉樹的數(shù)組對(duì)象。

堆（heap）是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個(gè)可以被看做一棵樹的數(shù)組對(duì)象。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。堆總是滿足下列性質(zhì)：

• 堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值；（即k?? <=k?? 且k?<=k????為小根堆，k?>k??且k?>=k????為大根堆）

• 堆總是一棵完全二叉樹。

在堆的數(shù)據(jù)結(jié)構(gòu)中，堆中的最大值總是位于根節(jié)點(diǎn)（在優(yōu)先隊(duì)列中使用堆的話堆中的最小值位于根節(jié)點(diǎn)）。堆中定義以下幾種操作：

• 最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)

• 創(chuàng)建最大堆（Build Max Heap）：將堆中的所有數(shù)據(jù)重新排序

• 堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算?

?可以看下面小根堆建立的GIF簡單了解堆排序的的過程

?

?2、基本思想??

堆排序是簡單選擇排序的改進(jìn)，利用二叉樹代替簡單選擇方法來找最大或者最小值，屬于一種樹形選擇排序方法。

利用大根堆(小根堆)堆頂記錄的是最大關(guān)鍵字(最小關(guān)鍵字)這一特性，使得每次從無序中選擇最大值(最小值)變得簡單。

1. ?將待排序的序列構(gòu)造成一個(gè)大根堆，此時(shí)序列的最大值為根節(jié)點(diǎn)
2. 依次將根節(jié)點(diǎn)與待排序序列的最后一個(gè)元素交換
3. ?再維護(hù)從根節(jié)點(diǎn)到該元素的前一個(gè)節(jié)點(diǎn)為大根堆，如此往復(fù)，最終得到一個(gè)遞增序列

?3、堆的存儲(chǔ)方式??

從堆的概念可知，堆是一棵完全二叉樹，因此可以層序的規(guī)則采用順序的方式來高效存儲(chǔ)。

?

注意：對(duì)于非完全二叉樹，則不適合使用順序方式進(jìn)行存儲(chǔ)，因?yàn)闉榱四軌蜻€原二叉樹，空間中必須要存儲(chǔ)空節(jié)

點(diǎn)，就會(huì)導(dǎo)致空間利用率比較低。

將元素存儲(chǔ)到數(shù)組中后，可以根據(jù)二叉樹章節(jié)的性質(zhì)5對(duì)樹進(jìn)行還原。假設(shè)i為節(jié)點(diǎn)在數(shù)組中的下標(biāo)，則有：

• 如果i為0，則i表示的節(jié)點(diǎn)為根節(jié)點(diǎn)，否則i節(jié)點(diǎn)的雙親節(jié)點(diǎn)為 (i - 1)/2
• 如果2 * i + 1 小于節(jié)點(diǎn)個(gè)數(shù)，則節(jié)點(diǎn)i的左孩子下標(biāo)為2 * i + 1，否則沒有左孩子
• 如果2 * i + 2 小于節(jié)點(diǎn)個(gè)數(shù)，則節(jié)點(diǎn)i的右孩子下標(biāo)為2 * i + 2，否則沒有右孩子

4、堆的shift up和shift down??

Ⅰ、shift up：向一個(gè)最大堆中添加元素??

如下面向堆中加入一個(gè)新元素52，這時(shí)需要重新調(diào)整為大根堆，52比它的父節(jié)點(diǎn)28大，需要交換，然后和28的父節(jié)點(diǎn)（41）比較，還是更大也需要交換。

?

?

Ⅱ、shift down：從一個(gè)最大堆中取出一個(gè)元素只能取出最大優(yōu)先級(jí)的元素，也就是根節(jié)點(diǎn)??

如果上面那個(gè)堆的62變成了12，這時(shí)候?yàn)榱司S持大根堆，只能將12這個(gè)節(jié)點(diǎn)進(jìn)行shift down操作以維持大根堆

??

??

?5、堆的插入與刪除??

Ⅰ、插入??

堆的插入總共需要兩個(gè)步驟：

1. ?先將元素放入到底層空間中(注意：空間不夠時(shí)需要擴(kuò)容)
2. 將最后新插入的節(jié)點(diǎn)向上調(diào)整，直到滿足堆的性質(zhì)

?其實(shí)這就是shift up操作

?

?Ⅱ、刪除??

注意：堆的刪除一定刪除的是堆頂元素（因?yàn)?/strong>二叉堆不支持查找元素位置，因此刪除一個(gè)你完全不知道內(nèi)容的元素毫無意義）。具體如下：

1. 將堆頂元素對(duì)堆中最后一個(gè)元素交換

2. 將堆中有效數(shù)據(jù)個(gè)數(shù)減少一個(gè)

3. 對(duì)堆頂元素進(jìn)行向下調(diào)整（小根堆為例）

import java.util.Arrays;

public class Main {

    public static int[] elem;
    public static int usedSize;//當(dāng)前堆當(dāng)中的有效的元素的數(shù)據(jù)個(gè)數(shù)


    /**
     * 建堆:【大根堆】
     * 時(shí)間復(fù)雜度：O(n)
     */
    public static void createHeap() {
        for (int parent = (usedSize-1-1) / 2; parent >= 0 ; parent--) {
            shiftDown(parent,usedSize);
        }
    }

    /**
     * 實(shí)現(xiàn) 向下調(diào)整
     * @param parent 每棵子樹的根節(jié)點(diǎn)的下標(biāo)
     * @param len 每棵子樹的結(jié)束位置
     */
    private static void shiftDown(int parent, int len) {
        int child = 2 * parent + 1;
        //最起碼是有左孩子
        while (child < len) {
            //判斷 左孩子 和 右孩子  誰最大,前提是  必須有  右孩子
            if(child+1 < len && elem[child] < elem[child+1]) {
                child++;//此時(shí) 保存了最大值的下標(biāo)
            }
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 入隊(duì)
     * @param x
     */
    public void offer(int x) {
        if(isFull()) {
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        this.elem[usedSize] = x;
        usedSize++;
        shiftUp(usedSize-1);
    }
    /**
     * 實(shí)現(xiàn) 向上調(diào)整
     * @param child 需要向上調(diào)整的子樹的下標(biāo)
     */
    private void shiftUp(int child) {
        int parent = (child-1) / 2;
        while (child > 0) {
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent);
                child = parent;
                parent = (child-1) / 2;
            }else {
                break;
            }
        }
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 出隊(duì)
     */
    public int poll() {
        if(isEmpty()) {
            return -1;
        }
        int old = elem[0];
        swap(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return old;
    }
    /*
    判斷是否為空
     */
    public boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     *建立小根堆
     */
    public static void heapSort() {
        int end = usedSize - 1;
        while (end > 0) {
            swap(elem,0,end);
            shiftDown(0,end);
            end--;
        }
    }

    public static void main(String[] args) {
        elem = new int[]{5,4,10,16,1,8,9,48,18,17};
        usedSize = elem.length;
        createHeap();//建立小根堆，先建立大根堆，然后將最大值放入堆尾，建立小根堆
        heapSort();
        System.out.println(Arrays.toString(elem));
        //[1, 4, 5, 8, 9, 10, 16, 17, 18, 48]
        createHeap();//建立大根堆
        System.out.println(Arrays.toString(elem));
        //[48, 18, 16, 17, 9, 10, 5, 1, 8, 4]
    }
}

public class Main {
    public static 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--) {
                swap(arr, j, j + 1);
            }
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr={1,8,6,29,10,14,37,48};//排序結(jié)果為1,6,8,10,14,29,37,48
        insertionSort(arr);
    }
}

public class Main {
    public static void insertionSort(int[] arr) {
        int j,left,mid,right,temp;
        for(int i = 1;i<arr.length;i++){
            left = 0;
            right = i-1;
            temp = arr[i];
            /*找到合適的插入位置right+1，如果中間位置元素
             *比要插入元素大，則查找區(qū)域向低半?yún)^(qū)移動(dòng)，否則向高半?yún)^(qū)移動(dòng)
             */
            while(left <= right){
                mid = (left+right)/2;
                if(arr[mid]>temp){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }
            /*right+1后的元素后移*/
            for(j = i-1;j >= right+1;j--)
            {
                arr[j+1] = arr[j];
            }
            /*將元素插入到指定位置*/
            arr[j+1] = temp;
        }
    }
    public static void main(String[] args) {
        int[] arr={1,8,6,29,10,14,37,48};//排序結(jié)果為1,6,8,10,14,29,37,48
        insertionSort(arr);
    }
}

public static void insertSort(int[] arr) {
    int len = arr.length;
    for (int i = 1; i < len; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

public class Main {
    public static void shellSort(int[] arr){
        /*初始化劃分增量*/
        int n = arr.length;
        int temp;
        /*每次減小增量，直到n = 1*/
        while (n > 1){
            /*增量的取法之一：除2向下取整*/
            n = n/2;
            /*對(duì)每個(gè)按gap劃分后的邏輯分組，進(jìn)行直接插入排序*/
            for (int i = n; i < arr.length; ++i) {
                if (arr[i-n] > arr[i]) {
                    temp = arr[i];
                    int j = i-n;
                    while (j >= 0 && arr[j] > temp) {
                        arr[j+n] = arr[j];
                        j -= n;
                    }
                    arr[j+n] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] arr={1,8,6,29,10,14,37,48};//排序結(jié)果為1,6,8,10,14,29,37,48
        shellSort(arr);
    }
}

public class Main {
    public static void shellSort(int[] arr) {
        int j, left, mid, right, temp;
        int n = arr.length;
        while (n > 1) {
            n /= 2;
            for (int i = n; i < arr.length; i++) {
                left = 0;
                right = i - 1;
                temp = arr[i];
                while (left <= right) {
                    mid = (left + right) / 2;
                    if (arr[mid] > temp) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                for (j = i - n; j >= right + 1; j-=n) {
                    arr[j + n] = arr[j];
                }
                arr[j + n] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {1, 8, 6, 29, 10, 14, 37, 48};//排序結(jié)果為1,6,8,10,14,29,37,48
        shellSort(arr);
    }
}

public static void shellSort(int[] arr) {
    int n = arr.length;
    int h = 1;

    // 計(jì)算間隔值
    while (h < n / 3) {
        h = 3 * h + 1;
    }

    while (h >= 1) {
        // 對(duì)每個(gè)子序列進(jìn)行插入排序
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                swap(arr, j, j - h);
            }
        }

        // 縮小間隔值
        h /= 3;
    }
}

// 交換數(shù)組中兩個(gè)元素的位置
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        // 找到數(shù)組中的最大值和最小值
        int max = arr[0], min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        int bucketSize = max - min + 1; // 桶的大小
        int[] bucket = new int[bucketSize]; // 創(chuàng)建桶

        // 統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i] - min]++;
        }
        //System.out.println(Arrays.toString(bucket));//[1, 1, 0, 0, 1, 0, 1, 0, 2]

        // 對(duì)桶進(jìn)行順序求和，bucket[i]存放的就是原數(shù)組中小于等于i的元素個(gè)數(shù)
        for (int i = 1; i < bucketSize; i++) {
            bucket[i] += bucket[i - 1];
        }
        //System.out.println(Arrays.toString(bucket));//[1, 2, 2, 2, 3, 3, 4, 4, 6]

        int[] temp = new int[arr.length]; // 創(chuàng)建臨時(shí)數(shù)組

        // 從后往前遍歷原數(shù)組，根據(jù)桶中統(tǒng)計(jì)的元素個(gè)數(shù)，將每個(gè)元素放到正確的位置上
        for (int i = arr.length - 1; i >= 0; i--) {
            temp[--bucket[arr[i] - min]] = arr[i];
        }
        //System.out.println(Arrays.toString(temp));[1, 2, 5, 7, 9, 9]

        // 把排好序的元素復(fù)制回原數(shù)組
        for (int i = 0; i < arr.length; i++) {
            arr[i] = temp[i];
        }
    }

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int p = 0; p < temp.length; p++) {
        arr[left + p] = temp[p];
    }
}

public static void mergeSort(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];
    for (int gap = 1; gap < n; gap *= 2) {
        for (int i = 0; i < n - gap; i += gap * 2) {
            int left = i;
            int mid = i + gap - 1;
            int right = Math.min(i + 2 * gap - 1, n - 1);
            merge(arr, left, mid, right, temp);
        }
    }
}

public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int p = 0; p < k; p++) {
        arr[left + p] = temp[p];
    }
}

public static void mergeSort(int[] arr, int l, int r) {
    if (l >= r) {
        return;
    }
    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

public static void insertSort(int[] arr, int l, int r) {
    for (int i = l + 1; i <= r; i++) {
        int temp = arr[i];
        int j = i - 1;
        for (; j >= l && arr[j] > temp; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = temp;
    }
}