前端排序之插入排序與希爾排序

03-06

插入排序：

<1>.從第一個元素開始，該元素可以認為已經被排序；
<2>.取出下一個元素，在已經排序的元素序列中從後向前掃描；
<3>.如果該元素（已排序）大於新元素，將該元素移到下一位置；
<4>.重複步驟3，直到找到已排序的元素小於或者等於新元素的位置；
<5>.將新元素插入到該位置後；
<6>.重複步驟2~5。

function insertSort(arr) { var temp; for(var i = 1; i < arr.length; i++) { temp = arr[i] for(var j = i - 1; j >= 0; j--) { if(arr[j] > temp) { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = temp } return arr}

希爾排序：

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，具體演算法描述：

<1>. 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
<2>.按增量序列個數k，對序列進行k 趟排序；
<3>.每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

function shellSort(arr){ var len = arr.length; var temp; var gap = Math.floor(len/2); while(gap !== 0) { // 循環次數為子序列的數量 for (var i = gap; i < len; i++) { temp = arr[i] // 對子序列進行插入排序，從子序列的最後一位開始往前遍歷 for (var j = i - gap; j >= 0; j -= gap){ if (arr[j] > temp) { arr[j+gap] = arr[j] } else { break } } arr[j+gap] = temp; } gap = Math.floor(gap/2) } return arr}

註：分割子序列方式：(從後往前分割的方式)

var arr = [26, 2, 38, 5, 47, 15, 36, 44, 3, 27, 46, 4, 19, 50, 48];

增量為5；[26，15]

[2，36]

[38，44]

[5，3]

[47，27]

[26,15,46]

[2,36,4]

[38,44,19]

[5,3,50]

[47,27,48]