JavaScript插入排序算法原理與實現方法示例

2019-11-19 13:20:16

字體：大中小

來源：轉載

供稿：網友

本文實例講述了JavaScript插入排序算法原理與實現方法。分享給大家供大家參考，具體如下：

一、插入排序簡介：

想象我們斗地主，摸排階段，手里的牌都按照從小到大排序。如果每摸一張牌，我們就把他插入合適的位置，使得它比后面位置的牌小，比前面位置的牌大或者相等。

類似這樣的一種排序方法就是插入排序：

在一個數組a中，我們要實現升序排序，假設我們前面已經對a[0]到a[k]排好序，現在需要將a[k+1]的值放入合適的位置。

（為簡便，此處不討論k的取值范圍，只是用它代表數組的某個位置）

1、首先，我們將a[k+1]的值與a[k]比較，如果小于a[k]就交換兩者的值，相等或者大于都不需要交換。假設交換了，那么現在a[k]存放的是原先a[k+1]的值，新的a[k]的值有可能比前面位置的值小，故又需要再次對a[k]與a[k-1]進行比較，以此類推。直到發現某個位置a[p](p是0到k之間數）的值已經不比a[p-1]的值小，比較結束，a[k+1]的值已經放入合適的位置a[p]?；蛘?span style="color: #0000ff">a[k+1]的值比前面的值都小，一步步交換之后a[0]存放了原先a[k+1]的值，那么也結束。現在a[0]到a[k+1]是一個有序數組。

2、對a[k+1]之后a[k+2]到a[a.length-1]的每一個元素都依次進行相同操作，最終得到一個有序數組。

二、JavaScript實現插入排序

function insertion_sort(arr) {  var temp;  for (var i = 1; i < arr.length; i++) {    for (var j = i-1; j >=0; j--) {      if (arr[j+1]<arr[j]) {        temp=arr[j+1];        arr[j+1]=arr[j];        arr[j]=temp;      }else if (arr[j+1]>=arr[j]) {        break;      }    }  }  return arr;}var a=[11,2,3,445,7,32,71,8,94];console.log(insertion_sort(a));var b=[94,11];console.log(insertion_sort(b));

說明：

1、一旦發現arr[j+1]的值不比前面的值小，就可以結束內層循環了，break實現這一功能；

2、內層循環用arr[j+1]的原因：初始時a[j]（即a[i-1]）代表a[i]前一個位置，進入循環后，a[j+1]就表示了a[i]的位置，實現了a[i]和a[i-1]的第一次比較；隨著j第一次自減，實際上比較了a[i-1]和a[i-2]；依次類推。如果將arr[j+1]改成a[i]是不行的，因為沒有實現位置的移動。