用js冒泡排序,快速排序,選擇排序

1.冒泡排序

冒泡排序是比較經(jīng)典的排序方法，是一種用時間換空間的排序方法。我總結(jié)了一下它的特點：（1）它的時間復雜度是；（2）每一趟相鄰元素兩兩比較完畢就會產(chǎn)生最值（最大值）；（3）每次比較完后下一趟就會少一個元素參與比較（即該趟比較的最大值）。
// 冒泡排序

function maopao(arr){for(var i=0;i<arr.length-1;i++){for(var j=i+1;j<arr.length;j++){// 如果前面的大,交換位置var temp=[];if(arr[i]>arr[j]){temp = arr[i];arr[i]=arr[j];arr[j]=temp;}}}return arr;}var arr = [1,9,3,7,2,8,3,99,44,1,6];maopao(arr);console.log("冒泡排序");console.log(arr);

快速排序

// 2.快速排序
一趟快速排序的算法是： 　　

1）設置兩個變量i、j，排序開始的時候：i=0，j=N-1； 　　

2）以第一個數(shù)組元素作為關鍵數(shù)據(jù)，賦值給key，即 key=A[0]； 　　

3）從j開始向前搜索，即由后開始向前搜索（j=j-1即j--）， 找到第一個小于key的值A[j]，A[i]與A[j]交換； 　　

4）從i開始向后搜索，即由前開始向后搜索（i=i+1即i++）， 找到第一個大于key的A[i]，A[i]與A[j]交換； 　　

5）重復第3、4、5步，直到I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。 找到并交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j-完成的最后令循環(huán)結(jié)束）

function quickSort(arr){// 如果數(shù)組長度小于等于1,直接返回if(arr.length<=1){return arr;}// 選擇一個基準var pivotIndex = Math.floor(arr.length/2);// 將基準與原數(shù)組分離var pivot = arr.splice(pivotIndex,1)[0];// 定義左右兩個空數(shù)組用來存放var left = [];var right=[];// 循環(huán),如果小于基準就放左邊,大于基準就放右邊f(xié)or(var i=0;i<arr.length;i++){if(arr[i]<=pivot){left.push(arr[i]);}else{right.push(arr[i]);}}// 使用遞歸return quickSort(left).concat(pivot, quickSort(right));}var arr2 = [999,9,3,7,24,8,3,99,44,1,6];console.log("快速排序")console.log(quickSort(arr2));

3.選擇排序

選擇排序相比冒泡排序不穩(wěn)定，時間復雜度也是。選擇排序沒趟都會產(chǎn)生最小值，它不是相鄰元素的比較而是在該元素設置一個索引i。然后與數(shù)組的其他元素依次比較（除了上一個索引值），直到找到小于該元素（索引j）時交換兩元素，接著繼續(xù)從i索引（此時已經(jīng)不是原來的數(shù)值）值與索引j+1值比較。
// 選擇排序

function selectSort(arr){var minIndex;var temp;// 循環(huán)for(var i=0;i<arr.length-1;i++){minIndex=i;// 找到從i開始到最后的最小的數(shù)for(var j=i+1;j<arr.length;j++){if( arr[j] < arr[minIndex] ) {minIndex = j;}}temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;} return arr;}var arr3 = [99,9,3,7,24,8,3,99,44,1,6];console.log(selectSort(arr3));

總結(jié)

以上是生活随笔為你收集整理的js实现冒泡排序,快速排序,选择排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。