插入排序

发表于

js(看了原理五分钟内自己写,不一定正确)

1
2
3
4
5
6
7
8
9
var alertSort=function (array){
	const len=array.length;
    let i=1;
    for(i;i<len;i++){
        while(array[i]<array[i-1]&&i>=0){
            swap(i,i-1)
        }
    }
}

3 4 2 5 1

3 4

2 3 4

2 3 4 5

1 2 3 4 5

书上的

1
2
3
4
5
6
7
8
9
10
11
12
this.insertionSort=fuction(){
    var length=array.length,j,temp;
    for(var i=1;i<length;i++){
        j=i;
        temp=array[i];
        while(j>0&&array[j-1]>temp){
            array[j]=array[j-1];
            j--;
        }
        array[j]=temp;
    }
}

思否

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function insertSort(arr) {
  let length = arr.length;
  for(let i = 1; i < length; i++) {
    let temp = arr[i];
    let j = i;
    for(; j > 0; j--) {
      if(temp >= arr[j-1]) {
        break;      // 当前考察的数大于前一个数，证明有序，退出循环
      }
      arr[j] = arr[j-1]; // 将前一个数复制到后一个数上
    }
    arr[j] = temp;  // 找到考察的数应处于的位置
  }
  return arr;
}

// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10]
console.log(insertSort(arr));