新聞資訊  快訊  焦點  財經  政策  社會
互 聯 網   電商  金融  數據  計算  技巧
生活百科  科技  職場  健康  法律  汽車
手機百科  知識  軟件  修理  測評  微信
軟件技術  應用  系統  圖像  視頻  經驗
硬件技術  知識  技術  測評  選購  維修
網絡技術  硬件  軟件  設置  安全  技術
程序開發  語言  移動  數據  開源  百科
安全防護  資訊  黑客  木馬  病毒  移動
站長技術  搜索  SEO  推廣  媒體  移動
財經百科  股票  知識  理財  財務  金融
教育考試  育兒  小學  高考  考研  留學
您當前的位置:首頁 > IT百科 > 程序開發 > 算法

常用排序算法之JavaScript實現

時間:2019-11-22 13:12:00  來源:  作者:

?????¨????o?????3??1?JavaScript?????°

筆試面試經常涉及各種算法,本文簡要介紹常用的一些算法,并用JAVAScript實現。

1、插入排序

1)算法簡介插入排序(Insertion-Sort)的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列,對于未排序數據,在已排序序列中從后向前掃描,找到相應位置并插入。插入排序在實現上,通常采用in-place排序(即只需用到O(1)的額外空間的排序),因而在從后向前掃描過程中,需要反復把已排序元素逐步向后挪位,為最新元素提供插入空間。2)算法描述和實現一般來說,插入排序都采用in-place在數組上實現。具體算法描述如下:

  • 從第一個元素開始,該元素可以認為已經被排序;

  • 取出下一個元素,在已經排序的元素序列中從后向前掃描;

  • 如果該元素(已排序)大于新元素,將該元素移到下一位置;

  • 重復步驟3,直到找到已排序的元素小于或者等于新元素的位置;

  • 將新元素插入到該位置后;

  • 重復步驟2~5。

  • JavaScript代碼實現:

  • functioninsertionSort(array){ if(Object.prototype.toString.call(array).slice(8, -1) === 'Array'){ for(vari = 1;i < array.length;i++){ varkey = array[i]; varj = i - 1; while(j >= 0 && array[j] > key){ array[j + 1] = array[j]; j--; } array[j + 1] = key; } returnarray; }else{ return'array is not an Array!'; }}


  • 3)算法分析

  • 最佳情況:輸入數組按升序排列。T(n) = O(n)

  • 最壞情況:輸入數組按降序排列。T(n) = O(n2)

  • 平均情況:T(n) = O(n2)

二、二分插入排序

1)算法簡介二分插入(Binary-insert-sort)排序是一種在直接插入排序算法上進行小改動的排序算法。其與直接插入排序算法最大的區別在于查找插入位置時使用的是二分查找的方式,在速度上有一定提升。2)算法描述和實現一般來說,插入排序都采用in-place在數組上實現。具體算法描述如下:

  • 從第一個元素開始,該元素可以認為已經被排序;

  • 取出下一個元素,在已經排序的元素序列中二分查找到第一個比它大的數的位置;

  • 將新元素插入到該位置后;

  • 重復上述兩步。

  • JavaScript代碼實現:

  • functionbinaryInsertionSort(array){ if(Object.prototype.toString.call(array).slice(8, -1) === 'Array'){ for(vari = 1;i < array.length;i++){ varkey = array[i],left = 0,right = i - 1; while(left <= right){ varmiddle = parseInt((left + right) / 2); if(key < array[middle]){ right = middle - 1; }else{ left = middle + 1; } } for(varj = i - 1;j >= left;j--){ array[j + 1] = array[j]; } array[left] = key; } returnarray; }else{ return'array is not an Array!'; }}


  • 3)算法分析

  • 最佳情況:T(n) = O(nlogn)

  • 最差情況:T(n) = O(n2)

  • 平均情況:T(n) = O(n2)

三、選擇排序

1)算法簡介選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續尋找最小(大)元素,然后放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。2)算法描述和實現n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體算法描述如下:

  • 初始狀態:無序區為R[1..n],有序區為空;

  • 第i趟排序(i=1,2,3…n-1)開始時,當前有序區和無序區分別為R[1..i-1]和R(i..n)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k],將它與無序區的第1個記錄R交換,使R[1..i]和R[i+1..n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區;

  • n-1趟結束,數組有序化了。

  • JavaScript代碼實現:

  • functionselectionSort(array){ if(Object.prototype.toString.call(array).slice(8, -1) === 'Array'){ varlen = array.length,temp; for(vari = 0;i < len - 1;i++){ varmin = array[i]; for(varj = i + 1;j < len;j++){ if(array[j] < min){ temp = min; min = array[j]; array[j] = temp; } } array[i] = min; } returnarray; }else{ return'array is not an Array!'; }}


  • 3)算法分析

  • 最佳情況:T(n) = O(n2)

  • 最差情況:T(n) = O(n2)

  • 平均情況:T(n) = O(n2)

四、冒泡排序

1)算法簡介冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列,一次比較兩個元素,如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。2)算法描述和實現具體算法描述如下:

  • 比較相鄰的元素。如果第一個比第二個大,就交換它們兩個;

  • 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最后一對,這樣在最后的元素應該會是最大的數;

  • 針對所有的元素重復以上的步驟,除了最后一個;

  • 重復步驟1~3,直到排序完成。

  • functionbubbleSort(array){ if(Object.prototype.toString.call(array).slice(8, -1) === 'Array'){ varlen = array.length,temp; for(vari = 0;i < len - 1;i++){ for(varj = len - 1;j >= i;j--){ if(array[j] < array[j - 1]){ temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } returnarray; }else{ return'array is not an Array!'; }}


  • 3)算法分析

  • 最佳情況:T(n) = O(n)

  • 最差情況:T(n) = O(n2)

  • 平均情況:T(n) = O(n2)

五、快速排序

1)算法簡介快速排序的基本思想:通過一趟排序將待排記錄分隔成獨立的兩部分,其中一部分記錄的關鍵字均比另一部分的關鍵字小,則可分別對這兩部分記錄繼續進行排序,以達到整個序列有序。2)算法描述和實現快速排序使用分治法來把一個串(list)分為兩個子串(sub-lists)。具體算法描述如下:

  • 從數列中挑出一個元素,稱為 “基準”(pivot);

  • 重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的后面(相同的數可以到任一邊)。在這個分區退出之后,該基準就處于數列的中間位置。這個稱為分區(partition)操作;

  • 遞歸地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列排序。

  • //方法一functionquickSort(array,left,right){ if(Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeofleft === 'number' && typeofright === 'number'){ if(left < right){ varx = array[right],i = left - 1,temp; for(varj = left;j <= right;j++){ if(array[j] <= x){ i++; temp = array[i]; array[i] = array[j]; array[j] = temp; } } quickSort(array,left,i - 1); quickSort(array,i + 1,right); }; }else{ return'array is not an Array or left or right is not a number!'; }} varaaa = [3,5,2,9,1];quickSort(aaa,0,aaa.length - 1);console.log(aaa);


  • //方法二varquickSort = function(arr){  if(arr.length <= 1){returnarr;}  varpivotIndex = Math.floor(arr.length / 2);  varpivot = arr.splice(pivotIndex,1)[0];  varleft = [];  varright = [];  for(vari = 0;i < arr.length;i++){    if(arr[i] < pivot){      left.push(arr[i]);    }else{      right.push(arr[i]);    }  }  returnquickSort(left).concat([pivot],quickSort(right));};3)算法分析

  • 最佳情況:T(n) = O(nlogn)

  • 最差情況:T(n) = O(n2)

  • 平均情況:T(n) = O(nlogn)

六、堆排序

1)算法簡介堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構,并同時滿足堆積的性質:即子結點的鍵值或索引總是小于(或者大于)它的父節點。2)算法描述和實現具體算法描述如下:

  • 將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆,此堆為初始的無序區;

  • 將堆頂元素R[1]與最后一個元素R[n]交換,此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n];

  • 由于交換后新的堆頂R[1]可能違反堆的性質,因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆,然后再次將R[1]與無序區最后一個元素交換,得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1,則整個排序過程完成。

  • /*方法說明:堆排序@param array 待排序數組*/ functionheapSort(array){ if(Object.prototype.toString.call(array).slice(8, -1) === 'Array'){//建堆 varheapSize = array.length,temp; for(vari = Math.floor(heapSize / 2);i >= 0;i--){ heapify(array,i,heapSize); } //堆排序 for(varj = heapSize - 1;j >= 1;j--){ temp = array[0]; array[0] = array[j]; array[j] = temp; heapify(array,0, --heapSize); } }else{ return'array is not an Array!'; }}/*方法說明:維護堆的性質@param arr 數組@param x 數組下標@param len 堆大小*/functionheapify(arr,x,len){ if(Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeofx === 'number'){ varl = 2 * x,r = 2 * x + 1,largest = x,temp; if(l < len && arr[l] > arr[largest]){ largest = l; } if(r < len && arr[r] > arr[largest]){ largest = r; } if(largest != x){ temp = arr[x]; arr[x] = arr[largest]; arr[largest] = temp; heapify(arr,largest,len); } }else{ return'arr is not an Array or x is not a number!'; }


  • 3)算法分析

  • 最佳情況:T(n) = O(nlogn)

  • 最差情況:T(n) = O(nlogn)

  • 平均情況:T(n) = O(nlogn)

七、歸并排序

1)算法簡介歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。歸并排序是一種穩定的排序方法。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為2-路歸并。2)算法描述和實現具體算法描述如下:

  • 把長度為n的輸入序列分成兩個長度為n/2的子序列;

  • 對這兩個子序列分別采用歸并排序;

  • 將兩個排序好的子序列合并成一個最終的排序序列。

  • functionmergeSort(array,p,r){ if(p < r){ varq = Math.floor((p + r) / 2); mergeSort(array,p,q); mergeSort(array,q + 1,r); merge(array,p,q,r); }}functionmerge(array,p,q,r){ varn1 = q - p + 1,n2 = r - q,left = [],right = [],m = n = 0; for(vari = 0;i < n1;i++){ left[i] = array[p + i]; } for(varj = 0;j < n2;j++){ right[j] = array[q + 1 + j]; } left[n1] = right[n2] = Number.MAX_VALUE; for(vark = p;k <= r;k++){ if(left[m] <= right[n]){ array[k] = left[m]; m++; }else{ array[k] = right[n]; n++; } }}


  • 3)算法分析

  • 最佳情況:T(n) = O(n)

  • 最差情況:T(n) = O(nlogn)

  • 平均情況:T(n) = O(nlogn)

八、桶排序

1)算法簡介桶排序 (Bucket sort)的工作的原理:假設輸入數據服從均勻分布,將數據分到有限數量的桶里,每個桶再分別排序(有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序)。2)算法描述和實現具體算法描述如下:

  • 設置一個定量的數組當作空桶;

  • 遍歷輸入數據,并且把數據一個一個放到對應的桶里去;

  • 對每個不是空的桶進行排序;

  • 從不是空的桶里把排好序的數據拼接起來。

  • /*方法說明:桶排序@param array 數組@param num 桶的數量*/functionbucketSort(array,num){ if(array.length <= 1){ returnarray; } varlen = array.length,buckets = [],result = [],min = max = array[0],regex = '/^[1-9]+[0-9]*$/',space,n = 0; num = num || ((num > 1 && regex.test(num))?num : 10); for(vari = 1;i < len;i++){ min = min <= array[i]?min : array[i]; max = max >= array[i]?max : array[i]; } space = (max - min + 1) / num; for(varj = 0;j < len;j++){ varindex = Math.floor((array[j] - min) / space); if(buckets[index]){ // 非空桶,插入排序 vark = buckets[index].length - 1; while(k >= 0 && buckets[index][k] > array[j]){ buckets[index][k + 1] = buckets[index][k]; k--; } buckets[index][k + 1] = array[j]; }else{ //空桶,初始化 buckets[index] = []; buckets[index].push(array[j]); } } while(n < num){ result = result.concat(buckets[n]); n++; } returnresult;}


  • 3)算法分析桶排序最好情況下使用線性時間O(n),桶排序的時間復雜度,取決與對各個桶之間數據進行排序的時間復雜度,因為其它部分的時間復雜度都為O(n)。很顯然,桶劃分的越小,各個桶之間的數據越少,排序所用的時間也會越少。但相應的空間消耗就會增大。

九、計數排序

1)算法簡介計數排序(Counting sort)是一種穩定的排序算法。計數排序使用一個額外的數組C,其中第i個元素是待排序數組A中值等于i的元素的個數。然后根據數組C來將A中的元素排到正確的位置。它只能對整數進行排序。2)算法描述和實現具體算法描述如下:

  • 找出待排序的數組中最大和最小的元素;

  • 統計數組中每個值為i的元素出現的次數,存入數組C的第i項;

  • 對所有的計數累加(從C中的第一個元素開始,每一項和前一項相加);

  • 反向填充目標數組:將每個元素i放在新數組的第C(i)項,每放一個元素就將C(i)減去1。

  • functioncountingSort(array){ varlen = array.length,B = [],C = [],min = max = array[0]; for(vari = 0;i < len;i++){ min = min <= array[i]?min : array[i]; max = max >= array[i]?max : array[i]; C[array[i]] = C[array[i]]?C[array[i]] + 1 : 1; } for(varj = min;j < max;j++){ C[j + 1] = (C[j + 1] || 0) + (C[j] || 0); } for(vark = len - 1;k >=0;k--){ B[C[array[k]] - 1] = array[k]; C[array[k]]--; } returnB;}


  • 3)算法分析當輸入的元素是n 個0到k之間的整數時,它的運行時間是 O(n + k)。計數排序不是比較排序,排序的速度快于任何比較排序算法。由于用來計數的數組C的長度取決于待排序數組中數據的范圍(等于待排序數組的最大值與最小值的差加上1),這使得計數排序對于數據范圍很大的數組,需要大量時間和內存

歡迎在留言區留下你的觀點,一起討論提高。如果今天的文章讓你有新的啟發,學習能力的提升上有新的認識,歡迎轉發分享給更多人。



Tags:排序算法   點擊:()  評論:()
聲明:本站部分內容來自互聯網,內容觀點僅代表作者本人,如有任何版權侵犯請與我們聯系,我們將立即刪除。
▌相關評論
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
▌相關推薦
筆試面試經常涉及各種算法,本文簡要介紹常用的一些算法,并用JavaScript實現。1、插入排序1)算法簡介插入排序(Insertion-Sort)的算法描述是一種簡單直觀的排序算法。它的工作原...【詳細內容】
2019-11-22   排序算法  點擊:(4)  評論:(0)  加入收藏
一、前言什么是算法?算法是某種集合,是簡單指令的集合,是被指定的簡單指令集合。確定該算法重要的指標: 第一是否能解決問題; 第二算法運行時間,即解決問題出結果需要多少時間; 還...【詳細內容】
2019-11-21   排序算法  點擊:(3)  評論:(0)  加入收藏
很久之前有過一次面試,被問到一個問題,能不能寫一個冒泡排序?說實話,盡管在這之前曾經寫過不少比這個更加復雜的處理邏輯,但很悲劇的是我當時真不知道什么是冒泡排序。。。只知道如果讓我排序某段混亂序列,能很快搞定就是了...【詳細內容】
2019-11-04   排序算法  點擊:(5)  評論:(0)  加入收藏
1、冒泡排序這個名詞的由來很好理解,一般河水中的冒泡,水底剛冒出來的時候是比較小的,隨著慢慢向水面浮起會逐漸增大,這物理規律我不作過多解釋,大家只需要了解即可。冒泡算法的...【詳細內容】
2019-10-31   排序算法  點擊:(6)  評論:(0)  加入收藏
待排序的元素需要實現 Java 的 Comparable 接口,該接口有 compareTo() 方法,可以用它來判斷兩個元素的大小關系。...【詳細內容】
2019-10-30   排序算法  點擊:(8)  評論:(0)  加入收藏
算法原理:將一個記錄插入到已排好序的序列中,從而得到一個新的有序序列(將序列的第一個數據看成是一個有序的子序列,然后從第二個記錄逐個向該有序的子序列進行有序的插入,直至...【詳細內容】
2019-10-30   排序算法  點擊:(9)  評論:(0)  加入收藏
常見的排序算法: 快速排序、堆排序、歸并排序、選擇排序 插入排序、二分插入排序 冒泡排序、雞尾酒排序 桶排序、計數排序、基數排序、位圖排序一、快速排序通過一趟排序將待...【詳細內容】
2019-10-29   排序算法  點擊:(9)  評論:(0)  加入收藏
冒泡排序時間之所以效率低,就是因為將所有數都一視同仁不做區分挨個比較,這是最普通的做事方法,所以效率也是最普通的,時間復雜度為N的平方;而歸并排序效率高,則是采用了分治的思...【詳細內容】
2019-10-22   排序算法  點擊:(8)  評論:(0)  加入收藏
插入排序時一種常見的排序算法,有點類似于我們打撲克摸牌的過程,每摸一張牌,我們便通過對比手上已有的牌,將剛拿到的牌放入合適的位置。實現實現思路假設前j-1個元素已經排好序,...【詳細內容】
2019-10-08   排序算法  點擊:(10)  評論:(0)  加入收藏
概述在計算器科學與數學中,一個排序算法(英語:Sorting algorithm)是一種能將一串數據依照特定排序方式進行排列的一種算法。本文將總結幾類常用的排序算法,包括冒泡排序、選擇排...【詳細內容】
2019-09-19   排序算法  點擊:(15)  評論:(0)  加入收藏
一、什么是排序算法1.1、排序定義對一序列對象根據某個關鍵字進行排序。1.2、排序術語穩定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不穩定:如果a原本在b的前面,而a=b,排序...【詳細內容】
2019-09-05   排序算法  點擊:(27)  評論:(0)  加入收藏
冒泡排序(Bubble Sort),又被稱為氣泡排序或泡沫排序。它是一種較簡單的排序算法。它會遍歷若干次要排序的數列,每次遍歷時,它都會從前往后依次的比較相鄰兩個數的大小;如果前者...【詳細內容】
2019-08-27   排序算法  點擊:(31)  評論:(0)  加入收藏
常見算法總結PHP 算法算法是我們遇到復雜問題時,處理程序的利器。說到算法,我們先來理解算法復雜度,其實算法復雜度是一個概念,一定程度上反映一個算法的好壞程度。算法復雜度...【詳細內容】
2019-08-14   排序算法  點擊:(30)  評論:(0)  加入收藏
什么是排序算法的穩定性?穩定: 如果 a = b, a原本在b的前面, 排序之后, a仍然在b的前面, 那么這個排序算法就是穩定的。反之, 就是不穩定的排序算法。穩定的排序算法有:一.快速排序...【詳細內容】
2019-08-02   排序算法  點擊:(60)  評論:(0)  加入收藏
常見的排序算法如下: 性能比較如下: 一般不會要求寫太復雜的排序算法,能寫幾個簡單的排序算法即可冒泡排序冒泡排序思路比較簡單: 將序列當中的左右元素,依次比較,保證右邊的元素...【詳細內容】
2019-07-29   排序算法  點擊:(33)  評論:(0)  加入收藏
排序算法是最基本最常用的算法,不同的排序算法在不同的場景或應用中會有不同的表現,我們需要對各種排序算法熟練才能將它們應用到實際當中,才能更好地發揮它們的優勢。今天,來總...【詳細內容】
2019-07-25   排序算法  點擊:(29)  評論:(0)  加入收藏
冒泡排序要點冒泡排序是一種交換排序。什么是交換排序呢?交換排序:兩兩比較待排序的關鍵字,并交換不滿足次序要求的那對數,直到整個表都滿足次序要求為止。算法思想它重復地走訪...【詳細內容】
2019-07-17   排序算法  點擊:(36)  評論:(0)  加入收藏
冒泡法排序核心思想:若有N個數從小到大排序,需進行N-1輪比較,第一輪每相鄰的兩個數據進行比較N-1次,最終挑選出最大的數,放到這一輪的最后位置;第二輪比較N-1-i次,挑選出這一輪最大...【詳細內容】
2019-06-19   排序算法  點擊:(96)  評論:(0)  加入收藏
概述排序分為內部排序和外部排序,內部排序是待排序的元素全部放在內存,并在內存中調整它們的順序。外部排序是部分元素放到內存中,在內外存間調整元素的順序。我們通常說的八大...【詳細內容】
2019-06-17   排序算法  點擊:(96)  評論:(0)  加入收藏
一. 插入排序插入排序的時間復雜度是O(n^2)。插入排序重復地將新元素插入到一個排好序的子線性表中,直到整個線性表排好序。算法描述如下:for(int i=0;i<list.length;i++){將li...【詳細內容】
2019-06-17   排序算法  點擊:(58)  評論:(0)  加入收藏
最新更新
欄目熱門
欄目頭條
31选7开奖11185