Home-theater-designers
Sắp xếp hợp nhất là một thuật toán sắp xếp dựa trên kỹ thuật 'chia để trị'. Đó là một trong những thuật toán sắp xếp hiệu quả nhất.
trang web hẹn hò trực tuyến miễn phí cho thanh thiếu niên
Trong bài viết này, bạn sẽ tìm hiểu về hoạt động của thuật toán sắp xếp hợp nhất, thuật toán sắp xếp hợp nhất, độ phức tạp về thời gian và không gian của nó cũng như cách triển khai của nó trong các ngôn ngữ lập trình khác nhau như C ++, Python và JavaScript.
Thuật toán Sắp xếp Hợp nhất hoạt động như thế nào?
Merge sort hoạt động trên nguyên tắc chia để trị. Sắp xếp hợp nhất liên tục chia một mảng thành hai mảng con bằng nhau cho đến khi mỗi mảng con bao gồm một phần tử duy nhất. Cuối cùng, tất cả các mảng con đó được hợp nhất để sắp xếp mảng kết quả.
Khái niệm này có thể được giải thích hiệu quả hơn với sự trợ giúp của một ví dụ. Hãy xem xét một mảng không được sắp xếp với các phần tử sau: {16, 12, 15, 13, 19, 17, 11, 18}.
Ở đây, thuật toán sắp xếp hợp nhất chia mảng thành hai nửa, tự gọi mảng cho hai nửa và sau đó hợp nhất hai nửa đã sắp xếp.
Thuật toán sắp xếp hợp nhất
Dưới đây là thuật toán của sắp xếp hợp nhất:
MergeSort(arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
return
else
Find the middle index that divides the array into two halves:
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Call mergeSort() for the first half:
Call mergeSort(arr, leftIndex, middleIndex)
Call mergeSort() for the second half:
Call mergeSort(arr, middleIndex+1, rightIndex)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, leftIndex, middleIndex, rightIndex)Liên quan: Đệ quy là gì và bạn sử dụng nó như thế nào?
Độ phức tạp về thời gian và không gian của thuật toán sắp xếp hợp nhất
Thuật toán sắp xếp hợp nhất có thể được biểu diễn dưới dạng quan hệ lặp lại sau:
T (n) = 2T (n / 2) + O (n)
Sau khi giải quan hệ lặp lại này bằng cách sử dụng định lý bậc thầy hoặc phương pháp cây tái hiện, bạn sẽ nhận được nghiệm là O (n logn). Do đó, độ phức tạp về thời gian của thuật toán sắp xếp hợp nhất là O (n logn) .
Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp hợp nhất: O (n logn)
Độ phức tạp thời gian theo trường hợp trung bình của sắp xếp hợp nhất: O (n logn)
Độ phức tạp thời gian trong trường hợp xấu nhất của sắp xếp hợp nhất: O (n logn)
Có liên quan: Ký hiệu Big-O là gì?
Sự phức tạp của không gian phụ trợ của thuật toán sắp xếp hợp nhất là Trên) như n không gian phụ trợ được yêu cầu trong việc triển khai sắp xếp hợp nhất.
C ++ Triển khai thuật toán sắp xếp hợp nhất
Dưới đây là cách triển khai C ++ của thuật toán sắp xếp hợp nhất:
// C++ implementation of the
// merge sort algorithm
#include
using namespace std;
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
void merge(int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
int L[leftSubarraySize], R[rightSubarraySize];
// Copying data to temporary arrays L[] and R[]
for (int i = 0; i L[i] = arr[leftIndex + i];
for (int j = 0; j R[j] = arr[middleIndex + 1 + j];
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
int i = 0;
// Initial index of Right subarray
int j = 0;
// Initial index of merged subarray
int k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int leftIndex, int rightIndex)
{
if(leftIndex >= rightIndex)
{
return;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
void printArray(int arr[], int size)
{
for (int i = 0; i {
cout << arr[i] << ' ';
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << 'Unsorted array:' << endl;
printArray(arr, size);
mergeSort(arr, 0, size - 1);
cout << 'Sorted array:' << endl;
printArray(arr, size);
return 0;
} Đầu ra:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19JavaScript Triển khai Thuật toán Sắp xếp Hợp nhất
Dưới đây là triển khai JavaScript của thuật toán sắp xếp hợp nhất:
// JavaScript implementation of the
// merge sort algorithm
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
function merge(arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
var L = new Array(leftSubarraySize);
var R = new Array(rightSubarraySize);
// Copying data to temporary arrays L[] and R[]
for(let i = 0; i L[i] = arr[leftIndex + i];
}
for (let j = 0; j R[j] = arr[middleIndex + 1 + j];
}
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
var i = 0;
// Initial index of Right subarray
var j = 0;
// Initial index of merged subarray
var k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort(arr, leftIndex, rightIndex) {
if(leftIndex >= rightIndex) {
return
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
function printArray(arr, size) {
for(let i = 0; i document.write(arr[i] + ' ');
}
document.write('
');
}
// Driver code:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = arr.length;
document.write('Unsorted array:
');
printArray(arr, size);
mergeSort(arr, 0, size - 1);
document.write('Sorted array:
');
printArray(arr, size); Đầu ra:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19Liên quan: Lập trình động: Ví dụ, Sự cố thường gặp và Giải pháp
Triển khai thuật toán sắp xếp hợp nhất trong Python
Dưới đây là triển khai Python của thuật toán sắp xếp hợp nhất:
# Python implementation of the
# merge sort algorithm
def mergeSort(arr):
if len(arr) > 1:
# Finding the middle index of the array
middleIndex = len(arr)//2
# Left half of the array
L = arr[:middleIndex]
# Right half of the array
R = arr[middleIndex:]
# Sorting the first half of the array
mergeSort(L)
# Sorting the second half of the array
mergeSort(R)
# Initial index of Left subarray
i = 0
# Initial index of Right subarray
j = 0
# Initial index of merged subarray
k = 0
# Copy data to temp arrays L[] and R[]
while i if L[i] arr[k] = L[i]
i = i + 1
else:
arr[k] = R[j]
j = j + 1
k = k + 1
# Checking if there're some remaining elements
while i arr[k] = L[i]
i = i + 1
k = k + 1
while j arr[k] = R[j]
j = j + 1
k = k + 1
# Function to print the elements
# of the array
def printArray(arr, size):
for i in range(size):
print(arr[i], end=' ')
print()
# Driver code
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
size = len(arr)
print('Unsorted array:')
printArray(arr, size)
mergeSort(arr)
print('Sorted array:')
printArray(arr, size)
Đầu ra:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19Hiểu các thuật toán sắp xếp khác
Sắp xếp là một trong những thuật toán được sử dụng nhiều nhất trong lập trình. Bạn có thể sắp xếp các phần tử trong các ngôn ngữ lập trình khác nhau bằng cách sử dụng các thuật toán sắp xếp khác nhau như sắp xếp nhanh, sắp xếp bong bóng, sắp xếp hợp nhất, sắp xếp chèn, v.v.
Sắp xếp bong bóng là lựa chọn tốt nhất nếu bạn muốn tìm hiểu về thuật toán sắp xếp đơn giản nhất.
Đăng lại Đăng lại tiếng riu ríu E-mail Giới thiệu về thuật toán sắp xếp bong bóngThuật toán Sắp xếp bong bóng: một giới thiệu tuyệt vời về sắp xếp các mảng.
Đọc tiếp Chủ đề liên quan- Lập trình
- JavaScript
- Python
- Hướng dẫn viết mã
Yuvraj là sinh viên ngành Khoa học Máy tính tại Đại học Delhi, Ấn Độ. Anh ấy đam mê Phát triển Web Full Stack. Khi không viết, anh ấy đang khám phá chiều sâu của các công nghệ khác nhau.
Xem thêm từ Yuvraj ChandraTheo dõi bản tin của chúng tôi
Tham gia bản tin của chúng tôi để biết các mẹo công nghệ, đánh giá, sách điện tử miễn phí và các ưu đãi độc quyền!
Bấm vào đây để đăng ký