用C＋＋实现 1.实现简单选择排序、直接插入排序和冒泡排序。 2.实现希尔排序算法。 3.实现快速排序算法。 4.实现堆排序算法。 5.快速排序的非递归算法。6.在主函数里由键盘输入输入一组关键字序列调试运行这些算法

当然，我可以为你介绍如何使用C++实现这些排序算法以及提供相应的示例代码。让我们逐一来看： 1. **简单选择排序（Selection Sort）**: ``` void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { int minIndex = i; for (int j = i + 1; j < n; ++j) { if (arr[j] < arr[minIndex]) { minIndex = j; } } std::swap(arr[i], arr[minIndex]); } } ``` 2. **直接插入排序（Insertion Sort）**: ``` void insertionSort(int arr[], int n) { for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } ``` 3. **冒泡排序（Bubble Sort）**: ``` void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { for (int j = 0; j < n - i - 1; ++j) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); } } } } ``` 4. **希尔排序（Shell Sort, 希尔增量为gap数组决定）**: ``` // 这里只给出基础版本，可以根据需求调整gap序列 void shellSort(int arr[], int n) { const int gaps[] = {10, 7, 5, 3, 2, 1}; for (gap : gaps) { for (int i = gap; i < n; i++) { int temp = arr[i]; for (int j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = temp; } } } ``` 5. **快速排序（Quicksort, 递归版）**: ```cpp void quickSort(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 partition(int arr[], int low, int high) { // ... } ``` 6. **快速排序（Quicksort, 非递归版或Lomuto版本）**: ```cpp void quickSort(int arr[], int size) { stack<int> s; s.push({0, size - 1}); while (!s.empty()) { pair<int, int> range = s.top(); s.pop(); int pivotIndex = partition(arr, range.first, range.second); if (pivotIndex - 1 > range.first) s.push({range.first, pivotIndex - 1}); if (pivotIndex + 1 < range.second) s.push({pivotIndex + 1, range.second}); } } ``` 7. **堆排序（Heap Sort）**: ``` void heapify(int arr[], int n, int i) { // ... } void heapSort(int arr[], int n) { buildMaxHeap(arr, n); for (int i = n - 1; i > 0; --i) { swap(&arr[0], &arr[i]); heapify(arr, i, 0); } } ``` 8. **主函数中的键盘输入和排序调用**: ```cpp int main() { int arr[] = {...}; // 输入从键盘或文件 int n = sizeof(arr) / sizeof(arr[0]); cout << "Before sorting:\n"; for (int i : arr) { cout << i << " "; } selectionSort(arr, n); insertionSort(arr, n); bubbleSort(arr, n); shellSort(arr, n); quickSort(arr, n); heapSort(arr, n); cout << "\nAfter sorting:\n"; // 输出排序后的数组 return 0; } ```