实现直接插入排序算法、直接选择排序、快速排序、堆排序算法,并用main函数测试,若能给出排序过程可加分。
时间: 2023-10-20 17:10:51 浏览: 30
好的,我可以帮您实现这些排序算法。这里提供 C++ 代码实现,每个算法都包含排序函数和辅助函数(如果需要的话)。
### 直接插入排序
```c++
#include <iostream>
#include <vector>
using namespace std;
void insertSort(vector<int>& nums) {
int len = nums.size();
for (int i = 1; i < len; ++i) {
int temp = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > temp) {
nums[j + 1] = nums[j];
--j;
}
nums[j + 1] = temp;
}
}
int main() {
vector<int> nums = {5, 2, 4, 6, 1, 3};
insertSort(nums);
for (auto num : nums) {
cout << num << " ";
}
return 0;
}
```
### 直接选择排序
```c++
#include <iostream>
#include <vector>
using namespace std;
void selectSort(vector<int>& nums) {
int len = nums.size();
for (int i = 0; i < len - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < len; ++j) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(nums[i], nums[minIndex]);
}
}
}
int main() {
vector<int> nums = {5, 2, 4, 6, 1, 3};
selectSort(nums);
for (auto num : nums) {
cout << num << " ";
}
return 0;
}
```
### 快速排序
```c++
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& nums, int low, int high) {
int pivot = nums[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
if (nums[j] < pivot) {
++i;
swap(nums[i], nums[j]);
}
}
swap(nums[i + 1], nums[high]);
return i + 1;
}
void quickSort(vector<int>& nums, int low, int high) {
if (low < high) {
int pivotIndex = partition(nums, low, high);
quickSort(nums, low, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, high);
}
}
int main() {
vector<int> nums = {5, 2, 4, 6, 1, 3};
quickSort(nums, 0, nums.size() - 1);
for (auto num : nums) {
cout << num << " ";
}
return 0;
}
```
### 堆排序
```c++
#include <iostream>
#include <vector>
using namespace std;
void maxHeapify(vector<int>& nums, int i, int heapSize) {
int l = 2 * i + 1, r = 2 * i + 2, largest = i;
if (l < heapSize && nums[l] > nums[largest]) {
largest = l;
}
if (r < heapSize && nums[r] > nums[largest]) {
largest = r;
}
if (largest != i) {
swap(nums[i], nums[largest]);
maxHeapify(nums, largest, heapSize);
}
}
void buildMaxHeap(vector<int>& nums) {
int heapSize = nums.size();
for (int i = heapSize / 2 - 1; i >= 0; --i) {
maxHeapify(nums, i, heapSize);
}
}
void heapSort(vector<int>& nums) {
buildMaxHeap(nums);
int heapSize = nums.size();
for (int i = nums.size() - 1; i >= 1; --i) {
swap(nums[0], nums[i]);
--heapSize;
maxHeapify(nums, 0, heapSize);
}
}
int main() {
vector<int> nums = {5, 2, 4, 6, 1, 3};
heapSort(nums);
for (auto num : nums) {
cout << num << " ";
}
return 0;
}
```
以上是四种常见的排序算法的 C++ 代码实现,每个算法都包含排序函数和 main 函数测试代码。如果需要输出排序过程,可以在排序函数中添加一些额外的代码,例如打印每一轮排序后的数组。