摘要:對每一對相鄰元素作同樣的工作,從開始第一對一直到結尾的最后一對,如此將最大的數放在后面。持續每次對元素重復上面的步驟,直到排序完成。排序步驟將第一待排序序列第一個元素看做一個有序序列,把第二個元素到最后一個元素當成是未排序序。
前端攻城獅——學習常用的排序算法 一、冒泡排序
優點:
所有排序中最簡單的,易于理解;
缺點:
時間復雜度O(n^2),平均來說是最差的一種排序方式;
因為在默認情況下,對于已經排好序的部分,此排序任然會進行比較(當然可以進行改進優化)
算法步驟:
比較相鄰的元素,如果第一個比第二個大,就交換他們兩個。
對每一對相鄰元素作同樣的工作,從開始第一對一直到結尾的最后一對,如此將最大的數放在后面。
對所有的元素重復以上的步驟,除了最后一個。
持續每次對元素重復上面的步驟,直到排序完成。
原理分析:
通過比較兩個相鄰的項,(由小到大排序)如果第一個比的二個大,則交換它們的位置元素項向上移動至正確的順序,就好像氣泡升至表面,冒泡也因此得名。
const bubbleSort = (arr) => { const length= arr.length; for (let i = 0; iarr[j+1]){ let swap = arr[j]; arr[j] = arr[j+1]; arr[j+1] = swap; } } } }
改進優化:
默認上述代碼,對于第一輪之后的循環任然會進行和全部元素的比較,但其實之前的循環已經將器排序正確了,所以可以從內循環中減去外循環已經進行過的輪數,從而避免不必要的比較
const bubbleSort = (arr) => { const length= arr.length; for (let i = 0; i二、選擇排序arr[j+1]){ let swap = arr[j]; arr[j] = arr[j+1]; arr[j+1] = swap; } } } }
原理:
進行原地址比較,找到數據結構中最小值并放在第一位,接著在剩下的中找到第二個最小值放在第二位,依次類推;
代碼實現:
function selectionSort(arr) { var length= arr.length; var minIndex; for (var i = 0; i < length - 1; i++) { minIndex = i; for (var j = i + 1; j < length; j++) { if (arr[j] < arr[minIndex]) { // 尋找最小的數 minIndex = j; // 將最小數的索引保存 } } if(i != minIndex){ var temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } return arr; }三、插入排序
原理:
通過構建有序序列,對于未排序數據,在已排序序列中從后向前掃描,找到相應位置并插入。
排序步驟:
將第一待排序序列第一個元素看做一個有序序列,把第二個元素到最后一個元素當成是未排序序。
從頭到尾依次掃描未排序序列,將掃描到的每個元素插入有序序列的適當位置。(如果待插入的元素與有序序列中的某個元素相等,則將待插入元素插入到相等元素的后面。)
代碼實現
function insertionSort(arr) { var len = arr.length; var preIndex, current; for (var 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 mergeSort(arr) { // 采用自上而下的遞歸方法,數組拆分 var len = arr.length; if(len < 2) { return arr; } var middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); } //合并數組,并進行排序 function merge(left, right) { var 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; }
原理圖
五、快速排序原理:
快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分為兩個子串行(sub-lists)。
排序步驟:
首先,從數組中選擇中間一項作基數;
然后,創建兩個指針,左邊一個指向數組的第一項,右邊一個指向數組的最后一項;
移動左指針直到找到一個比基數大的元素,移動右指針,直到找到一個比基數小的元素;然后交換它們;
重復以上步驟,直到左指針超過了右指針;(這個過程將使得比基數小的樹都在基數的前面,較大的數都在基數的后面)
最后,對劃分后的小數組(比基數小的值組成的子數組,以及比基數大的值組成是子數組)重復之前的兩個步驟,直到數組已經完全排序。
代碼實現
function quickSort(arr, left, right) { var len = arr.length, partitionIndex, left = typeof left != "number" ? 0 : left, right = typeof right != "number" ? len - 1 : right; if (left < right) { partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex-1); quickSort(arr, partitionIndex+1, right); } return arr; } function partition(arr, left ,right) { // 分區操作 var pivot = left, // 設定基準值(pivot) index = pivot + 1; for (var i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index-1; } function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function partition2(arr, low, high) { let pivot = arr[low]; while (low < high) { while (low < high && arr[high] > pivot) { --high; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { ++low; } arr[high] = arr[low]; } arr[low] = pivot; return low; } function quickSort2(arr, low, high) { if (low < high) { let pivot = partition2(arr, low, high); quickSort2(arr, low, pivot - 1); quickSort2(arr, pivot + 1, high); } return arr; }
原理圖
持續更新中~喜歡留下個贊哦!
往期經典好文推薦——前端JavaScript面試寶典
我的成長日記——我的前端面試日記(1)
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/116732.html
摘要:對每一對相鄰元素作同樣的工作,從開始第一對一直到結尾的最后一對,如此將最大的數放在后面。持續每次對元素重復上面的步驟,直到排序完成。排序步驟將第一待排序序列第一個元素看做一個有序序列,把第二個元素到最后一個元素當成是未排序序。 前端攻城獅——學習常用的排序算法 一、冒泡排序 優點: 所有排序中最簡單的,易于理解; 缺點: 時間復雜度O(n^2),平均來說是最差的一種排序方式; 因為在...
摘要:對每一對相鄰元素作同樣的工作,從開始第一對一直到結尾的最后一對,如此將最大的數放在后面。持續每次對元素重復上面的步驟,直到排序完成。排序步驟將第一待排序序列第一個元素看做一個有序序列,把第二個元素到最后一個元素當成是未排序序。 前端攻城獅——學習常用的排序算法 一、冒泡排序 優點: 所有排序中最簡單的,易于理解; 缺點: 時間復雜度O(n^2),平均來說是最差的一種排序方式; 因為在...
摘要:算法描述冒泡排序是一種簡單的排序算法。算法描述和實現一般來說,插入排序都采用在數組上實現。平均情況希爾排序年發明第一個突破的排序算法是簡單插入排序的改進版它與插入排序的不同之處在于,它會優先比較距離較遠的元素。 前言 讀者自行嘗試可以想看源碼戳這,博主在github建了個庫,讀者可以Clone下來本地嘗試。此博文配合源碼體驗更棒哦~~~ 個人博客:Damonare的個人博客 原文地址:...
摘要:使用來描述算法和數據結構的教程很少,目前市面上用描述算法和數據結構的書屈指可數,并且就我看過的那本而言我只看過數據結構與算法語言描述質量實在堪憂。 使用JavaScript來描述算法和數據結構的教程很少, 目前市面上用JS描述算法和數據結構的書屈指可數,并且就我看過的那本而言(我只看過《數據結構與算法 JavaScript 語言描述》)質量實在堪憂。碰巧有次看到Nicolas博客中的C...
閱讀 3192·2023-04-26 01:39
閱讀 3345·2023-04-25 18:09
閱讀 1612·2021-10-08 10:05
閱讀 3228·2021-09-22 15:45
閱讀 2758·2019-08-30 15:55
閱讀 2393·2019-08-30 15:54
閱讀 3167·2019-08-30 15:53
閱讀 1324·2019-08-29 12:32