算法：排序算法總結（JavaScript描述）

dkzwm 發布于2019-08-23 11:45 / 2345人閱讀

摘要：二代碼簡單選擇排序一分析循環次，每一次的當前項與其之后的項作比較，找出其中最小的那個，與當前項交換。二代碼希爾排序是一種改進版的插入排序，縮小增量排序。這樣做的目的是因為，直接插入排序在序列基本有序時效率最高。

排序算法	平均情況	最好情況	最壞情況	輔助空間	穩定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	穩定
簡單選擇排序	O(n^2)	O(n^2)	O(n^2)	O(1)	穩定
直接插入排序	O(n^2)	O(n)	O(n^2)	O(1)	穩定
希爾排序	O(nlogn)~O(n^2)	O(n^1.3)	O(n^2)	O(1)	不穩定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不穩定
歸并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	穩定
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(nlogn)~O(n)	不穩定

簡單算法：冒泡、簡單選擇、直接插入
改進算法：希爾、堆、歸并、快速

后三種改進算法比希爾算法效率高，但最好的情況下，冒泡和直接插入最有效，因此如果數組基本有序，則需要考慮簡單算法

1. 冒泡排序

一、分析

冒泡arr.length-1趟；

第i趟，比較arr.length-i-1次，兩兩比較，反序則交換位置。

改進：為了避免已經有序的情況下進行無意義的兩兩比較，用flag標志上一趟是否有交換，沒有交換則已經是有序數組，退出循環。

二、代碼

    function bubbleSort(arr){
        var flag=true;
        for(let i=0;iarr[j+1]){
                    [arr[j],arr[j+1]]=[arr[j+1],arr[j]];
                    flag=true;
                }
            }
        }
        return arr;
    }

2. 簡單選擇排序

一、分析

循環arr.length-1次，每一次的當前項與其之后的項作比較，找出其中最小的那個，與當前項交換。

二、代碼

    function selectSort(arr){
        var min=0;
        for(let i=0;i
3. 直接插入排序
一、分析

從數組的第二項開始，循環arr.length-1次；
將當前項的值賦值給臨時變量：（留出一個“坑”）為了前面大于當前項的項能夠后移；
當前項與其前面的項比較，如果大于當前項后移，直到找到小于當前項的那個，將當前項插入其后；
如果前面沒有小于當前項的，前面項全部后移以為，當前項就插入位置0處。

二、代碼
    function insertSort(arr){
        for(let i=1;i=0&&arr[j]>temp){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=temp;
        }
        return arr;
    }
4. 希爾排序
??是一種改進版的插入排序，“縮小增量排序”。
一、分析

通過增量將待排序列分割成若干個子序列，每個子序列進行插入排序；
縮小增量，重復步驟1，直到增量不大于0；
ps：增量等于1時，進行了一次全排的直接插入排序。這樣做的目的是因為，直接插入排序在序列基本有序時效率最高。

二、代碼
    function shellSort(arr){
        for(let increment=Math.floor(arr.length/2);increment>0;increment=Math.floor(increment/2)){
            for(let i=increment;i=0&&arr[j]>temp){
                    arr[j+increment]=arr[j];
                    j-=increment;
                }
                arr[j+increment]=temp;
            }
        }
        return arr;
    }
5. 堆排序
一、分析

將待排序列構造成一個大頂堆（位置0處，也就是堆頂，為最大數）；
將arr[0]與arr[arr.length-1]進行交換，此時數組尾為最大值；
調整0~arr.length-2成一個大頂堆，繼續2，直到全部排完。

二、代碼
    function heapSort(arr){
        //1. 構造大頂堆
        //2. 頂值最大，交換到最末尾
        //3. 調整大頂堆
        var len=arr.length;
        for(let i=Math.floor(len/2)-1;i>=0;i--){
            heapAdjust(arr,i,len);
        }
        for(let i=arr.length-1;i>0;i--){
            [arr[0],arr[i]]=[arr[i],arr[0]];
            heapAdjust(arr,0,i);
        }
        return arr;
    }
    function heapAdjust(arr,pos,len){
        var root=pos;
        for(let i=2*pos+1;i
6. 歸并排序
一、分析

將兩個有序數組合成一個有序數組：歸并。
將一個數組分割成長度為1的數組，就可以當做它是一個有序數組，兩兩合并，就成了一個長度為2的有序數組，再兩兩合并，直到排序完成。

二、代碼
    function mergeSort(arr){
        if(arr.length<=1){return arr};

        let mid=Math.floor(arr.length/2);
        let left=arr.slice(0,mid);
        let right=arr.slice(mid);
        // console.log(left+"+"+right);
        return merge(mergeSort(left),mergeSort(right));
    }
    function merge(left,right){
        var result=[];
        while(left.length>0&&right.length>0){
            if(left[0]
7. 快速排序
一、分析

找基準
小于基準的放左邊，大于基準的放右邊；
遞歸基準左、右無序序列找基準；
直到輸入數組長度為1，跳出遞歸。

二、代碼
    function qSort1(arr){
        if(arr.length<=1){return arr;}

        let pivot=arr[0];
        let left=[];let right=[];
        for(let i=1;i=arr[low]){
                low++
            }
            [arr[low],arr[high]]=[arr[high],arr[low]];
        }

        return low;
    }

云服務器 GPU云服務器排序算法總結算法c語言描述自然語言算法描述最大流算法總結

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

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

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

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

Binguner 2019-08-20 11:05 評論0 收藏0
常用排序算法之JavaScript實現

摘要：代碼實現六堆排序算法簡介堆排序是指利用堆這種數據結構所設計的一種排序算法。九計數排序算法簡介計數排序是一種穩定的排序算法。計數排序不是比較排序，排序的速度快于任何比較排序算法。贊助我以寫出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡介插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它...

jerry 2019-08-21 12:27 評論0 收藏0
用JavaScript實現插入排序

摘要：實現插入排序插入排序是一種非常簡單的算法，最適合大部分已經被排好序的數據。由此才有了這個名字插入排序。插入排序的最壞情況是輸入的數組是按逆序排序的。總結當輸入的數組已經大部分被排好序時，插入排序的效果最佳。翻譯：瘋狂的技術宅https://medium.com/@jimrottin... 本文首發微信公眾號：前端先鋒歡迎關注，每天都給你推送新鮮的前端技術文章插入排序的工作原理...

LittleLiByte 2019-08-26 13:44 評論0 收藏0
JavaScript 數據結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 評論0 收藏0