十大排序算法總結

王晗發布于2019-08-16 18:30 / 3195人閱讀

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

0. 前言

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

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

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

1. 冒泡排序

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

代碼實現：

public class BubbleSort {

    private static void bubbleSort(int[] data){
        int length = data.length;
        for (int i = length - 1; i > 0; i --) {
            //判斷是否有數據交換，如果沒有則提前退出
            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. 選擇排序

將要排序的數據分為了已排序區間和未排序區間，每次從未排序區間找到最小值，然后將其放到已排序區間的末尾，循環遍歷未排序區間則排序完成。

示意圖如下：

代碼實現：

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. 插入排序

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

示意圖如下：

代碼實現：

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;
        }
    }
}

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

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

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

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

在數據量較大的時候，兩者性能差距就體現出來了。

4. 希爾排序

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

示意圖如下：

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

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. 歸并排序

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

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

代碼實現：

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);
        //結果合并
        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 ++];
            }
        }
        //合并可能出現的剩余元素
        int start = i;
        int end = q;
        if (j <= r){
            start = j;
            end = r;
        }
        while (start <= end){
            temp[k ++] = data[start ++];
        }
        //拷貝回原數組
        if (r - p + 1 >= 0) {
            System.arraycopy(temp, 0, data, p, r - p + 1);
        }
    }
}

6. 快速排序

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

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

代碼實現：

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);
    }

    /**
     * 獲取分區點函數
     */
    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;
    }
    /**
     * 交換數組兩個元素
     */
    private static void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

7. 堆排序

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

建堆

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

排序

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

代碼實現：

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);
        }
    }

    /**
     * 堆化函數
     */
    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;
        }
    }

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

8. 桶排序

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

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

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

public class BucketSort {

    /**
     * 測試場景：數組中有10000個數據，范圍在(0-100000)
     * 使用100個桶，每個桶存放的數據范圍為：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<>());
        }
        //遍歷數據，將數據放到桶中
        for (int i : data) {
            buckets.get(i / 1000).add(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. 計數排序

計數排序其實是一種特殊的桶排序，適用于數據的區間不是很大的情況。

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

計數排序的基本思路如下：

代碼實現：

public class CountingSort {

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

10. 基數排序

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

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

代碼實現：

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();
                }
            }
        }
    }

    /**
     * 獲取數組最大位數
     */
    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 上面有更加詳細的數據結構與算法代碼

云服務器 GPU云服務器排序算法總結最大流算法總結最短路徑算法總結最高優先數優先調度算法實驗總結

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75215.html

十大經典排序算法總結(Javascript描述)

摘要：算法描述冒泡排序是一種簡單的排序算法。算法描述和實現一般來說，插入排序都采用在數組上實現。平均情況希爾排序年發明第一個突破的排序算法是簡單插入排序的改進版它與插入排序的不同之處在于，它會優先比較距離較遠的元素。前言讀者自行嘗試可以想看源碼戳這，博主在github建了個庫，讀者可以Clone下來本地嘗試。此博文配合源碼體驗更棒哦~~~ 個人博客：Damonare的個人博客原文地址：...

Binguner 2019-08-20 11:05 評論0 收藏0
十大經典排序算法的 JavaScript 實現

摘要：計算機領域的都多少掌握一點算法知識，其中排序算法是數據結構與算法中最基本的算法之一。排序算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。計算機領域的都多少掌握一點算法知識，其中排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分為內部排序和外部排序，內部排序是數據記錄在內...

philadelphia 2019-08-20 16:23 評論0 收藏0
JavaScript：十大排序的算法思路和代碼實現

摘要：本文內容包括雙向冒泡排序選擇排序插入排序快速排序填坑和交換歸并排序桶排序基數排序計數排序優化堆排序希爾排序。大家可以在這里測試代碼。本文內容包括：(雙向)冒泡排序、選擇排序、插入排序、快速排序(填坑和交換)、歸并排序、桶排序、基數排序、計數排序(優化)、堆排序、希爾排序。大家可以在這里測試代碼。更多 leetcode 的 JavaScript 解法也可以在我的算法倉庫中找到，歡迎查看...

Lsnsh 2019-08-26 13:57 評論0 收藏0
JavaScript：十大排序的算法思路和代碼實現

摘要：本文內容包括雙向冒泡排序選擇排序插入排序快速排序填坑和交換歸并排序桶排序基數排序計數排序優化堆排序希爾排序。大家可以在這里測試代碼。本文內容包括：(雙向)冒泡排序、選擇排序、插入排序、快速排序(填坑和交換)、歸并排序、桶排序、基數排序、計數排序(優化)、堆排序、希爾排序。大家可以在這里測試代碼。更多 leetcode 的 JavaScript 解法也可以在我的算法倉庫中找到，歡迎查看~ 另外...

Invoker 2019-05-27 17:40 評論0 收藏0