CHIASE123.COM - Diễn đàn chia sẻ kiến thức

nghiammo1992 · gửi bởi **nghiammo1992** » 12/09/2021 12:30

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

Thuật toán sắp xếp theo cơ số Radix Sort (Không hoạt động với mảng chứa số âm)

Mã: Chọn tất cả: #include <iostream> using namespace std; int get_max_element(int arr[], int n) { int max = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > max) max = arr[i]; return max; } void sort_counting(int arr[], int size, int place) { int output[size + 1]; int max = (arr[0] / place) % 10; for (int i = 1; i < size; i++) { if (((arr[i] / place) % 10) > max) max = arr[i]; } int count[max + 1]; for (int i = 0; i < max; ++i) count[i] = 0; for (int i = 0; i < size; i++) count[(arr[i] / place) % 10]++; for (int i = 1; i < 10; i++) count[i] += count[i - 1]; for (int i = size - 1; i >= 0; i--) { output[count[(arr[i] / place) % 10] - 1] = arr[i]; count[(arr[i] / place) % 10]--; } for (int i = 0; i < size; i++) arr[i] = output[i]; } void sort_radix(int arr[], int size) { int max = get_max_element(arr, size); for (int place = 1; max / place > 0; place *= 10) sort_counting(arr, size, place); } 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 sort_radix(arr, n); cout << "So luong phan tu trong mang: " << n << endl; for (int i : arr) { cout << i << " "; } return 0; }

nghiammo1992 · gửi bởi **nghiammo1992** » 12/09/2021 12:32

Thuật toán sắp xếp nhanh Quick Sort

Mã: Chọn tất cả: #include <iostream> using namespace std; void quickSort(int Data[], int l , int r) { // If the first index less or equal than the last index if (l <= r) { // Create a Key/Pivot Element int key = Data[(l+r)/2]; // Create temp Variables to loop through array int i = l; int j = r; while (i <= j) { while (Data[i] < key) i++; while (Data[j] > key) j--; if (i <= j) { swap(Data[i], Data[j]); i++; j--; } } // Recursion to the smaller partition in the array after sorted above if (l < j) quickSort(Data, l, j); if (r > i) quickSort(Data, i, 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 quickSort(arr, 0, n-1); cout << "So luong phan tu trong mang: " << n << endl; for (int i : arr) { cout << i << " "; } return 0; }

nghiammo1992 · gửi bởi **nghiammo1992** » 12/09/2021 12:34

Thuật toán Counting Sort – Thuật toán sắp xếp đếm phân phối (thuật toán tốt hơn Quick Sort, nhưng tốn bộ nhớ hơn)

Mã: Chọn tất cả: #include <iostream> using namespace std; // Function that sort the given input void counting_sort(int input[], int n) { int output[n]; // The output will have sorted input array int max = input[0]; int min = input[0]; for(int i = 1; i < n; i++) { if(input[i] > max) max = input[i]; // Maximum value in array else if(input[i] < min) min = input[i]; // Minimum value in array } int k = max - min + 1; // Size of count array int count_array[k]; // Create a count_array to store count of each individual input value fill_n(count_array, k, 0); // Initialize count_array elements as zero for(int i = 0; i < n; i++) count_array[input[i] - min]++; // Store count of each individual input value /* Change count_array so that count_array now contains actual position of input values in output array */ for(int i = 1; i < k; i++) count_array[i] += count_array[i - 1]; // Populate output array using count_array and input array for(int i = 0; i < n; i++) { output[count_array[input[i] - min] - 1] = input[i]; count_array[input[i] - min]--; } for(int i = 0; i < n; i++) input[i] = output[i]; // Copy the output array to input, so that input now contains sorted values } 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 counting_sort(arr, n); cout << "So luong phan tu trong mang: " << n << endl; for (int i : arr) { cout << i << " "; } return 0; }

nghiammo1992 · gửi bởi **nghiammo1992** » 12/09/2021 12:36

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; }

CHIASE123.COM - Diễn đàn chia sẻ kiến thức

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

[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

Re: [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

Ai đang trực tuyến?