JavaScript实现 插入排序 算法(INSERTION-SORT)

插入排序介绍

算法导论：对于少量的元素，它是一种有效的算法。插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面朝下。然后我们每次从座子上拿走一张扑克牌并将它插入左手中正确的位置，我们从右到左将它与已在手中的牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

伪代码实现

INSERTION-SORT(A)
// Note that i is the index of Array A which is from zero not one 
// if from one ,next line will be `for i = 2 to A.length`
    for i = 1 to A.length - 1
         key = A[i]
         j = j - 1
   //Insert A[i] into the sorted sequence A[1..i-1]
    while j > 0 and A[j] > key
	      A[j+1] = A[j]
	      A[j] = key
	      j = j - 1

JavaScript实现

// 内部使用 while 实现
function insertionSort(arr) { 
  // 当数组中最多只有一个元素时，无需进行排序
  if (arr.length > 1) { 
    // 第一个元素是起始位置不用进行排序，直接从第二个元素开始比较
    for (let i = 1; i < arr.length; i++) { 
      // key , i 分别是当前需要排序的元素的值 和 索引
      const key = arr[i];
      //从已排数组的最右边开始比较
      let j = i - 1;
      //当已排序元素的值大于可以时交换位置
      while (j >= 0 && arr[j] > key) { 
        arr[j + 1] = arr[j];
        arr[j] = key;
        j = j - 1;
      }
    }
  }
  return arr;
}

//内部使用for循环实现
function insertionSort(arr) { 
  // 当数组中最多只有一个元素时，无需进行排序
  if (arr.length > 1) { 
    // 第一个元素是起始位置不用进行排序，直接从第二个元素开始比较
    for (let i = 1; i < arr.length; i++) { 
      // key,i分别是当前需要排序的元素的值 和 索引
      const key = arr[i];
      //从已排数组的最右边开始比较

      //当已排序元素的值大于可以时交换位置
      for (let j = i - 1; j >= 0; j--) { 
        // 如果key值比要比较的值大，则表示排序完成，此时直接跳出循环
        if (key > arr[j]) { 
          break;
        }
        arr[j + 1] = arr[j];
        arr[j] = key;
      }
    }
  }
  return arr;
}