JavaScript實現 插入排序 演演算法(INSERTION-SORT)

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;
}