[C++] Các thuật toán sắp xếp cơ bản thường sử dụng

💚15💚 · 08/03/2012 10:56

Thuật toán sắp xếp trộn Merge Sort (nên ưu tiên dùng thuật toán Quick Sort hơn)

Mã: Chọn tất cả: #include <iostream> using namespace std; // Gộp hai mảng con arr[l...m] và arr[m+1..r] void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* Tạo các mảng tạm */ int L[n1], R[n2]; /* Copy dữ liệu sang các mảng tạm */ for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1+ j]; /* Gộp hai mảng tạm vừa rồi vào mảng arr*/ i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai k = l; // IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } /* Copy các phần tử còn lại của mảng L vào arr nếu có */ while (i < n1) { arr[k] = L[i]; i++; k++; } /* Copy các phần tử còn lại của mảng R vào arr nếu có */ while (j < n2) { arr[k] = R[j]; j++; k++; } } /* l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp */ void mergeSort(int arr[], int l, int r) { if (l < r) { // Tương tự (l+r)/2, nhưng cách này tránh tràn số khi l và r lớn int m = l+(r-l)/2; // Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng mergeSort(arr, l, m); mergeSort(arr, m+1, r); merge(arr, l, m, r); } } int main() { int arr[] {32,71,12,45,26,80,53,33,-7,99,1,5,2,-3,-100}; int n = sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang mergeSort(arr, 0, n-1); cout << "So luong phan tu trong mang: " << n << endl; for (int i : arr) { cout << i << " "; } return 0; }

[C++] Các thuật toán sắp xếp cơ bản thường sử dụng

Re: [C++] Các thuật toán sắp xếp cơ bản thường sử dụng