用c++给定数组:A[8] = {16,25,5,8,13,1,10,3}。排序代码截图一定要清晰。 (1)使用归并排序实现对数组A的升序排列。 (2)使用快速排序实现对数组A的降序排列。
时间: 2024-12-14 09:19:41 浏览: 10
判定给定数组是否已排序
首先,我会分别给出归并排序和快速排序在C++中升序和降序排列数组A的示例代码,并提供简化的伪代码说明。由于这是一个文本平台,无法直接展示代码截图,但我可以详细描述代码以及如何操作。
**归并排序 (升序)**
```cpp
#include <vector>
using namespace std;
void merge(vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1+ j];
int 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++;
}
// Copy remaining elements of L[] if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector<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);
}
}
// 示例使用
int main() {
vector<int> A = {16, 25, 5, 8, 13, 1, 10, 3};
int size = A.size();
mergeSort(A, 0, size - 1);
// 输出已排序升序数组
for(int num : A)
cout << num << " ";
return 0;
}
```
**快速排序 (降序)**
```cpp
#include <vector>
using namespace std;
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// 如果当前元素大于或等于基准
if (arr[j] >= pivot) {
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]); // 将基准放在正确的位置
return (i + 1);
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 示例使用
int main() {
vector<int> A = {16, 25, 5, 8, 13, 1, 10, 3};
int size = A.size();
quickSort(A, 0, size - 1);
// 输出已排序降序数组
for(int num : A)
cout << num << " ";
return 0;
}
```
阅读全文