JavaScript常見的三種排序算法，手把手解釋代碼

泡排序

冒泡排序的實質就是將數組的相鄰項進行比對，如果前一個比后一個大，就交換位置。

冒泡排序需要兩層的循環，第一層循環負責比對的輪次，第二層負責相鄰位置對比的次數。

比如一個最壞情況的數組為 arr = [4,3,2,1]，按照從小到大排序：

第一輪交換的過程依次為：[3,4,2,1]、[3,2,4,1]、[3,2,1,4]
第二輪交換的過程依次為：[2,3,1,4]、[2,1,3,4]
第三輪交換的過程依次為：[1,2,3,4]

可以發現一個規律，比較次數+當次輪數 = 數組的長度

代碼如下：

function bubbleSort (arr){
	let length = arr.length
  for(let i = 0 ; i<length ; i++){
  	for(let j = 0 ; j<arr.length - i -1 ; j++ ){
         if(arr[j] > arr[j+1]){
             temp = arr[j]
             arr[j] = arr[j+1]
             arr[j+1] = temp 
         }
     }
  }  
  return arr
}

冒泡排序的比較次數可以依次推倒為：

比如4個數字的排序，第一輪比較3次，第二輪比較2次，第三輪比較1次
比較總次數為：3+2+1
n個數字，比較次數為 (n-1)+(n-2)+ …… + 1 = n*(n-1)/2
去除常項只保留最高階項
比較次數為：O( n2 )

冒泡排序的交換次數：

假定兩次比較會交換一次，取一個平均值，為n*(n-1)/2 /2
去除常項只保留最高階項
交換次數為：O( n2 )

選擇排序

選擇排序的實質：

第一步，設置一個min最小索引值，一般從0開始

第二步，arr[min]和未排序項進行比對，把比arr[min]小的項的索引值，改為新的最小索引值

第三步，將新的最小索引值的位置和未排序的起始位置進行交換，重復以上過程

function selectionSort(arr){
		let temp , min = 0
    for( let j = 0 ; j< arr.length ; i++){
    		for( let i = min + 1 ; i < arr.length ; i++ ){
    		if( arr[min] > arr[i] ){
        		min = i
        }
 	   }
  	temp = arr[min]
  	arr[min] = arr[0]
  	arr[0] = temp
    }
}

選擇排序的比較次數O(n2)

選擇排序的交換次數O(n)

插入排序

插入排序就像在打撲克牌，歡樂斗地主，按照從小到到從左到右的順序將牌進行排列。

在一個無序的序列中，先把第一個元素當做已排序序列，剩余當做未排序序列。

然后遍歷未排序的序列，依次和第一個元素進行比對。如果元素較小，就將其移至前方。這里可以使用while循環。

function insertSort(arr){
   for(let i = 1;i<arr.length;i++){
        // temp是未排序中的元素
        let temp = arr[i]
        let j = i
        while(temp < arr[j-1] && j>0){
             arr[j] = arr[j-1]
              j--
        }
        arr[j]=temp
   }
   return arr
}

插入排序最多的比較次數為：(1+2+...+N-1)/2 = N*(N-1)/4

插入排序的復制次數：N*(N-1)/4

時間復雜度為O(n2)

格(行)排序:

<html>
<head>
<meta charset="utf-8">
<title>無標題文檔</title>
<script>
window.onload=function (){
    var oTab=document.getElementById('tab1');
    var oBtn=document.getElementById('btn1');

    oBtn.onclick=function (){
    var arr=[];

    for(var i=0;i<oTab.tBodies[0].rows.length;i++){
    arr[i]=oTab.tBodies[0].rows[i]; //將表格行元素集合轉換為數組
    }

    arr.sort(function (tr1, tr2){ //自定義排序函數
    var n1=parseInt(tr1.cells[0].innerHTML);
    var n2=parseInt(tr2.cells[0].innerHTML);

    return n1-n2;
    });

    for(var i=0;i<arr.length;i++){
    oTab.tBodies[0].appendChild(arr[i]);
    }
    };
};
</script>
</head>
<body>
<input id="btn1" type="button" value="排序" />
<table id="tab1" border="1" width="500">
<thead>
<td>ID</td>
<td>姓名</td>
<td>年齡</td>
<td>操作</td>
</thead>
<tbody>
<tr>
<td>2</td>
<td>張三</td>
<td>23</td>
<td></td>
</tr>
<tr>
<td>6</td>
<td>王四</td>
<td>24</td>
<td></td>
</tr>
<tr>
<td>1</td>
<td>Blue</td>
<td>27</td>
<td></td>
</tr>
<tr>
<td>5</td>
<td>張偉</td>
<td>24</td>
<td></td>
</tr>
<tr>
<td>3</td>
<td>李四</td>
<td>28</td>
<td></td>
</tr>
<tr>
<td>4</td>
<td>王五</td>
<td>25</td>
<td></td>
</tr>
</tbody>
</table>
</body>
</html>

appendChild()方法理解:

target.appendChild(newnode)

1.先把元素從原有父級上刪掉

2.添加到新的父級

.冒泡排序：

比較相鄰的兩個數，如果前一個數大于后一個數，就將這兩個數換位置。每一次遍歷都會將本次遍歷最大的數冒泡到最后。為了將n個數排好序，需要n-1次遍歷。如果某次遍歷中，沒有調整任何兩個相鄰的數的位置關系，說明此時數組已排好序，可以結束程序。

Array.prototype.bubbleSort = function () {
let i, j;
for (i = 1; i < this.length; i++) { //表示本次是第i次遍歷
let changed = false;
for (j = 0; j < this.length - i; j++) { //訪問序列為arr[0:length-i]
if(this[j] > this[j + 1]){ //發現前一個數大于后一個時，互換位置
[this[j],this[j+1]] = [this[j+1],this[j]];
changed = true;
}
}
if(!changed) { //如果本輪遍歷沒有發現位置調整，結束排序函數
break;
}
}
};
let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.bubbleSort();
console.log(arr);

在線咨詢

上一篇：利用HTML5的canvas實現幾個有趣的小球運動效果，來學一下吧
下一篇：JSP 表單處理

您的項目需求

*請認真填寫需求信息，我們會在24小時內與您取得聯系。

整合營銷服務商

JavaScript常見的三種排序算法，手把手解釋代碼

泡排序

選擇排序

插入排序

您的項目需求