Javascript - Thuật toán Shell sort
Thuật toán Shell sort
Shell Sort là một giải thuật sắp xếp mang lại hiệu quả cao dựa trên giải thuật sắp xếp chèn (Insertion Sort). Giải thuật này tránh các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử lớn hơn bên trái).
Mã nguồn:
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Sorts an array of numbers, using the Head _Sort algorithm.</title>
<script>
function shellSort(arr) {
var increment = arr.length / 2;
while (increment > 0) {
for (i = increment; i < arr.length; i++) {
var j = i;
var temp = arr[i];
while (j >= increment && arr[j-increment] > temp) {
arr[j] = arr[j-increment];
j = j - increment;
}
arr[j] = temp;
}
if (increment == 2) {
increment = 1;
} else {
increment = parseInt(increment*5 / 11);
}
}
return arr;
}
document.write(shellSort([3, 0, 2, 5, -1, 4, 1]));
</script>
</head>
<body>
</body>
</html>
Lưu đồ thuật toán:
