排序相關概念

穩定性

內部排序

外部排序

十種排序演算法特點總結

交換排序

冒泡排序（陣列sort方法的原理）

圖解

js實作

特點

快速排序

圖解

js實作

特點

選擇排序

直接選擇排序

圖解

js實作

特點

堆排序

大（小）頂堆

非葉節點

js實作

特點

插入排序

直接插入排序

圖解

js實作

特點

希爾排序

圖解

js實作

特點

其它排序

桶排序

圖解

js實作

特點

基數排序

圖解

js實作

特點

歸并排序

圖解

js實作

特點

計數排序

圖解

js實作

特點

排序相關概念

穩定性

不改變相同數值的順序為穩定，例如在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序演算法是穩定的(記錄的相對次序保持不變)；否則稱為不穩定的，

內部排序

指待排序列完全存放在記憶體中所進行的排序程序，適合不太大的元素序列，有冒泡、選擇、插入、希爾、快速、堆排序（通常快速排序為最好的），

外部排序

外部排序指的是大檔案的排序，即待排序的記錄存盤在外存盤器上，待排序的檔案無法一次裝入記憶體，需要在記憶體和外部存盤器之間進行多次資料交換，以達到排序整個檔案的目的，有歸并、計數、桶、基數排序，

十種排序演算法特點總結

交換排序

冒泡排序（陣列sort方法的原理）

1.比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，

2.對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，這步做完后，最后的元素會是最大的數，

3.針對所有的元素重復以上的步驟，除了最后一個，

4.持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，

圖解

js實作

function swap(arr, x, y) {
    let tmp = arr[x]
    arr[x] = arr[y]
    arr[y] = tmp
}
function bubbleSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        //比較出一輪中的最大值放入最后
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1)
            }
        }
    }
    return arr;
}

特點

時間復雜度：O(N^2)
空間復雜度：O(1)
穩定性：穩定

快速排序

1.以陣列第一位為基準值，將小于的元素放在左邊，大于的元素放在右邊，分為左右兩塊，

2.在左右2塊中重復第一步，不斷回圈，直到磁區的大小為1則停止，

圖解

注意左右磁區，我們可以通過將基準元素和左邊磁區最右端元素交換實作

js實作

function swap(arr, x, y) {
    let tmp = arr[x]
    arr[x] = arr[y]
    arr[y] = tmp
}
//用于一次以基準值進行排序
function partition(arr, left, right) {
    //設定基準值pivot
    let pivot = left
    let index = pivot + 1
    for (let i = index; i <= right; i++) {
        //小于基準值的放左邊，大于的不變
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index)
            index++
        }
    }
    //和小于基準值的最右邊一個交換位置，實作左邊小于基準值，右邊大于基準值
    swap(arr, pivot, index - 1)
    //回傳基準值的位置
    return index - 1
}
function quickSort(arr, left, right) {
    let len = arr.length
    left = typeof left != 'number' ? 0 : left
    right = typeof right != 'number' ? len - 1 : right
    if (left < right) {
        //進行一次排序
        let partitionIndex = partition(arr, left, right)
        //遞回對左邊進行排序
        quickSort(arr, left, partitionIndex - 1)
        //遞回對右邊進行排序
        quickSort(arr, partitionIndex + 1, right)
    }
    return arr
}
console.log(quickSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))

特點

時間復雜度：O(N*logN)
空間復雜度：O(logN)
穩定性：不穩定

選擇排序

直接選擇排序

每一次遍歷待排序的資料元素從中選出最小（或最大）的一個元素，存放在序列的起始（或者末尾）位置（和原存放位置上的元素交換順序），直到全部待排序的資料元素排完，

圖解

js實作

//交換陣列下標x位和y位的元素
function swap(arr, x, y) {
    arr[x] = arr[x] - arr[y]
    arr[y] = arr[y] + arr[x]
    arr[x] = arr[y] - arr[x]
    return arr
}
function selectionSort(arr) {
    let t = arr.length
    let x = 0
    while (x != t) {
        let min = 0;
        let tmp = Number.MAX_VALUE
        //選出最小的元素的下標
        for (let i = x; i < t; i++) {
            if (tmp > arr[i]) {
                tmp = arr[i]
                min = i
            }
        }
        //不是當前位置，則交換順序
        if (x != min) {
            swap(arr, x, min)
        }
        x++
    }
    return arr
}
console.log(selectionSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))

特點

時間復雜度：O(N^2)
空間復雜度：O(1)
穩定性：不穩定

堆排序

1.將元素排序為一個大（小）頂堆，則頂部元素為最大（小）元素，將其與元素尾（頭）部元素交換順序，

2.重新排序剩下元素，再次形成大（小）頂堆，重復1操作，直到只剩一個元素，

大（小）頂堆

每個節點的值都大于（小于）或等于其子節點的值，在堆排序演算法中用于升（降）序排列；

代碼中表示為：

大頂堆arr[i]>=arr[2i+1]和arr[i]>=arr[2i+2] 父節點大于左右子節點

小頂堆arr[i]<=arr[2i+1]和arr[i]<=arr[2i+2] 父節點小于左右子節點

非葉節點

有孩子節點的節點，最后一個非葉節點在陣列中的序號為元素個數除以2向下取整，

js實作

// 建立大頂堆
function buildMaxHeap(arr) {
    let len = arr.length;
    //Math.floor(len/2)表示最后一個非葉節點（含有子節點的節點），
    //從后往前調整每一個非葉子節點的順序，使堆變為大頂堆
    for (let i = Math.floor(len / 2); i >= 0; i--) {
        heapify(arr, i, len);
    }
}
// 調整堆
function heapify(arr, i, len) {
    let left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
    //通過2次判斷選出父節點和2個子節點中最大的一個
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
    //將最大的節點和父節點交換順序
    if (largest != i) {
        swap(arr, i, largest);
        //遞回對換順序的節點進行調整，使其還是大頂堆
        heapify(arr, largest, len);
    }
}
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function heapSort(arr) {
    // 建立大頂堆
    buildMaxHeap(arr);
    let len = arr.length
    //每次建立一個大頂堆，將最大的元素（堆頂元素）放入尾部達到排序效果
    for (let i = len - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0, len);
    }
    return arr;
}
console.log(heapSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))

特點

時間復雜度：O(N*logN)
空間復雜度：O(1)
穩定性：不穩定

插入排序

直接插入排序

每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序（默認是從后向前比較），

圖解

藍色部分為無序表，黃色部分為有序表：

在這里插入圖片描述

js實作

使用的是一個陣列，將陣列下標為i之前的為有序，之后為無序，

注意用的是改變原陣列的方法，可以不用回傳，

//將陣列下標為的x元素取出插入為y的
function popInsert(arr,x,y){
    arr.splice(y,0,...arr.splice(x,1))
}
function insertSort(arr){
    let t=arr.length
    for (let i=1;i<t;i++){
        let j=i-1
        do{
            if(arr[j]<arr[i]){
                popInsert(arr,i,j+1)
                break
            }
            j--
            //比較到下標為0的時候直接插入
            if(j<0){
                popInsert(arr,i,0)
            }
        }while(j>=0)
    }
    return arr
}
console.log(insertSort([3,1,2,3134,113,342,123412,55,111,4,234,5,5]))

特點

元素集合越接近有序，直接插入排序演算法的時間效率越高
時間復雜度：O(N^2)
空間復雜度：O(1)，它是一種穩定的排序演算法
穩定性：穩定

希爾排序

希爾排序在直接排序之前，進行預排列，將某些極端資料更快的排列到數列前面，構成一個接近排列好的序列，最后再進行一次直接插入排序，

預排列的原理也是插入排列，只不過這里的將陣列分成了gap組，分別對每一個小組進行插入排序，

圖解

對于升序，當gap從5 – 2 – 1的程序中，排在后面的數值小的數能更快排到前面，當gap為1的時候實際上就是進行了一次插入排序

js實作

每次將下標位置差為gap的數進行直接排序，其中第一次gap=Math.floor(arr.length/2)，之后每次gap=Math.floor(gap/2)，

function shellsSort(arr){
    let t=arr.length
    let gap=t
    let tmp
    //gap取不同值的排序
    do{
        //每次的分組
        gap=Math.floor(gap/2)
        for(let i=gap;i<t;i++){
            //只和上一個間距為gap的元素進行比較，判斷是否要插入，還是維持原順序
            if(arr[i-gap]>arr[i]){
                tmp = arr[i]
                let j=i-gap
                //將插入位置之后的元素整體后移
                do{
                    arr[j+gap]=arr[j]
                    j-=gap
                }while(j>=0&&arr[j]>tmp)
                //插入對應位置
                arr[j+gap]=tmp
            }
        }
    }while(gap>1)
    return arr
}
console.log(shellsSort([3,1,2,3134,113,342,123412,55,111,4,234,5,5]))

特點

希爾排序是對直接插入排序的優化當gap > 1時都是預排序，目的是讓陣列更接近于有序，當gap == 1時，陣列已經接近有序的了，這樣就會很快，這樣整體而言，可以達到優化的效果，我們實作后可以進行性能測驗的對比
希爾排序的時間復雜度不好計算，因為gap的取值方法很多，一般來說為O(n^1.3)
穩定性：不穩定

其它排序

桶排序

選出待排序元素中的最大最小值，根據最大最小值劃分多個區域（桶），通過映射函式將元素分到不同區域（桶）中，對區域（桶）中的元素進行排序后，依次取出即可，

圖解

將排序的元素放入對應的桶中

對桶中的元素進行排序

js實作

//插入排序
function insertionSort(arr) {
    let len = arr.length;
    let preIndex, current;
    for (let i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}
function bucketSort(arr, bucketSize) {
    let minValue = arr[0];
    let maxValue = arr[0];
    //找到陣列中的最大和最小值
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < minValue) {
            minValue = arr[i];
        } else if (arr[i] > maxValue) {
            maxValue = arr[i];
        }
    }
    //桶的初始化
    let DEFAULT_BUCKET_SIZE = 5;
    // 設定一個桶能存盤的默認數量為5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    //桶的個數
    let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    let buckets = new Array(bucketCount);
    for (let i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
    //利用映射函式將元素分配到各個桶中
    for (let i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
    //洗掉arr陣列中的所有元素
    arr.length = 0;
    for (let i = 0; i < buckets.length; i++) {
        // 對每個桶進行排序，這里使用了插入排序
        insertionSort(buckets[i]);
        // 將每個桶的資料從小到大拿出                    
        for (let j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);
        }
    }
    return arr;
}
console.log(bucketSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))

特點

時間復雜度：O(N+K)
空間復雜度：O(N+K)
穩定性：穩定

基數排序

確定最大數的位數，先按第一位進行排序，在按第二位進行排序，直到按最后一位進行排序為止，

圖解

js實作

function radixSort(arr) {
    let counter = [];
    //獲取元素的最大位數
    let maxDigit = `${Math.max(...arr)}`.length
    let mod = 10;
    let dev = 1;
    //從小到大依次對元素的每一位進行回圈排序
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for (let j = 0; j < arr.length; j++) {
            //獲取元素對應位上的數值
            let bucket = parseInt((arr[j] % mod) / dev);
            if (counter[bucket] == null) {
                counter[bucket] = [];
            }
            //根據對應的數值，將元素放入對應的桶中
            counter[bucket].push(arr[j]);
        }
        let pos = 0;
        //從0~9的桶中將元素取出，完成一次排序
        for (let j = 0; j < counter.length; j++) {
            let value = null;
            if (counter[j] != null) {
                while ((value = counter[j].shift()) != null) {
                    arr[pos++] = value;
                }
            }
        }
    }
    return arr;
}
console.log(radixSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5], 6))

特點

時間復雜度：O(N*K)
空間復雜度：O(N+K)
穩定性：穩定

歸并排序

申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；
設定兩個指標，最初位置分別為兩個已經排序序列的起始位置；
比較兩個指標所指向的元素，選擇相對小的元素放入到合并空間，并移動指標到下一位置；
重復步驟 3 直到某一指標達到序列尾；
將另一序列剩下的所有元素直接復制到合并序列尾，

圖解

js實作

function mergeSort(arr) {  // 采用自上而下的遞回方法
    let len = arr.length;
    if (len < 2) {
        return arr;
    }
    let middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
    let result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}
console.log(mergeSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5], 6))

特點

時間復雜度：O(N*logN)
空間復雜度：O(N)
穩定性：穩定

計數排序

1.找出待排序的陣列中最大和最小的元素

2.統計陣列中每個值為i的元素出現的次數，存入陣列C的第i項

3.對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）

4.反向填充目標陣列：將每個元素i放在新陣列的第C(i)項，每放一個元素就將C(i)減去1

圖解

js實作

function countingSort(arr) {
    let maxValue = Math.max(...arr)
    let bucket = new Array(maxValue + 1),
        sortedIndex = 0;
    arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (let i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (let j = 0; j < bucketLen; j++) {
        while (bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}
console.log(countingSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))

特點

時間復雜度：O(N+K)
空間復雜度：O(K)
穩定性：穩定

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/393135.html

標籤：java

上一篇：《23種設計模式（Java版）》| 工廠模式（內附原始碼案例）。

下一篇：【JDBC】The new driver class is `com.mysql.cj.jdbc.Driver‘. The driver is automatically

十大排序總結（js實作、穩定性、內外部排序區別、時間空間復雜度、冒泡、快速、直接選擇、堆、直接插入、希爾、桶、基數、歸并、計數排序）

排序相關概念

穩定性

內部排序

外部排序

十種排序演算法特點總結

交換排序

冒泡排序（陣列sort方法的原理）

圖解

js實作

特點

快速排序

圖解

js實作

特點

選擇排序

直接選擇排序

圖解

js實作

特點

堆排序

大（小）頂堆

非葉節點

js實作

特點

插入排序

直接插入排序

圖解

js實作

特點

希爾排序

圖解

js實作

特點

其它排序

桶排序

圖解

js實作

特點

基數排序

圖解

js實作

特點

歸并排序

圖解

js實作

特點

計數排序

圖解

js實作

特點