插入排序

插入排序

思路：分为有序（原数组的第一项）和无序（原数组的剩余项）俩个数组，枚举无序数组，将每一项添加到有序数组中，并且在添加的时候逐一枚举有序数组，并插入合适的位置。

#include <iostream>
using namespace std;

int main()
{
  int cards[13] = {311, 112, 402, 405, 206, 207, 101, 113, 208, 303, 304, 309, 410};
  // 枚举无序数组的每一项
  for (int i = 1; i < 13; i++)
  {
    // 获取当前项
    int target = cards[i], min = 500, pos = -1;
    // 比较当前项和有序数组每一项，确定插入位置
    // 如果当前项比有序数组每一项都大，直接跳出此次循环
    // 如果当前项大小在有序数组之中，找到插入位置
    for (int j = 0; j < i; j++)
      if(cards[j] > target && cards[j] < min)
      {
        min = cards[j];
        pos = j;
      }
    // 插到合适的位置
    if (pos != -1)
    {
      // 有序数组中，将比 当前项 大的项逐一往后移
      for (int j = i; j > pos; j--)
        cards[j] = cards[j - 1];
      // 把目标值插入到找到的pos位置
      cards[pos] = target;
    }
  }
  for (int i = 0; i < 13; i++)
    cout << cards[i] << endl;
  return 0;
}

用js实现：

function insertSort(arr) {
  //判断参数的合法性
  if (toString.call(arr) !== '[object Array]') {
    return false;
  }
  //获取数组的长度
  var len = arr.length;
  if (len <= 1) {
    return arr; //小于等于1不用排序
  }
  //i=1开始，留着0作为有序部分，也就是说，外层循环获取数组后面的元素，也就是上面所讲的无序部分
  for (var i = 1; i < len; i++) {
    //j=i-1，就是获取有序部分最后的一个元素作为对照，也就是有序部分
    for (var j = i - 1; j >= 0; j--) {
      //注意，j--,就是从有序部分的后面元素开始和无序部分的元素作比较
      if (arr[j] > arr[j + 1]) {
        //第一个j+1也就是外层循环i，
        //互换元素，对前面数组进行排序
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}
//测试
var ar = [9, 3, 8, 5, 2, 7, 0, 6, 1, 4];
console.log(insertSort(ar));

js结合c++思路优化：

function insertSort(arr) {
  if (toString.call(arr) !== '[object Array]') return false;
  if (arr.length <= 1) return arr;
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    let target = arr[i],
      min = 1000000,
      pos = -1;
    for (let j = 0; j < i; j++) {
      if (target < arr[j] && arr[j] < min) {
        min = arr[j];
        pos = j;
      }
    }
    if (pos != -1) {
      for (let k = i; k > pos; k--) {
        arr[k] = arr[k - 1];
      }
      arr[pos] = target;
    }
  }
  return arr;
}
var ar = [9, 3, 8, 5, 2, 7, 0, 6, 1, 4];
console.log(insertSort(ar));