JS—關于排序

一、冒泡排序

原理：相鄰兩元素之間兩兩比較，比較出大值進行賦值互換，再依次與相鄰的元素比較，層層遞進，#互換元素位置，相互賦值，

時間復雜度：最好O(n)，最差O(n^2)

1、比較相鄰的兩個元素，如果前一個比后一個大，則交換位置，
2、比較完第一輪的時候，最后一個元素是最大的元素，
3、這時候最后一個元素是最大的，所以最后一個元素就不需要參與比較大小，

const bubbleSort = (arr)=>{
    for(let i = 0 ; i < arr.length - 1 ; i++){
        for(let j = 0 ; j < arr.length - 1 - i ; j++){
            if(arr[j] > arr[j + 1]){
                var temp = 0;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

console.log(bubbleSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]

決議

兩個回圈，當i=0的時候，里面的回圈完整執行，從j=0執行到j=7，結果是將最大的數排到了最后，當i=1的時候，里面的回圈再次完整執行，由于最大的數已經在最后了，沒有必要去比較陣列的最后兩項，這也是j<arr.length-1-i的巧妙之處，

二、選擇排序

原理：先定義一個元素的最大值或最小值，拿每個元素與最值比較，取大值放到陣列最右端，或者最小值放到陣列最左端，層層比較，#互換元素下標位置，再賦值，

時間復雜度：O(n^2)

const selectionSort = (arr)=>{
    let minIndex,temp;
    for(let i = 0 ; i < arr.length ; i++){
        minIndex = i;
        for(let j = i + 1 ; j < arr.length ; j++){
            if(arr[j] < arr[minIndex]){
                minIndex = j; 
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

console.log(selectionSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]

決議

首先從原始陣列中找到最小的元素，并把該元素放在陣列的最前面，然后再從剩下的元素中尋找最小的元素，放在之前最小元素的后面，直到排序完畢，

minIndex始終保存著最小值的位置的索引，隨著i的自增，遍歷的陣列長度越來越短，直到完成排序，

三、歸并排序

歸并排序（MERGE-SORT）是利用歸并的思想實作的排序方法，
該演算法采用經典的分治（divide-and-conquer）策略
（分治法將問題分(divide)成一些小的問題然后遞回求解，
而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)，

歸并排序采用的是分治的思想，首先是“分”，將一個陣列反復二分為兩個小陣列，直到每個陣列只有一個元素；其次是“治”，從最小陣列開始，兩兩按大小順序合并，直到并為原始陣列大小，下面是圖解：

“分”就是將原始陣列逐次二分，直到每個陣列只剩一個元素，一個元素的陣列自然是有序的，所以就可以開始“治”的程序了，

時間復雜度分析：分的程序需要三步：log8 = 3，而每一步都需要遍歷一次8個元素，所以8個元素共需要運行 8log8 次指令，那么對于 n 個元素，時間復雜度為 O(nlogn)，

 “治”實際上是將已經有序的陣列合并為更大的有序陣列，那怎么做呢?就是創建一個新陣列，比較left[0]和right[0] ，那個比較小就將那個的值放進新陣列，然后再繼續比較left[0]和right[1]，或者是left[1]和right[0]，可以看出陣列left，right都只需遍歷一遍，所以對兩個有序陣列的排序的時間復雜度為O(n)，

一、遞回分解

 二、合并為有序陣列

const mergeSort = (arr)=>{
    let len = arr.length;
    if(len < 2){
        return arr;
    }
    let mid = Math.floor(len/2);
    //拆分成兩個子陣列
    let left = arr.slice(0,mid);
    let right = arr.slice(mid,len);
    //遞回拆分
    let mergeSortLeft = mergeSort(left);
    let mergeSortRight = mergeSort(right);
    //組合
    return merge(mergeSortLeft,mergeSortRight)
}

const merge = (left,right)=>{
    const arr1 = [];
    while(left.length && right.length){
        // 注意: 判斷的條件是小于或等于，如果只是小于，那么排序將不穩定.
        if(left[0]<=right[0]){
            //每次都要洗掉left或者right的第一個元素，將其加入arr1中
            arr1.push(left.shift());
        }else{
            arr1.push(right.shift());
        }
    }
    //將剩下的元素加上
    while(left.length) arr1.push(left.shift());
    while(right.length) arr1.push(right.shift());

    return arr1;
}


console.log(mergeSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]

參考： https://www.cnblogs.com/lyt0207/p/12489144.html

四、排序二叉樹

標籤：JavaScript

上一篇：JS JSON格式化列印：JSON.stringify方法

下一篇：AJAX（Web資料互動方式）