在MySort.cpp中完成两个排序方法。 mergeSort(int* arr, int len); 实现归并排序,需要排序的数组为arr,数组长度为len cardSort(int* arr, int len); 实现基数排序,需要排序的数组为arr,数组长度为len 整数基数排序的一个方法:可以逐位取 &获得不同位的信息,例如,第一趟基数排序时,将序列中的数字(a & 0xf0000000),就得到了最高四位的数值,可以首先对最高位比较大小并进行排序。
时间: 2024-03-16 13:44:25 浏览: 42
插入排序:主函数中先定义了一个待排序的数组 arr,然后调用 insertionSort 函数进行排序,并打印出排序后的结果
好的,我会在MySort.cpp中实现这两个排序方法。以下是归并排序和基数排序的代码实现:
```c++
// 归并排序
void merge(int* arr, int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
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 l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void mergeSort(int* arr, int len) {
mergeSort(arr, 0, len - 1);
}
// 基数排序
void countSort(int* arr, int n, int exp) {
int output[n];
int i, count[10] = { 0 };
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}
void cardSort(int* arr, int len) {
int max = arr[0];
for (int i = 1; i < len; i++) {
if (arr[i] > max)
max = arr[i];
}
for (int exp = 1; max / exp > 0; exp *= 10)
countSort(arr, len, exp);
}
```
请注意,这是C++代码。如果您使用的是其他编程语言,请相应地进行修改。
阅读全文