免費(fèi)AI編程助手
（5）插入排序 (Insertion Sort)
算法原理
設(shè)有一組關(guān)鍵字｛K1， K2，…， Kn｝；排序開始就認(rèn)為 K1?是一個(gè)有序序列；讓 K2?插入上述表長為 1 的有序序列，使之成為一個(gè)表長為 2 的有序序列；然后讓 K3?插入上述表長為 2 的有序序列，使之成為一個(gè)表長為 3 的有序序列；依次類推，最后讓 Kn?插入上述表長為 n-1 的有序序列，得一個(gè)表長為 n 的有序序列。
具體算法描述如下：
- 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復(fù)步驟 3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟 2~5
如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個(gè)變種，稱為二分查找排序。
二分查找法，是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜素過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。
圖片來自維基百科
實(shí)例分析
現(xiàn)有一組數(shù)組 arr = [5, 6, 3, 1, 8, 7, 2, 4]，共有八個(gè)記錄，排序過程如下：
[5] 6 3 1 8 7 2 4
↑ │
└───┘
[5, 6] 3 1 8 7 2 4
↑ │
└────────┘
[3, 5, 6] 1 8 7 2 4
↑ │
└──────────┘
[1, 3, 5, 6] 8 7 2 4
↑ │
└──┘
[1, 3, 5, 6, 8] 7 2 4
↑ │
└────┘
[1, 3, 5, 6, 7, 8] 2 4
↑ │
└────────────────┘
[1, 2, 3, 5, 6, 7, 8] 4
↑ │
└─────────────┘
[1, 2, 3, 4, 5, 6, 7, 8]其中有一點(diǎn)比較有意思的是，在每次比較操作發(fā)現(xiàn)新元素小于等于已排序的元素時(shí)，可以將已排序的元素移到下一位置，然后再將新元素插入該位置，接著再與前面的已排序的元素進(jìn)行比較，這樣做交換操作代價(jià)比較大。還有一個(gè)做法是，將新元素取出，從左到右依次與已排序的元素比較，如果已排序的元素大于新元素，那么將該元素移動(dòng)到下一個(gè)位置，接著再與前面的已排序的元素比較，直到找到已排序的元素小于等于新元素的位置，這時(shí)再將新元素插入進(jìn)去，就像下面這樣：
圖片來自維基百科
JavaScript 語言實(shí)現(xiàn)
直接插入排序 JavaScript 實(shí)現(xiàn)代碼：
function insertionSort(array) {
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
var length = array.length,
i,
j;
for (i = 1; i < length; i++) {
for (j = i; j > 0; j--) {
if (array[j - 1] > array[j]) {
swap(array, j - 1, j);
} else {
break;
}
}
}
return array;
}下面這種方式可以減少交換次數(shù)：
function insertionSort(array) {
var length = array.length,
i,
j,
temp;
for (i = 1; i < length; i++) {
temp = array[i];
for (j = i; j >= 0; j--) {
if (array[j - 1] > temp) {
array[j] = array[j - 1];
} else {
array[j] = temp;
break;
}
}
}
return array;
}利用二分查找法實(shí)現(xiàn)的插入排序，二分查找排序：
function insertionSort2(array) {
function binarySearch(array, start, end, temp) {
var middle;
while (start <= end) {
middle = Math.floor((start + end) / 2);
if (array[middle] < temp) {
if (temp <= array[middle + 1]) {
return middle + 1;
} else {
start = middle + 1;
}
} else {
if (end === 0) {
return 0;
} else {
end = middle;
}
}
}
}
function binarySort(array) {
var length = array.length,
i,
j,
k,
temp;
for (i = 1; i < length; i++) {
temp = array[i];
if (array[i - 1] <= temp) {
k = i;
} else {
k = binarySearch(array, 0, i - 1, temp);
for (j = i; j > k; j--) {
array[j] = array[j - 1];
}
}
array[k] = temp;
}
return array;
}
return binarySort(array);
}
更多建議：