极客笔记C++ 通过执行给定的操作，对数组进行排列，以获得递增的顺序
您必须使用适当的排序算法来使用指定的操作对数组进行排序，以获得递增的顺序。根据数组的大小和数据属性，首先确定最有效的方法。冒泡排序、归并排序和快速排序是常见的排序算法示例。重复应用所选择的算法，根据元素之间的比较来移动元素的位置，直到数组按升序排列为止。算法的效率由它的耗时来决定，最好的算法能够产生更快的结果。通过谨慎使用所选的排序方法，可以有效地按递增顺序对数组进行排列，使数据的操作和分析更加容易。
使用的方法
- 冒泡排序
-
归并排序
-
快速排序
冒泡排序
冒泡排序是一种简单直观的排序技术，可以用来将数组按升序排列。它通过不断比较相邻的数组元素，判断它们是否按正确的顺序排列，并在需要时进行交换。重复这个过程，直到整个数组排序完成。您可以使用这种排序方法快速对数组按升序排列。但与归并排序或快速排序等其他排序算法相比，冒泡排序对于较大的数组来说效果较差，因为它的最坏情况时间复杂度为O(n2)。
步骤
- 从未排序的元素数组开始。
-
比较第一个和第二个元素。如果第一个元素大于第二个元素，则交换它们。
-
如果需要，对下一对相邻元素进行比较和交换过程进行重复。
-
直到数组的末尾，对每一对相邻元素重复这个过程。
-
经过一次遍历后，最大的元素最终会“冒泡”到最后一个位置。
-
对于剩下的数组元素（除了最后一个已经排序的元素），重复步骤2到5，直到整个数组按升序排列。
-
数组现在按增序排列，表示排序操作结束。
示例
#include <iostream>
template <typename T, size_t N>
void bubbleSort(T (&arr)[N]) {
for (size_t i = 0; i < N - 1; ++i) {
for (size_t j = 0; j < N - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}
输出
11 12 22 25 34 64 90
归并排序
归并排序使用分而治之的策略来按升序排列数组。它将数组分为两半，然后递归地分别对每个子数组进行排序。然后将排序好的子数组合并在一起，确保元素按升序排列。一旦完成这个操作，数组就完全排序好了。归并排序是一个有效的方法，可以在所有情况下保证时间复杂度为O(n log n)，使得数据处理和分析更加简单。
步骤
- 如果数组只包含一个元素或为空，则数组已经排序好了。返回原始数组。
-
将数组分成两个相等的部分。
-
对每个部分应用归并排序，独立地对它们进行排序。
-
重构两个排序好的部分，确保其中的元素按升序排列。
比较两个部分中的元素，将较小的元素添加到一个临时的组合数组中。
继续处理较小元素所在的子数组中的下一个元素。
在两个部分合并之前，进行比较和合并操作。
- 用合并后的数组替代原始数组。
-
在对整个数组进行排序后，继续递归。
-
归并排序技术被成功地用于按升序排序数组。
示例
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
void mergeSort(int arr[], int left, int right);
void merge(int arr[], int left, int mid, int right);
int main() {
const int size = 10;
int arr[size];
srand(time(0));
cout << "Original Array: ";
for (int i = 0; i < size; i++) {
arr[i] = rand() % 100;
cout << arr[i] << " ";
}
mergeSort(arr, 0, size - 1);
cout << "\nSorted Array: ";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
return 0;
}
void mergeSort(int arr[], int left, int right) {
}
void merge(int arr[], int left, int mid, int right) {
}
输出
Original Array: 64 10 16 73 95 69 25 68 11 45
Sorted Array: 64 10 16 73 95 69 25 68 11 45
快速排序
通过选择数组中的一个“枢轴”元素将数组分割成较小和较大的子数组，根据通常称为快速排序的常见排序技术。该方法然后迭代地对这些子数组进行排序。一旦完成此操作，数组就会完全排序。由于其平均时间复杂度为O(n log n)，快速排序对大数组非常有效。通过谨慎使用快速排序可以将数组重新排列成升序，使数据处理和分析更加简单。
步骤
- 从列表中选择一个重要元素；这个元素可以是任何一个，但通常是第一个、最后一个或中间的成员。
-
重新排列数组的项，创建一个分区，将较小的元素放在左侧，较大的元素放在右侧。
-
以递归的方式对左右两个分区（小于和大于枢轴的项）应用快速排序。
-
对每个分区重复该过程，直到子数组中包含的元素为零或只有一个元素为止。
-
当递归取消时，将子数组连接起来生成最终排序的数组。
示例
#include <iostream>
#include <vector>
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int main() {
std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
int n = arr.size();
quickSort(arr, 0, n - 1);
std::cout << "Sorted array: ";
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}
输出
Sorted array: 3 9 10 27 38 43 82
结论
总之，综合考虑Bubble Sort（冒泡排序）、Merge Sort（归并排序）和Quick Sort（快速排序）这三种排序算法来将一个数组按照递增顺序组织起来，每种方法都有其优点和缺点。虽然构建简单，但是由于其最坏情况时间复杂度为O(n2)，当处理大型数组时，冒泡排序的效率会大大降低。归并排序适用于较大规模的数据集，并且由于其时间复杂度为O(n log n)，在所有情况下都表现稳定。快速排序由于其高效性，在绝大多数情况下表现良好，它的平均时间复杂度也是O(n log n)。具体的排序算法取决于被排序数据的要求和特性。