上面文章讲完了插入排序和交换排序，本次我们来讨论选择排序。
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面)。
1、普通(单个)选择排序
每遍历一次，记录下最值元素所在位置，遍历结束后，将此最值元素调整到合适的位置。这样一次遍历，只需一次交换，便可将最值放置到合适位置
计算
安全
数据库
网络和加速
企业服务
//成功返回0，失败返回-1
int select_sort(int *arr,const int n)
{
//判断参数是否正确
if(NULL == arr || 0 >= n)
return -1;
int i = 0; //循环使用
int j = 0; //循环使用
int k = -1; //记录比较的下标
int temp; //交换时作中间值
//每次循环只进行一次交换 最多进行n - 1次循环，因此总体上，比冒泡进行交换的次数少
for(i = 0; i < n - 1; i++)
{
//第i次排序时，已经进行了i次大循环，因此已经排好了i个元素
//已排好序的元素0，,...,i-2,i-1
//待排元素为i,i+1,...,n-1
k = i; //拿i的位置值与后面的值相比较
for(j = i + 1; j < n; i++)
{
if(arr[k] < arr[j])
k = j;
}
//判断k值是否有变化，有变量就交换
if(k != i)
{
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
}
return 0;
}2、二分选择排序
int select_sort(int *arr, const int n)
{
//判断参数是否正确
if(NULL == arr || 0 >= n)
return -1;
int i = 0;
int j = 0;
int minpos = -1;
int maxpos = -1;
int temp;
//每次循环完进行二次交换 最多进行n/2次循环，因此总体上，比冒普通选择排序的次数少
for(i = 0; i < n / 2; i++)
{
minpos = i;
maxpos = i;
for(j = i + 1; j < n; j++)
{
if(arr[j] > arr[maxpos])
{
maxpos = j;
continue;
}
if(arr[j] < arr[minpos])
{
minpos = j;
}
}
temp = arr[i];
arr[i] = arr[minpos];
arr[minpos] = temp;
if(maxpos == i)
{
temp = arr[minpos];
arr[minpos] = arr[n - 1 - i];
arr[n - 1 - i] = temp;
}
else
{
temp = arr[maxpos];
arr[maxpos] = arr[n - 1 - i];
arr[n - 1 -i] = temp;
}
}
return 0;
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
