什么是选择排序,如何用c++实现
时间: 2023-07-16 11:16:19 浏览: 43
选择排序是一种简单直观的排序算法,其基本思想是每次从待排序的元素中选择最小的一个元素,将其放到已排序的序列的末尾,直到所有元素均排序完毕。具体实现步骤如下:
1. 遍历待排序的序列,找到最小的元素。
2. 将最小元素与序列的第一个元素交换位置。
3. 在剩余的元素中继续重复上述步骤,直到所有元素均被排序。
下面是使用C++实现选择排序的示例代码:
```
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
swap(arr[i], arr[min_idx]);
}
}
```
其中,`arr`表示待排序的数组,`n`表示数组的长度。在每次遍历中,使用`min_idx`记录当前未排序部分中最小元素的下标,然后将其与第`i`个元素交换位置。通过多次这样的操作,最终得到排好序的数组。
需要注意的是,选择排序的时间复杂度为$O(n^2)$,不适合对大规模数据进行排序。
相关问题
用c++实现简单选择排序
以下是用C++实现简单选择排序的代码示例:
```c++
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
int i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++) {
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: \n";
for (int i=0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
```
用c++实现快速排序和选择排序
好的,下面是用 C++ 实现快速排序和选择排序的示例代码。
快速排序:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void quickSort(vector<int>& nums, int left, int right) {
if (left >= right) return; // 只有一个元素或者没有元素,直接返回
int pivot = nums[left]; // 选取最左边的元素作为基准值
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= pivot) j--;
nums[i] = nums[j];
while (i < j && nums[i] <= pivot) i++;
nums[j] = nums[i];
}
nums[i] = pivot; // 基准值归位
quickSort(nums, left, i - 1); // 递归排序左边部分
quickSort(nums, i + 1, right); // 递归排序右边部分
}
int main() {
vector<int> nums = {3, 5, 2, 1, 6, 4, 8, 7};
quickSort(nums, 0, nums.size() - 1);
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
```
选择排序:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void selectionSort(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(nums[i], nums[minIndex]);
}
}
}
int main() {
vector<int> nums = {3, 5, 2, 1, 6, 4, 8, 7};
selectionSort(nums);
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
```
相关推荐
![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)