Thuật Toán Merge Sort
Chào mừng các bạn đến với chủ đề thuật toán lập trình.
Hôm nay chúng ta cùng tìm hiểu về thuật toán Merge Sort (Thuật toán sắp xếp trộn)
1. Nguyên lý cơ bản của Merge Sort.
– Là một thuật toán sắp xếp dựa theo nguyên lý chia để trị.
– Giả sử đầu vào là một mảng arr với hai vị trí đầu cuối là: left và right.
+ Tìm ra điểm trung tâm để chia mảng thành hai phần, gọi vị trí là mid.
+ Gọi hàm xử lý MergeSort cho nửa đầu tiền chạy từ left đến mid.
+ Gọi hàm xử lý MergeSort cho nửa thứ hai chạy từ mid+1 đến right.
+ Hợp nhất hai mảng đã được sắp xếp lại từ hai bước ở trên.
– Độ phức tạp: O = n*log2(n);
2 Thực hành Thuật Toán Merge Sort
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
// Phattrienphanmem123az.com #include<iostream> #include <conio.h> void ImplMerge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int* L = new int[n1]; int* R = new int [n2]; for (int ii = 0; ii < n1; ii++) L[ii] = arr[left + ii]; for (int jj = 0; jj < n2; jj++) R[jj] = arr[mid + 1+ jj]; int i = 0; int j = 0; int k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(int arr[], int left, int right) { if (left < right) { int mid = left +(right -left)/2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); ImplMerge(arr, left, mid, right); } } void Show(int A[], int size) { for (int i=0; i < size; ++i) std::cout << A[i] << " "; } int main() { int arr[] = {312, 311, 313, 35, 36, 37}; int arr_size = sizeof(arr)/sizeof(arr[0]); mergeSort(arr, 0, arr_size - 1); std::cout < "\nSorted array is \n"; Show(arr, arr_size); _getch(); return 0; } |
TPham