题目描述 完整实现6种不同的排序算法，并比较它们的时间复杂度和空间复杂度。所有排序算法必须自行编写代码实现，不允许使用任何内置或第三方的排序算法库。最后，提交所有实现的代码、实验报告，报告中需要对每个测试用例的算法运行时间进行比较。 输入说明： 第一行为数字1~6，对应6种不同的排序方式，分别为以下6种： 1. 冒泡排序 2. 直接插入排序 3. 简单选择排序 4. 2路归并排序 5. 快速排序 6. 堆排序 第二行为需要排序的数字个数 num（ 1 <= num <= 1e5), 数字类型type (0为int, 1为float) 第三行为需要排序的数列，用空格隔开 数字确保不超过int和float的表示范围 注意：浮点数据类型请使用float，使用double可能由于精度不一致导致输出结果不匹配 输出说明 最终排序为升序，为保证输出的确定性，对以下排序算法中间步骤进行说明，最终输出格式请参考示例 1.冒泡排序 输出每一轮迭代的交换元素 输出总共交换的次数 2.直接插入排序 输出每一轮迭代元素插入的位置 3.简单选择排序 输出每一轮迭代，最小的index 4.2路归并排序 输出每一次

以下是冒泡排序的 C++ 代码实现： ```cpp #include <iostream> using namespace std; // 冒泡排序函数 void bubbleSort(int arr[], int n) { int temp; int swapCount = 0; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; cout << "Swap " << swapCount << " : " << arr[j] << " and " << arr[j + 1] << endl; swapCount++; } } cout << "Iteration " << i << endl; } cout << "Total swaps: " << swapCount << endl; } // 打印数组函数 void printArray(int arr[], int size) { for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } // 测试案例 int main() { int arr[] = {70, 33, -59, 16, -56, 63, 80, -21, 75, -5, 90, -4, 72, -61, -39, -97, 44, 9, 18, 14}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Bubble Sort" << endl; bubbleSort(arr, n); cout << "Sorted array: "; printArray(arr, n); return 0; } ``` 以下是直接插入排序的 C++ 代码实现： ```cpp #include <iostream> using namespace std; // 直接插入排序函数 void insertionSort(int arr[], int n) { int key, j; for (int i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; cout << "Number " << arr[i] << " inserts at position " << j + 1 << endl; } } // 打印数组函数 void printArray(int arr[], int size) { for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } // 测试案例 int main() { int arr[] = {70, 33, -59, 16, -56, 63, 80, -21, 75, -5, 90, -4, 72, -61, -39, -97, 44, 9, 18, 14}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Insertion Sort" << endl; insertionSort(arr, n); cout << "Sorted array: "; printArray(arr, n); return 0; } ``` 额外需要注意的逻辑点： 1. 注意代码中的边界情况，例如数组为空或只有一个元素的情况。 2. 对于排序算法的时间和空间复杂度的分析要准确。 3. 确保代码的可读性和可维护性，添加必要的注释。 [2025-01-10 13:19:29 | AI写代码神器 | 859点数解答]