选择排序
比较一下下面两张图,可以看出来,冒泡是循环着将两个相邻的元素进行比较,一直找最大值,以此类推。
而选择排序则是用第一个元素和后面的元素挨个进行比较,每次循环都可以获取当时的最小值,以此类推。
如同理解冒泡排序要理解何为冒泡一样,理解选择排序就要理解何为选择。
选择排序每次都会用没有排序的第一个元素和未排序的序列中的值进行比较,选择出最小(最大值),然后从第一位开始,挨个放置,就如上图中显示的一样,这样,已经排好序的部分就不会再参与比较选择了。
选择排序和冒泡排序在处理的过程中都会将部分元素先进行排序,这种方式不占用额外的内存(不适用额外的变量)。
还有一种情况是需要使用额外内存的,先稍稍理解下:
上体育课了,老师要排队:
A老师扫了一眼参差不齐的队伍,然后拨拉着同学们的脑袋,队伍就排好了。
B老师发现队伍很长,拨拉脑袋不好排,就先找出各自最低的同学,让站到一边,然后不断地找他认为个子最低的同学,让排在那个同学身后,这样就重新排了个队伍。重新排的这个队伍就是额外的内存。
代码实现为:
#include <iostream>
using namespace std;
/**
* 定义一个选择排序的函数,传入数组的数组的长度
**/
void selectSort(int arr[], int n)
{
for (int i=0; i<n-1; i++) { // 每次和其他数比较的元素
for(int j = i+1; j<n;j++) { // 待比较的数(即还没有排序的数,已经排好序的数不再参与比较)
if(arr[i] > arr[j]){
swap(arr[i], arr[j]); // 交换作比较的数组两个位置的值,这里调用的swap是C++提供的函数
}
}
}
}
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90}; // 要排序的一维数组
int n = sizeof(arr) / sizeof(arr[0]); // 获取数组的长度,sizeof用来获取当前对象在内存中占用的大小
cout << "排序前的数组为: ";
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
selectSort(arr, n); // 调用排序函数
cout << "\n 排序后的数组为: ";
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}
一条评论
发表新评论
- Pingback: 插入排序