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

王晗發(fā)布于2019-08-16 18:30 / 3208人閱讀

摘要：排序算法的穩(wěn)定性例如排序一個數(shù)組，數(shù)組中有兩個，排序之后是，如果排序之后的兩個的前后順序沒有發(fā)生變化，那么稱這個排序是穩(wěn)定的，反之則是不穩(wěn)定的。冒泡排序冒泡排序是很經(jīng)典的排序算法了，相鄰的兩個數(shù)據(jù)依次進行比較并交換位置。

0. 前言

排序算法中涉及到了兩個概念：

原地排序：根據(jù)算法對內(nèi)存的消耗情況，可以將算法分為原地排序和非原地排序，原地排序特指空間復(fù)雜度為 O(1) 的排序。

排序算法的穩(wěn)定性：例如排序一個數(shù)組 [1, 5, 3, 7, 4, 9, 5]，數(shù)組中有兩個 5，排序之后是 [1, 3, 4, 5, 5, 7, 9]，如果排序之后的兩個 5 的前后順序沒有發(fā)生變化，那么稱這個排序是穩(wěn)定的，反之則是不穩(wěn)定的。

1. 冒泡排序

冒泡排序是很經(jīng)典的排序算法了，相鄰的兩個數(shù)據(jù)依次進行比較并交換位置。遍歷一遍數(shù)組后，則有一個數(shù)據(jù)排序完成，然后再遍歷 n 次，排序完成。示意圖如下：

代碼實現(xiàn)：

public class BubbleSort {

    private static void bubbleSort(int[] data){
        int length = data.length;
        for (int i = length - 1; i > 0; i --) {
            //判斷是否有數(shù)據(jù)交換，如果沒有則提前退出
            boolean flag = false;
            for (int j = 0; j < i; j ++) {
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag){
                break;
            }
        }
    }
}

2. 選擇排序

將要排序的數(shù)據(jù)分為了已排序區(qū)間和未排序區(qū)間，每次從未排序區(qū)間找到最小值，然后將其放到已排序區(qū)間的末尾，循環(huán)遍歷未排序區(qū)間則排序完成。

示意圖如下：

代碼實現(xiàn)：

public class SelectionSort {

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

3. 插入排序

和選擇排序類似，插入排序也將數(shù)據(jù)分為了已排序區(qū)間和未排序區(qū)間，遍歷未排序區(qū)間，每次取一個數(shù)據(jù)，將其插入到已排序區(qū)間的合適位置，讓已排序區(qū)間一直保持有序，直到未排序區(qū)間遍歷完排序則完成。

示意圖如下：

代碼實現(xiàn)：

public class InsertionSort {

    public static void insertionSort(int[] data){
        int length = data.length;
        for (int i = 0; i < length - 1; i++) {
            int val = data[i + 1];
            int j = i + 1;
            while (j > 0 && data[j - 1] > val){
                data[j] = data[j - 1];
                j --;
            }
            data[j] = val;
        }
    }
}

插入排序為什么比冒泡排序更常用？

這兩種排序的時間復(fù)雜度都是一樣的，最好情況是 O(n)，最壞情況是 O(n2)，但是在實際的生產(chǎn)中，插入排序使用更多，原因在于兩者數(shù)據(jù)交換的次數(shù)不同。冒泡排序需要進行三次交換，插入排序只要一次：

//冒泡排序數(shù)據(jù)交換
if (data[j] > data[j + 1]){
    int temp = data[j];
    data[j] = data[j + 1];
    data[j + 1] = temp;
    flag = true;
}

//插入排序數(shù)據(jù)交換
while (j > 0 && data[j - 1] > val){
    data[j] = data[j - 1];
    j --;
}

在數(shù)據(jù)量較大的時候，兩者性能差距就體現(xiàn)出來了。

4. 希爾排序

希爾排序其實是插入排序的一種優(yōu)化，其思路是將排序的數(shù)組按照一定的增量將數(shù)據(jù)分組，每個分組用插入排序進行排序，然后增量逐步減小，當(dāng)增量減小為1的時候，算法便終止，所以希爾排序又叫做“縮小增量排序”。

示意圖如下：

圖中的示例，每次依次將數(shù)組分為若干組，每組分別進行插入排序。代碼實現(xiàn)如下：

public class ShellSort {

    public static void shellSort(int[] data) {

        int length = data.length;
        int step = length / 2;
        while (step >= 1){
            for (int i = step; i < length; i++) {
                int val = data[i];
                int j = i - step;
                for (; j >= 0; j -= step){
                    if (data[j] > val){
                        data[j + step] = data[j];
                    }
                    else {
                        break;
                    }
                }
                data[j + step] = val;
            }
            step = step / 2;
        }
    }
}

5. 歸并排序

歸并排序使用到了分治思想，分治思想即將大的問題分解成小的問題，小的問題解決了，大的問題也就解決了。蘊含分治思想的問題，一般可以使用遞歸技巧來實現(xiàn)。

歸并排序的思路是：首先將數(shù)組分解，局部進行排序，然后將排序的結(jié)果進行合并，這樣整個數(shù)組就有序了，你可以結(jié)合下圖理解：

代碼實現(xiàn)：

public class MergeSort {

    public static void mergeSort(int[] data){
        mergeInternally(data, 0, data.length - 1);
    }

    private static void mergeInternally(int[] data, int p, int r){
        if (p >= r){
            return;
        }
        int q = (p + r) / 2;
        //分治遞歸
        mergeInternally(data, p, q);
        mergeInternally(data, q + 1, r);
        //結(jié)果合并
        merge(data, p, q, r);
    }

    private static void merge(int[] data, int p, int q, int r){
        int[] temp = new int[r - p + 1];
        int k = 0;
        int i = p;
        int j = q + 1;
        //比較并合并
        while (i <= q && j <= r){
            if (data[i] < data[j]){
                temp[k ++] = data[i ++];
            }
            else {
                temp[k ++] = data[j ++];
            }
        }
        //合并可能出現(xiàn)的剩余元素
        int start = i;
        int end = q;
        if (j <= r){
            start = j;
            end = r;
        }
        while (start <= end){
            temp[k ++] = data[start ++];
        }
        //拷貝回原數(shù)組
        if (r - p + 1 >= 0) {
            System.arraycopy(temp, 0, data, p, r - p + 1);
        }
    }
}

6. 快速排序

快速排序也用到了分治的思想，只不過它和歸并排序的思路剛好是相反的，快速排序使用數(shù)組中一個數(shù)據(jù)作為分區(qū)點（一般可以選取數(shù)組第一個或最后一個元素），比分區(qū)點小的，放在左側(cè)，比分區(qū)點大的，放在右側(cè)。然后左右兩側(cè)的數(shù)據(jù)再次選擇分區(qū)點，循環(huán)進行這個操作，直到排序完成。

示意圖如下（圖中是以第一個元素作為分區(qū)點）：

代碼實現(xiàn)：

public class QuickSort {
    public static void quickSort(int[] data){
        quickSortInternally(data, 0, data.length - 1);
    }

    private static void quickSortInternally(int[] data, int p, int r){
        if (p >= r){
            return;
        }
        int q = partition(data, p, r);
        quickSortInternally(data, p, q - 1);
        quickSortInternally(data, q + 1, r);
    }

    /**
     * 獲取分區(qū)點函數(shù)
     */
    private static int partition(int [] data, int p, int q){
        int pivot = data[q];
        int i = 0;
        int j = 0;
        while (j < q){
            if (data[j] <= pivot){
                swap(data, i, j);
                i ++;
            }
            j ++;
        }
        swap(data, i, q);
        return i;
    }
    /**
     * 交換數(shù)組兩個元素
     */
    private static void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

7. 堆排序

基于堆的排序比較常用，時間復(fù)雜度為 O(nlogn)，并且是原地排序，主要的步驟分為建堆和排序。

建堆

思路是從堆中第一個非葉子節(jié)點，依次從上往下進行堆化，如下圖：

排序

建堆完成之后，假設(shè)堆中元素個數(shù)為 n，堆頂元素即是最大的元素，這時候直接將堆頂元素和堆中最后一個元素進行交換，然后將剩余的 n - 1 個元素構(gòu)建成新的堆，依次類推，直到堆中元素減少至 1，則排序完成。示意圖如下：

代碼實現(xiàn)：

public class HeapSort {

    /**
     * 排序
     */
    public void heapSort(int[] data){
        int length = data.length;
        if (length <= 1){
            return;
        }
        buildHeap(data);
        while (length > 0){
            swap(data, 0, -- length);
            heapify(data, length, 0);
        }
    }

    /**
     * 建堆
     */
    private void buildHeap(int[] data){
        int length = data.length;
        for (int i = (length - 2) / 2; i >= 0; i --) {
            heapify(data, length, i);
        }
    }

    /**
     * 堆化函數(shù)
     */
    private void heapify(int[] data, int size, int i){
        while (true){
            int max = i;
            if ((2 * i + 1) < size && data[i] < data[2 * i + 1]) {
                max = 2 * i + 1;
            }
            if ((2 * i + 2) < size && data[max] < data[2 * i + 2]) {
                max = 2 * i + 2;
            }
            if (max == i){
                break;
            }
            swap(data, i, max);
            i = max;
        }
    }

    /**
     * 交換數(shù)組中兩個元素
     */
    private void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

8. 桶排序

桶排序并不是基于數(shù)據(jù)比較的，因此比較的高效，時間復(fù)雜度接近 O(n)，但是相應(yīng)地，應(yīng)用的條件十分苛刻。其思路非常的簡單：將要排序的數(shù)據(jù)分到各個有序的桶內(nèi)，數(shù)據(jù)在桶內(nèi)進行排序，然后按序取出，整個數(shù)據(jù)就是有序的了。

最好情況下，數(shù)據(jù)被均勻的分到各個桶中，最壞情況是數(shù)據(jù)全都被分到一個桶中。

下面是一個桶排序的示例：

public class BucketSort {

    /**
     * 測試場景：數(shù)組中有10000個數(shù)據(jù)，范圍在(0-100000)
     * 使用100個桶，每個桶存放的數(shù)據(jù)范圍為：0-999, 1000-1999, 2000-2999，依次類推
     */
    public static void bucketSort(int[] data){
        //新建100個桶
        int bucketSize = 100;
        ArrayList> buckets = new ArrayList<>(bucketSize);
        for (int i = 0; i < bucketSize; i++) {
            buckets.add(new ArrayList<>());
        }
        //遍歷數(shù)據(jù)，將數(shù)據(jù)放到桶中
        for (int i : data) {
            buckets.get(i / 1000).add(i);
        }
        //在桶內(nèi)部進行排序
        int k = 0;
        for (int i = 0; i < bucketSize; i++) {
            ArrayList list = buckets.get(i);
            Integer[] num = list.toArray(new Integer[1]);
            Arrays.sort(num);
            //拷貝到data中
            for (int n : num) {
                data[k++] = n;
            }
        }
    }
    //測試
    public static void main(String[] args) {
        Random random = new Random();
        int[] data = new int[10000];
        for (int i = 0; i < data.length; i++) {
            data[i] = random.nextInt(100000);
        }
        BucketSort.bucketSort(data);
        System.out.println(Arrays.toString(data));
    }
}

9. 計數(shù)排序

計數(shù)排序其實是一種特殊的桶排序，適用于數(shù)據(jù)的區(qū)間不是很大的情況。

例如給 10 萬人按照年齡進行排序，我們知道年齡的區(qū)間并不是很大，最小的 0 歲，最大的可以假設(shè)為 120 歲，那么我們可以新建 121 個桶，掃描一遍數(shù)據(jù)，將年齡相同的放到一個桶中，然后按序從桶中將數(shù)據(jù)取出，這樣數(shù)據(jù)就有序了。

計數(shù)排序的基本思路如下：

代碼實現(xiàn)：

public class CountingSort {

    private static void countingSort(int[] data){
        int length = data.length;
        //找到數(shù)組的最大值
        int max = data[0];
        for (int i : data){
            if (max < i){
                max = i;
            }
        }
        //新建一個計數(shù)數(shù)組，大小為max+1
        //count數(shù)組的下標(biāo)對應(yīng)data的值，存儲的值為對應(yīng)data值的個數(shù)
        int[] count = new int[max + 1];
        for (int i : data){
            count[i] ++;
        }
        //根據(jù)count數(shù)組取出數(shù)據(jù)
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0){
                data[k ++] = i;
                count[i] --;
            }
        }
    }
}

10. 基數(shù)排序

基數(shù)排序適用于位數(shù)較多的數(shù)字或者字符串，思路是將排序的數(shù)據(jù)按位拆分，每一位多帶帶按照穩(wěn)定的排序算法進行比較，如下圖：

圖中的示例，以每個數(shù)字為下標(biāo)，建了 10 個 “桶”，每個桶是一個隊列（也可以是數(shù)組），然后將要排序的數(shù)據(jù)按位加入到隊列中，然后出隊，比較完每一位，則排序完成。

代碼實現(xiàn)：

public class RadixSort {

    private static void radixSort(int[] data) {
        int maxDigit = maxDigit(data);

        //新建并初始化10個桶
        Queue[] queues = new LinkedList[10];
        for (int i = 0; i < queues.length; i++) {
            queues[i] = new LinkedList<>();
        }

        for (int i = 0, mod = 1; i < maxDigit; i ++, mod *= 10) {
            for (int n : data){
                int m = (n / mod) % 10;
                queues[m].add(n);
            }

            int count = 0;
            for (Queue queue : queues) {
                while (queue.size() > 0) {
                    data[count++] = queue.poll();
                }
            }
        }
    }

    /**
     * 獲取數(shù)組最大位數(shù)
     */
    private static int maxDigit(int[] data){
        int maxDigit = data[0];
        for (int i : data){
            if (maxDigit < i){
                maxDigit = i;
            }
        }
        return String.valueOf(maxDigit).length();
    }
}

在我的 Github 上面有更加詳細的數(shù)據(jù)結(jié)構(gòu)與算法代碼

云服務(wù)器 GPU云服務(wù)器排序算法總結(jié) 最大流算法總結(jié) 最短路徑算法總結(jié) 最高優(yōu)先數(shù)優(yōu)先調(diào)度算法實驗總結(jié)

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/75215.html

發(fā)表評論

登陸后可評論

0條評論

王晗

男|高級講師

我要關(guān)注我要私信

TA的文章

在 main 函數(shù)之前執(zhí)行代碼（C 語言）

閱讀 2061·2021-09-29 09:35
面試知識點總結(jié)

閱讀 1970·2019-08-30 14:15
盒子模型，怪異盒子模型

閱讀 2998·2019-08-30 10:56
純css實現(xiàn)手機通訊錄

閱讀 986·2019-08-29 16:59
5分鐘搞定box-sizing

閱讀 601·2019-08-29 14:04
2017 前端面試準(zhǔn)備 - 收藏集 - 掘金

閱讀 1333·2019-08-29 12:30
CSS 樣式優(yōu)先級

閱讀 1051·2019-08-28 18:19
【js】《JavaScript設(shè)計模式與開發(fā)實踐》——this的指向

閱讀 535·2019-08-26 11:51

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

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

相關(guān)文章

**十大經(jīng)典排序算法總結(jié)(Javascript描述)**

十大經(jīng)典排序算法的 JavaScript 實現(xiàn)

JavaScript：十大排序的算法思路和代碼實現(xiàn)

JavaScript：十大排序的算法思路和代碼實現(xiàn)

發(fā)表評論

0條評論

王晗

男|高級講師

TA的文章

在 main 函數(shù)之前執(zhí)行代碼（C 語言）

面試知識點總結(jié)

盒子模型，怪異盒子模型

純css實現(xiàn)手機通訊錄

5分鐘搞定box-sizing

2017 前端面試準(zhǔn)備 - 收藏集 - 掘金

CSS 樣式優(yōu)先級

【js】《JavaScript設(shè)計模式與開發(fā)實踐》——this的指向

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

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

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！