排序算法總結(jié)

KoreyLee 發(fā)布于2019-08-15 18:01 / 3143人閱讀

摘要：如果對(duì)空間限制不大，可以使用基數(shù)排序等方法降低時(shí)間復(fù)雜度，這些線性時(shí)間排序法是利用了數(shù)據(jù)的特性達(dá)到最佳的效果。

內(nèi)部排序

以下為基于比較的排序。

一、插入排序 直接插入排序

基本思想：

將元素插入到已經(jīng)排好序的序列中。第一個(gè)元素已經(jīng)是有序序列，然后比較外圍的元素和序列的最后一個(gè)元素，判斷是否需要插入，如果小，則插入。

時(shí)間復(fù)雜度：最優(yōu) O(n) 最差 O(n^2)

是否穩(wěn)定：是

    public void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) 
            for (int j = i - 1; j >= 0; j--)
                if (arr[j + 1] < arr[j])
                    swap(arr, j + 1, j);
    }

改進(jìn)后的插入排序

比如，用二分查找優(yōu)化插入排序，因?yàn)槭且迦氲揭呀?jīng)排好序的序列當(dāng)中，所以在查找插入位置這個(gè)地方可以用二分查找來(lái)優(yōu)化。

    public int binarySearch(int[] arr, int low, int high, int key) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (key < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }

    public void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++)
            // determine whether to insert
            if (arr[i] < arr[i - 1]) {
                // record the element to insert
                int key = arr[i];
                // find insert index
                int indexInsert = binarySearch(arr, 0, i - 1, arr[i]);
                // move elements
                for (int j = i - 1; j >= indexInsert; j--)
                    arr[j + 1] = arr[j];
                // insert the key
                arr[indexInsert] = key;
            }
    }

二、選擇排序 1. 簡(jiǎn)單選擇排序

基本思想：

選出后面最小的元素和前面的交換

時(shí)間復(fù)雜度：最優(yōu) O(n^2) 最差 O(n^2)

是否穩(wěn)定：否

    public void selectSort(int[] arr) {

        int n = arr.length;

        for (int i = 0; i < n; i++) {
            int minIndex = i;
            // find the min index
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }
            if (minIndex != i)
                swap(arr, i, minIndex);
        }
    }

改進(jìn)后的選擇排序

之前的選擇排序是一趟只找到最小的，如果一趟可以把最大最小都找出來(lái)，就可以將循環(huán)的次數(shù)減半。

不過(guò)在交換時(shí)需要注意一種情況，就是第一個(gè)元素就已經(jīng)是最大元素的情況，因?yàn)榍懊嬉呀?jīng)交換過(guò) i 和 min，所以再交換時(shí)就是交換的 n - i - 1 和 min，而不是 max。

    public void selectSort(int[] arr) {

        int n = arr.length;

        for (int i = 0; i < n / 2; i++) {
            int min = i;
            int max = i;
            for (int j = i + 1; j < n - i; j++) {
                // find the min element
                if (arr[j] < arr[min]) {
                    min = j;
                    continue;
                }
                // find the max element
                if (arr[j] > arr[max])
                    max = j;
            }
            swap(arr, i, min);

            if (max != i)
                swap(arr, n - i - 1, max);
            else // the first element is the max element
                swap(arr, n - i - 1, min);
        }
    }

2. 堆排序

基本思想：

堆排序也是一種直接選擇排序，因?yàn)樗彩菍⑴藕眯虻拇蟾?or 小根堆的頂部元素逐個(gè)和尾部元素交換，也是一種選擇。

時(shí)間復(fù)雜度：最優(yōu) O(nlgn) 最差 O(nlgn) 是一個(gè)很優(yōu)秀的排序算法

是否穩(wěn)定：否

    public void adjustHeap(int[] arr, int i, int len) {

        int parent = arr[i];

        // start from left child
        for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
            // find max child (left or right)
            if (k + 1 < len && arr[k + 1] > arr[k])
                k++;
            // compare the parent and its child, but don"t swap
            if (arr[k] > arr[i]) {
                arr[i] = arr[k];
                i = k;
            } else
                break;
        }

        // insert the original parent on index i
        arr[i] = parent;
    }

    public void heapSort(int[] arr) {

        int len = arr.length;

        // adjust heap from the last none-leaf node
        // from bottom to up; from right to left
        for (int i = len / 2 - 1; i >= 0; i--)
            adjustHeap(arr, i, len);

        // swap the top element and the last element
        for (int i = len - 1; i >= 0; i--) {
            swap(arr, i, 0);
            adjustHeap(arr, 0, i);
        }
    }

三、歸并排序

基本思想：分治。將兩個(gè)有序序列合并成一個(gè)有序序列，遞歸進(jìn)行。需要輔助數(shù)組。

時(shí)間復(fù)雜度：最優(yōu) O(nlgn) 最差 O(nlgn)

空間復(fù)雜度

O(n)

是否穩(wěn)定：是

    /* create an array in advance to avoid creating arrays frequently */
    private void sort(int[] arr) {
        int n = arr.length;
        int[] temp_arr = new int[n];
        mergeSort(arr, 0, n - 1, temp_arr);
    }

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

    public void merge(int[] arr, int left, int mid, int right, int[] temp_arr) {

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

        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp_arr[t++] = arr[i];
                i++;
            } else {
                temp_arr[t++] = arr[j];
                j++;
            }
        }

        // insert the remaining elements
        while (i <= mid)
            temp_arr[t++] = arr[i++];
        while (j <= right)
            temp_arr[t++] = arr[j++];

        t = 0;
        // copy elements into array
        while (left <= right)
            arr[left++] = temp_arr[t++];
    }

四、交換排序 1. 冒泡排序

基本思想：

總共有 n 個(gè)元素，就比較 n - 1 趟，每一趟比較都會(huì)將相鄰元素進(jìn)行比較，然后將較大的元素向后放，就像大數(shù)沉底，小數(shù)像上冒一樣。冒泡排序的交換次數(shù)等于原始序列的逆序數(shù)。

時(shí)間復(fù)雜度：最優(yōu) O(n) 最差也是平均 O(n^2)

是否穩(wěn)定：是

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

改進(jìn)后的冒泡排序一

交換過(guò)后，會(huì)有部分元素是已經(jīng)排好序了，這一部分再進(jìn)行比較是沒(méi)有意義的，可以從這個(gè)地方入手改進(jìn)冒泡排序。

用一個(gè)標(biāo)志位記錄最后一次進(jìn)行交換的位置，這個(gè)位置后面的元素是沒(méi)有進(jìn)行交換的，說(shuō)明是已經(jīng)排好序的，所以不需要再比較。

    public void bubbleSort(int[] arr) {

        int n = arr.length;
        int i = n - 1;
        int pos = 0;

        while (i > 0) {
            for (int j = 0; j < i; j++) {
                pos = 0;
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    pos = j;
                }
            }
            i = pos;
        }
    }

改進(jìn)后的冒泡排序二

雙向冒泡（正反兩個(gè)方向同時(shí)排序），使排序次數(shù)幾乎減少一半

    public void bubbleSort(int[] arr) {

        int n = arr.length;
        int left = 0;
        int right = n - 1;

        while (left < right) {
            for (int i = left; i < right; i++) {
                if (arr[i] > arr[i + 1])
                    swap(arr, i, i + 1);
            }
            right--;

            for (int i = right; i > left; i--) {
                if (arr[i] < arr[i - 1])
                    swap(arr, i, i - 1);
            }
            left++;
        }
    }

2. 快速排序

基本思想：

根據(jù)選擇的基準(zhǔn)元素進(jìn)行劃分，然后兩邊都進(jìn)行排序，再遞歸進(jìn)行。需要注意的是，遍歷需要從選擇的基準(zhǔn)元素的反方向開(kāi)始。

時(shí)間復(fù)雜度：最優(yōu)也是平均 O(nlgn) 最差 O(n^2) 即每次選的基準(zhǔn)元素都是最大（小）值

是否穩(wěn)定：否

    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotLoc = partition(arr, low, high);
            quickSort(arr, low, pivotLoc - 1);
            quickSort(arr, pivotLoc + 1, high);
        }
    }

    public int partition(int[] arr, int low, int high) {
        int pivot = arr[low];

        while (low < high) {
            while (low < high && arr[high] >= pivot)
                high--;
            swap(arr, low, high);

            while (low < high && arr[low] <= pivot)
                low++;
            swap(arr, low, high);
        }

        return low;
    }

外部排序

非基于比較的排序，時(shí)間復(fù)雜度可以達(dá)到 O(n)，其實(shí)是用空間換時(shí)間。

下面列舉的都是線性時(shí)間排序法

1. 計(jì)數(shù)排序（Counting Sort）

基本思想：

利用數(shù)組下標(biāo)來(lái)排序。但只適合有限數(shù)值的數(shù)字，序列的數(shù)字最大值 k 如果太大，那么開(kāi)的輔助數(shù)組 C[] 就會(huì)很大，占用太多空間。
這種思路經(jīng)常被用到。

時(shí)間復(fù)雜度：最優(yōu)也是平均 O(n + k) 最差 O(n^2) 即每次選的基準(zhǔn)元素都是最大（?。┲?/p>

是否穩(wěn)定：是

    public int[] countingSort(int[] A, int k) {
        int n = A.length;
        int[] C = new int[k + 1];

        // counting the number of times each element appears in A
        for (int i = 0; i < n; i++) {
            C[A[i]]++;
        }

        // counting elements less than or equal to C[i]
        for (int i = 1; i <= k; i++) {
            C[i] = C[i] + C[i - 1];
        }

        // insert into result array
        int[] B = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            B[C[A[i]] - 1] = A[i];
            C[A[i]]--;
        }

        return B;
    }

2. 桶排序（Bucket Sort）

基本思想：

把數(shù)組中數(shù)據(jù)放到有限個(gè)桶中，在每個(gè)桶中分別進(jìn)行排序（可以采用任意排序方法）。

模擬畫圖 ≡ω≡

      input:[12,22,2,13,23,3]

     |     |     |     |     |     |
     | 2,3 |     |12,13|     |22,23|
     |_____|     |_____|     |_____|
     bucket1     bucket2     bucket3
      (1-10)     (11-20)     (21-30)

      output:[2,3,12,13,22,23]

時(shí)間復(fù)雜度：最優(yōu)近似 O(n) 最差 O(n^2) 即每次選的基準(zhǔn)元素都是最大（?。┲?/p>

是否穩(wěn)定：是

    public void bucketSort(int[] arr){

        int n = arr.length;

        int max = arr[0];
        int min = arr[0];
        for (int num : arr) {
            if (num < min)
                min = num;
            if (num > max)
                max = num;
        }

        // create bucket
        int bucketNum = max / 10 - min / 10 + 1;
        List bucketList = new ArrayList>();
        for (int i = 1; i <= bucketNum; i++) {
            bucketList.add(new ArrayList());
        }

        // insert into bucket
        for (int i = 0; i < n; i++) {
            int index = (arr[i] - min) / 10;
            ((ArrayList)bucketList.get(index)).add(arr[i]);
        }

        ArrayList bucket = null;
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            bucket = (ArrayList)bucketList.get(i);
            bucketInsertSort(bucket);
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }

    public void bucketInsertSort(List bucket) {
        for (int i = 0; i < bucket.size(); i++) {
            int temp = bucket.get(i);
            int j = i - 1;
            for (; j >= 0 && bucket.get(j) > temp; j--) {
                bucket.set(j + 1, bucket.get(j));
            }
            bucket.set(j + 1, temp);
        }
    }

3. 基數(shù)排序（Radix Sort）

基本思想：

前面的計(jì)數(shù)和桶排序都是只能排一個(gè)關(guān)鍵字，而基數(shù)排序可以排多個(gè)關(guān)鍵字。

基數(shù)排序分為兩種：假設(shè)有二元組 (a, b)，以 a 為首要關(guān)鍵字，b 為次要關(guān)鍵字排序

MSD(Most Siginificant Digit) 先排 a，后排 b

LSD(Least Siginificant Digit) 先排 b，后排 a

基數(shù)排序需要使用穩(wěn)定的排序算法，一般用計(jì)數(shù)或者桶排序。

e.g. 采用 LSD

input: [170, 45, 75, 90, 802, 24, 2, 66]

1. 從最后一個(gè)關(guān)鍵字開(kāi)始排：  
   170, 45, 75, 90, 802, 24, 2, 66
     0   5   5   0    2   4  2   6

   排序后（注意保持原來(lái)的相對(duì)順序，802 仍然在 2 前面）：
   170, 90, 802, 2, 24, 45, 75, 66

2. 從次要關(guān)鍵字開(kāi)始排
   170, 90, 802, 2, 24, 45, 75, 66
    7   9    0      2   4   7   6

   排序后（170 仍然在 75 前面）：
   802, 2, 24, 45, 66, 170, 75, 90

3. 從首要關(guān)鍵字開(kāi)始排：
   802, 2, 24, 45, 66, 170, 75, 90
   8                   1

   排序后：
   2, 24, 45, 66, 75, 90, 170, 802

output: [2, 24, 45, 66, 75, 90, 170, 802]

時(shí)間復(fù)雜度：

平均 O(d * (r + n))

d:digit 數(shù)字位數(shù) r:radix 基數(shù) n:number 關(guān)鍵字個(gè)數(shù)

空間復(fù)雜度：

O(r + n)

是否穩(wěn)定：是

    public void radixSort(int[] arr, int n) {

        // find max element
        int max = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        for (int k = 1; max / k > 0; k *= 10) {
            countingSort(arr, n, k);
        }
    }

    public void countingSort(int[] arr, int n, int k) {

        // max number is 9
        int C[] = new int[10];

        // counting occurrences
        for (int i = 0; i < n; i++) {
            C[(arr[i] / k) % 10]++;
        }

        // counting elements less than or equal to C[i]
        for (int i = 1; i < 10; i++) {
            C[i] = C[i] + C[i - 1];
        }

        // insert into result array
        int[] B = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            B[C[(arr[i] / k) % 10] - 1] = arr[i];
            C[(arr[i] / k) % 10]--;
        }

        for (int i = 0; i < n; i++) {
            arr[i] = B[i];
        }

    }

總結(jié)

關(guān)于穩(wěn)定性：

穩(wěn)定的排序算法：冒泡、插入、歸并、計(jì)數(shù)、桶和基數(shù)排序

不穩(wěn)定的排序算法: 選擇、快速、希爾和堆排序

排序算法的選擇：

如果數(shù)據(jù)有序或基本有序，冒泡和插入的時(shí)間復(fù)雜度可以降到 O(n)，而快排則相反。

如果數(shù)據(jù)很大，需要考慮使用 O(nlgn) 的排序方法，如快排、歸并排序、堆排。

如果對(duì)空間限制不大，可以使用基數(shù)排序等方法降低時(shí)間復(fù)雜度，這些線性時(shí)間排序法是利用了數(shù)據(jù)的特性達(dá)到最佳的效果。

參考資料：

https://www.byvoid.com/zhs/bl...

https://zh.wikipedia.org/wiki...

https://blog.csdn.net/hguisu/...

https://www.geeksforgeeks.org...

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

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

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

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

KoreyLee

男|高級(jí)講師

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

TA的文章

2021馬哥Linux云計(jì)算就業(yè)+架構(gòu)師班sre工程師

閱讀 2741·2021-11-22 15:22
0011 - YARN核心設(shè)計(jì)解析

閱讀 1653·2021-11-22 14:56
主機(jī)早怎么什么都沒(méi)有-裝好新主機(jī)后，開(kāi)機(jī)什么都沒(méi)有怎辦？裝好主機(jī)？

閱讀 3629·2021-09-22 15:12
Postman的使用

閱讀 2416·2021-09-02 15:41
“以假亂真” 網(wǎng)絡(luò)釣魚(yú)活動(dòng)巧妙使用 UPS.com XSS 漏洞分發(fā)惡意軟件

閱讀 2139·2021-08-27 16:26
前端性能優(yōu)化從css說(shuō)起

閱讀 1126·2019-08-30 15:55
APICloud使用Aui自定義Toast

閱讀 2151·2019-08-29 17:30
主流的CSS水平和垂直居中技術(shù)大全

閱讀 680·2019-08-29 16:26

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

資訊專欄INFORMATION COLUMN

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

排序算法總結(jié)

相關(guān)文章

各種排序算法總結(jié)

前端排序算法總結(jié)

**算法：排序算法總結(jié)（JavaScript描述）**

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

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

算法-java排序實(shí)現(xiàn)總結(jié)

發(fā)表評(píng)論

0條評(píng)論

KoreyLee

男|高級(jí)講師

TA的文章

2021馬哥Linux云計(jì)算就業(yè)+架構(gòu)師班sre工程師

0011 - YARN核心設(shè)計(jì)解析

主機(jī)早怎么什么都沒(méi)有-裝好新主機(jī)后，開(kāi)機(jī)什么都沒(méi)有怎辦？裝好主機(jī)？

Postman的使用

“以假亂真” 網(wǎng)絡(luò)釣魚(yú)活動(dòng)巧妙使用 UPS.com XSS 漏洞分發(fā)惡意軟件

前端性能優(yōu)化從css說(shuō)起

APICloud使用Aui自定義Toast

主流的CSS水平和垂直居中技術(shù)大全

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

排序算法總結(jié)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

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