用C++,先输入产生随机数的个数,进行随机数产生的输出,分别用简单选择排序、直接插人排序、冒泡排序、快速排序、两路合并排序以及堆排序进行排序,进行排序结果的输出,写出完整程序
时间: 2024-03-22 18:39:43 浏览: 48
C语言/C++如何生成随机数
5星 · 资源好评率100%
好的,以下是用C++实现的完整程序:
```cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
// 生成随机数序列
void generateRandomArray(int arr[], int len) {
srand((unsigned)time(NULL));
for (int i = 0; i < len; i++) {
arr[i] = rand() % 100;
}
}
// 输出数组
void printArray(int arr[], int len) {
for (int i = 0; i < len; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
// 交换两个数
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 简单选择排序
void simpleSelectionSort(int arr[], int len) {
for (int i = 0; i < len - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(arr[i], arr[minIndex]);
}
}
}
// 直接插入排序
void insertionSort(int arr[], int len) {
for (int i = 1; i < len; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
// 冒泡排序
void bubbleSort(int arr[], int len) {
bool flag = true;
for (int i = 0; i < len - 1 && flag; i++) {
flag = false;
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
flag = true;
}
}
}
}
// 快速排序
void quickSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int pivotIndex = (left + right) / 2;
int pivot = arr[pivotIndex];
int i = left, j = right;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
quickSort(arr, left, j);
quickSort(arr, i, right);
}
// 两路合并排序
void merge(int arr[], int left, int mid, int right) {
int* tempArr = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
tempArr[k++] = arr[i++];
}
else {
tempArr[k++] = arr[j++];
}
}
while (i <= mid) {
tempArr[k++] = arr[i++];
}
while (j <= right) {
tempArr[k++] = arr[j++];
}
for (int i = 0; i < k; i++) {
arr[left + i] = tempArr[i];
}
delete[] tempArr;
}
void mergeSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
// 堆排序
void adjustHeap(int arr[], int i, int len) {
int temp = arr[i];
for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
if (k + 1 < len && arr[k] < arr[k + 1]) {
k++;
}
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
}
else {
break;
}
}
arr[i] = temp;
}
void heapSort(int arr[], int len) {
// 构建大根堆
for (int i = len / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, len);
}
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
adjustHeap(arr, 0, i);
}
}
int main() {
int len;
cout << "请输入随机数的个数:";
cin >> len;
int* arr = new int[len];
generateRandomArray(arr, len);
cout << "随机数序列为:";
printArray(arr, len);
// 简单选择排序
simpleSelectionSort(arr, len);
cout << "简单选择排序结果:";
printArray(arr, len);
// 直接插入排序
insertionSort(arr, len);
cout << "直接插入排序结果:";
printArray(arr, len);
// 冒泡排序
bubbleSort(arr, len);
cout << "冒泡排序结果:";
printArray(arr, len);
// 快速排序
quickSort(arr, 0, len - 1);
cout << "快速排序结果:";
printArray(arr, len);
// 两路合并排序
mergeSort(arr, 0, len - 1);
cout << "两路合并排序结果:";
printArray(arr, len);
// 堆排序
heapSort(arr, len);
cout << "堆排序结果:";
printArray(arr, len);
delete[] arr;
return 0;
}
```
你可以直接复制上述代码,粘贴到你的 C++ 编辑器中运行。注意,堆排序算法中使用的是大根堆,因此排序结果是从小到大的顺序。
阅读全文