Javascript - Thuật toán Merge sort
Thuật toán Merge sort
Viết chương trình JavaScript để sắp xếp danh sách các phần tử bằng cách sử dụng Merge sort.
Theo Wikipedia - Trong khoa học máy tính, sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó
Ví dụ:
Mã nguồn:
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Sorts an array of numbers, using the mergesort algorithm.</title>
<script>
function merge_sort(left_part,right_part)
{
var i = 0;
var j = 0;
var results = [];
while (i < left_part.length || j < right_part.length) {
if (i === left_part.length) {
// j is the only index left_part
results.push(right_part[j]);
j++;
}
else if (j === right_part.length || left_part[i] <= right_part[j]) {
results.push(left_part[i]);
i++;
} else {
results.push(right_part[j]);
j++;
}
}
return results;
}
document.write(merge_sort([1,3,4], [3,7,9]));
</script>
</head>
<body>
</body>
</html>
Lưu đồ thuật toán:
