Sắp xếp chèn
Nó là một kiểu so sánh rất đơn giản để sắp xếp một mảng. Một sắp xếp so sánh so sánh giá trị hiện tại mà chúng tôi đang cố gắng sắp xếp với các giá trị khác trong mảng. Nó hoạt động với một mục tại một thời điểm và lặp đi lặp lại đặt từng mục vào đúng vị trí để có được một mảng được sắp xếp theo yêu cầu.
Trên thực tế, chèn sắp xếp không hiệu quả bằng một số thuật toán nâng cao như sắp xếp theo đống hoặc hợp nhất sắp xếp . Nó không phải là một lựa chọn tốt nhất khi xử lý các chương trình lớn. Vì giá trị hằng số ẩn thấp , sắp xếp chèn hoạt động tốt hơn một số thuật toán nâng cao như heap hoặc sắp xếp nhanh trong khi xử lý mảng nhỏ .
Sắp xếp chèn hoạt động bằng cách di chuyển từ trái sang phải trên một mảng. Nó sẽ sử dụng mục hiện tại dưới dạng 'chìa khóa' và tìm kiếm một giá trị ở bên trái của khóa đó để tìm vị trí nơi khóa thực sự sẽ nằm.
Thuật toán
Trong ví dụ sau, mảng đã cho là 0, -3,5,8,2,7,6
- Lặp lại 0 - trong lần lặp đầu tiên, chúng tôi chỉ có mảng thực tế chưa được sắp xếp là 0, -3,5,8,2,7,6.
- lần lặp 1 - trong lần lặp này, khóa là một giá trị ở chỉ số 1 là -3. Sắp xếp chèn so sánh khóa với các giá trị ở bên trái của khóa đó và tiếp tục quá trình. vì -3 nhỏ hơn 0 nên nó di chuyển sang trái của 0 ở đó bằng cách cho mảng là -3,0,5,8,2,7,6.
- Lặp lại 2 - Ở đây khóa là 5 (giá trị ở chỉ số 2). Nó sẽ được so sánh với các giá trị bên trái của nó là -3 và 0, và được đặt trong giá trị đã được sắp xếp của nó. Vì vậy, mảng sau lần lặp 2 là -3,0,5,8,2,7,6.
- Lặp lại 3 - Trong lần lặp này, giá trị khóa 8 sẽ được so sánh với các phần tử bên trái của nó và mảng cuối cùng sẽ là -3,0,5,8,2,7,6.
- Lặp lại 4 - Trong lần lặp này, giá trị khóa 2 được so sánh với các giá trị bên trái của nó và được đặt vào vị trí đã sắp xếp của nó. Vì vậy, mảng cuối cùng sau lần lặp 4 là -3,0,2,5,8,7,6.
Theo cách tương tự, vào cuối lần lặp cuối cùng, mảng được sắp xếp sẽ là -3,0,2,5,6,7,8
Ví dụ
<html>
<head>
<script>
function iSort(array) {
for (var p = 1; p < array.length; p++) {
if (array[p] < array[0]){
array.unshift(array.splice(p,1)[0]);
}
else if (array[p] > array[p-1]){
continue;
}
else {
for (var q = 1; q < p; q++) {
if (array[p] > array[q-1] && array[p] < array[q]){
array.splice(q,0,array.splice(p,1)[0]);
}
}
}
}
return array;
}
document.write(iSort([0,-3,5,8,2,7,6]));
</script>
</body>
</html> Đầu ra
-3,0,2,5,6,7,8