在MySort.cpp中完成两个排序方法。 mergeSort(int* arr, int len); 实现归并排序,需要排序的数组为arr,数组长度为len cardSort(int* arr, int len); 实现基数排序,需要排序的数组为arr,数组长度为len 整数基数排序的一个方法:可以逐位取 &获得不同位的信息,例如,第一趟基数排序时,将序列中的数字(a & 0xf0000000),就得到了最高四位的数值,可以首先对最高位比较大小并进行排序。
时间: 2024-03-16 20:44:33 浏览: 56
插入排序:主函数中先定义了一个待排序的数组 arr,然后调用 insertionSort 函数进行排序,并打印出排序后的结果
好的,我可以帮你完成这两个排序方法。以下是 MySort.cpp 中的代码实现:
归并排序 mergeSort(int* arr, int len):
```cpp
void merge(int* arr, int l, int mid, int r) {
int i = l, j = mid + 1, k = 0;
int* tmp = new int[r - l + 1];
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i <= mid) {
tmp[k++] = arr[i++];
}
while (j <= r) {
tmp[k++] = arr[j++];
}
for (i = l, k = 0; i <= r; i++, k++) {
arr[i] = tmp[k];
}
delete[] tmp;
}
void mergeSort(int* arr, int l, int r) {
if (l < r) {
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
}
void mergeSort(int* arr, int len) {
mergeSort(arr, 0, len - 1);
}
```
基数排序 cardSort(int* arr, int len):
```cpp
void cardSort(int* arr, int len) {
int maxNum = arr[0], exp = 1;
int* tmp = new int[len];
for (int i = 1; i < len; i++) {
if (arr[i] > maxNum) {
maxNum = arr[i];
}
}
while (maxNum / exp > 0) {
int card[10] = {0};
for (int i = 0; i < len; i++) {
card[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
card[i] += card[i - 1];
}
for (int i = len - 1; i >= 0; i--) {
tmp[--card[(arr[i] / exp) % 10]] = arr[i];
}
for (int i = 0; i < len; i++) {
arr[i] = tmp[i];
}
exp *= 10;
}
delete[] tmp;
}
```
希望这两个排序方法能够满足你的需求。
阅读全文