DIV CSS 佈局教程網

JavaScript 排序演算法實作:冒泡排序與快速排序
編輯:關於JavaScript     

一、氣泡排序(Bubble Sort)

思路最直觀的一種:相鄰兩兩比較,大的往後換,一輪下來最大值就浮到尾端。

 var arr1=[3,9,2,7,0,8,4]; for(var i=0;i<arr1.length;i++){ for(var j=i+1;j<arr1.length;j++){ var temp=0; if(arr1[i]>arr1[j]){ temp=arr1[i]; arr1[i]=arr1[j]; arr1[j]=temp; } } } alert(arr1);

時間複雜度 O(n²),資料量小時夠用,但實務上不太會拿它排序大量資料。

二、快速排序(Quick Sort)

分治法:選一個基準值 pivot,把比它小的放左邊、大的放右邊,然後對左右兩段遞迴處理。

 var a=[3,5,0,9,2,7,5]; function quickSort(arr){ var len=a.length; if(len<=1) return arr; function sort(low,height){ var pivot=a[low]; var i=low,j=height,t; if(i>j) return false; while(i!=j){ while(a[j]>=pivot&&i<j){ j--; } while(a[i]<=pivot&&i<j){ i++; } if(i<j){//把比pivot大的換到右邊,小的換到左邊 t=a[i]; a[i]=a[j]; a[j]=t; } } //此時i和j指向同一個數字,把這個數字和pivot交換 a[low]=a[i]; a[i]=pivot; //遞歸:把pivot左邊的數進行一次排序,右邊的數進行一次排序 sort(low,i-1); sort(i+1,height); } //調用這個排序的函數 sort(0,len-1); return a; } alert(quickSort(a));

平均時間複雜度 O(n log n),是實務上最常被使用的排序之一。

順帶一提,上面這段程式碼有個小 bug:函式內部讀的是全域變數 a 而不是參數 arr,換成傳入的陣列就會失效。把 a 全部改為 arr 即可。另外 JS 引擎本身提供的 arr.sort((x,y) => x-y) 在絕大多數場景下已經足夠,手写排序適合用來理解演算法原理。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved