189 8069 5689
上面文章讲完了插入排序和交换排序，本次我们来讨论选择排序。
选择排序(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;
}另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。