选择排序cpp每句代码及其解释
时间: 2024-06-11 09:02:21 浏览: 13
选择排序是一种简单直观的排序算法,其基本思想是每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。以下是选择排序的cpp代码及其解释:
```cpp
void selection_sort(int arr[], int n) { // 定义函数,传入待排序的数组和数组长度
int i, j, min_idx;
for (i = 0; i < n - 1; i++) { // 外层循环控制选择排序的轮数
min_idx = i; // 假设当前轮数下第一个元素为最小值
for (j = i + 1; j < n; j++) // 内层循环控制找到当前轮数下的最小值
if (arr[j] < arr[min_idx]) // 如果找到比假设最小值还要小的元素
min_idx = j; // 更新最小值下标
swap(&arr[min_idx], &arr[i]); // 将当前轮数下的最小值与第一个元素交换位置
}
}
```
以上是选择排序的cpp代码及其解释,其中`swap`函数用来交换两个元素的位置,可以自行实现或调用STL中的`std::swap`函数。
相关问题
桶排序步骤及c++代码
桶排序是一种线性时间复杂度的排序算法,适用于一定范围内的浮点数排序。下面是桶排序的步骤及C++代码示例:
步骤:
1. 创建一个固定大小的桶数组,每个桶存储一定范围内的元素。
2. 遍历待排序数组,将每个元素分配到对应的桶中。
3. 对每个桶中的元素进行排序,可以使用其他排序算法,也可以递归使用桶排序。
4. 将各个桶中的元素按顺序合并到待排序数组中。
C++代码示例:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void bucketSort(float arr[], int n) {
// 创建桶数组
vector<float> buckets[n];
// 将元素分配到对应的桶中
for (int i = 0; i < n; i++) {
int index = n * arr[i];
buckets[index].push_back(arr[i]);
}
// 对每个桶中的元素进行排序
for (int i = 0; i < n; i++) {
sort(buckets[i].begin(), buckets[i].end());
}
// 合并各个桶中的元素到待排序数组中
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
arr[index++] = buckets[i][j];
}
}
}
int main() {
float arr[] = {0.42, 0.32, 0.78, 0.62, 0.91, 0.16};
int n = sizeof(arr) / sizeof(arr[0]);
bucketSort(arr, n);
cout << "排序后的数组:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
这段代码实现了桶排序算法,对给定的浮点数数组进行排序。运行后输出排序后的数组:0.16 0.32 0.42 0.62 0.78 0.91。
计数排序步骤及c++代码
计数排序是一种非比较排序算法,适用于对一定范围内的整数进行排序。下面是计数排序的步骤及对应的C++代码示例:
步骤:
1. 找出待排序数组中的最大值max和最小值min;
2. 创建一个计数数组count,大小为max-min+1,用于记录每个元素出现的次数;
3. 遍历待排序数组,统计每个元素出现的次数,并在计数数组中对应的位置进行累加;
4. 根据计数数组中的累加值,重新构建排序后的数组;
5. 返回排序后的数组。
C++代码示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void countingSort(vector<int>& arr) {
int n = arr.size();
if (n <= 1) return;
int maxVal = arr[0], minVal = arr[0];
for (int i = 1; i < n; ++i) {
maxVal = max(maxVal, arr[i]);
minVal = min(minVal, arr[i]);
}
int countSize = maxVal - minVal + 1;
vector<int> count(countSize, 0);
for (int i = 0; i < n; ++i) {
count[arr[i] - minVal]++;
}
int index = 0;
for (int i = 0; i < countSize; ++i) {
while (count[i] > 0) {
arr[index++] = i + minVal;
count[i]--;
}
}
}
int main() {
vector<int> arr = {5, 3, 2, 6, 1, 9, 4, 8, 7};
countingSort(arr);
cout << "Sorted array: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}
```
这段代码实现了计数排序的功能。给定一个待排序的数组,通过调用`countingSort`函数进行排序,并输出排序后的结果。
注意:这只是计数排序的一个简单实现示例,仅对整数进行排序。对于其他数据类型或更复杂的排序需求,可能需要进行适当的修改。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)