摘要:冒泡排序冒泡算法是比較相鄰的兩項,如果前者比后者大,就交換他們。插入排序最好情況下時間復雜度是,其他情況下也都是。代碼演示插入排序歸并排序原生里面的方法,在里面是用歸并排序實現的,而在里面是用快速排序的變體來實現的。
1、冒泡排序
冒泡算法是比較相鄰的兩項,如果前者比后者大,就交換他們。 假設一共有n項,那么一共需要n-1趟,第一趟需要交換n-1次,但是第一趟結束后,最后一項基本確定就是最大項了,所以第二次需要交換n-2次,第i次交換n-i次。
這種排序最好情況下時間復雜度是O(n),一般情況下時間復雜度是O(n2),最差情況下也是O(n2)。 這里是代碼演示:
冒泡排序
2、選擇排序
選擇排序是找到最小的一項,然后和第一項交換位置,然后找到第二小的和第二項交換,依次類推,一共需要n-1次。
選擇排序在所有情況下空間復雜度都是O(n2)。 代碼演示:
選擇排序
3、插入排序
插入排序是將前面的項看做數組,然后后面的項根據大小插入到對應的位置。比如第二項和第一項對比,他該插到第一項前面還是后面呢?第三項該插到一二項的哪個地方? 這個一般也需要插入n-1次。
插入排序最好情況下時間復雜度是O(n),其他情況下也都是O(n2)。 代碼演示:
插入排序
4、歸并排序
原生js里面的sort方法,在firefox里面是用歸并排序實現的,而在chrome里面是用快速排序的變體來實現的。
歸并排序是一種分治的算法,他是將一個大數組分成無數的小數組,如果小數組里面只有一項,那么直接返回,如果大于一項,就繼續分,接著小數組合并成一個大數組,合并的時候左右會進行比較大小,然后排序 代碼演示:
歸并排序
5、快速排序
快速排序也使用了分治的算法,也是把大數組分成小數組. 它會選擇一個中間元,創建兩個左右指針,然后分別從左右開始出發,如果左指針遇到比中間元大的數,它會停下來,而右邊的如果遇到比中間元小的數,它也會停下來,然后兩者交換位置。 接著兩個指針繼續前進,直到左指針超過了右指針,這樣左邊的數就會小于中間元,右邊的數都會大于中間元,接下來分成左右數組,然后再進行上面的操作,直到數組完全排序。
代碼演示:快速排序
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/50031.html
摘要:上一篇數據結構與算法樹寫在前面這是學習數據結構與算法的最后一篇博客,也是在面試中常常會被問到的一部分內容排序和搜索。 上一篇:JS數據結構與算法_樹 寫在前面 這是《學習JavaScript數據結構與算法》的最后一篇博客,也是在面試中常常會被問到的一部分內容:排序和搜索。在這篇博客之前,我每每看到排序頭就是大的,心里想著類似冒泡排序,兩層遍歷啪啪啪就完事了,然后再也無心去深入研究排序相...
摘要:介紹排序算法是算法中最常見的算法之一,我這里要介紹的是排序算法中的三種基本算法冒泡排序選擇排序插入排序,在文章的后面我會對三種算法的速度進行對比。 1.介紹 排序算法是算法中最常見的算法之一,我這里要介紹的是排序算法中的三種基本算法:冒泡排序、選擇排序、插入排序,在文章的后面我會對三種算法的速度進行對比。 2.冒泡排序 冒泡排序其名來源與其算法實現,會使得數組中的元素一個個從數組一端漂...
摘要:本文對一些排序算法進行了簡單分析,并給出了的代碼實現。平均時間復雜度不好分析,它是冒泡排序是穩定的排序算法。冒泡排序是原地排序算法原地排序指的是空間復雜度是的排序算法。歸并排序,會將數組從中間分成左右兩部分。 本文對一些排序算法進行了簡單分析,并給出了 javascript 的代碼實現。因為本文包含了大量的排序算法,所以分析不會非常詳細,適合有對排序算法有一定了解的同學。本文內容其實不...
本篇有7k+字, 系統梳理了js中常見的12種排序算法。除了基本排序算法,文章還包含了希爾排序、堆排序、桶排序等較為復雜的排序實現,如果喜歡請點贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導讀 排序算法可以稱得上是我的盲點, 曾幾何時當我知道Chrome的Array.prototype.sort使用了快速排序時, 我的內心是奔潰的(啥是快排, 我只知道...
閱讀 3686·2021-09-07 10:19
閱讀 3627·2021-09-03 10:42
閱讀 3584·2021-09-03 10:28
閱讀 2548·2019-08-29 14:11
閱讀 809·2019-08-29 13:54
閱讀 1594·2019-08-29 12:14
閱讀 417·2019-08-26 12:12
閱讀 3614·2019-08-26 10:45