C语言或者C++实现,先生产n个随机数,然后完成下面操作: a)分别使用Insert sort和Merge sort对上述随机数进行排序,并分析其性能。 b)采用随机化快速排序算法对上述随机数进行排序。 c)设计一个基排序(Radix Sort)算法,对上述随机数进行排序。要求中间的稳定排序采用计数排序(Counting Sort)。
时间: 2024-02-09 07:08:18 浏览: 34
好的,我可以给您提供一个C++实现的代码。以下是实现分别使用Insert sort和Merge sort对随机数进行排序的代码:
```C++
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void insert_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int j = i - 1;
int temp = arr[i];
while (j >= 0 && arr[j] > temp) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, 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 merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid+1, right);
merge(arr, left, mid, right);
}
}
int main() {
// 生成随机数
srand(time(0));
const int n = 10;
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
// Insert sort
insert_sort(arr, n);
cout << "Insert sort: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// Merge sort
merge_sort(arr, 0, n-1);
cout << "Merge sort: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
以下是实现采用随机化快速排序算法对随机数进行排序的代码:
```C++
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int partition(int arr[], int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[right];
arr[right] = temp;
return i+1;
}
void randomized_quick_sort(int arr[], int left, int right) {
if (left < right) {
int pivot = rand() % (right - left + 1) + left;
int temp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = temp;
int p = partition(arr, left, right);
randomized_quick_sort(arr, left, p-1);
randomized_quick_sort(arr, p+1, right);
}
}
int main() {
// 生成随机数
srand(time(0));
const int n = 10;
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
// 随机化快速排序
randomized_quick_sort(arr, 0, n-1);
cout << "Randomized quick sort: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
以下是实现基排序(Radix Sort)算法的代码:
```C++
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int get_max(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 count_sort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i-1];
}
for (int i = n-1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
void radix_sort(int arr[], int n) {
int max = get_max(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10) {
count_sort(arr, n, exp);
}
}
int main() {
// 生成随机数
srand(time(0));
const int n = 10;
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
// 基排序(Radix Sort)
radix_sort(arr, n);
cout << "Radix sort: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```