选择法排序
选择法排序是一种简单的容易实现的对数据排序的算法。
以整形数组元素为例,有数组A[10](以C语言为例描述),即A[0],A[1],…,A[8],A[9](假设其元素均互不相同)。要求对其元素排序使之递增有序。
首先以一个元素为基准,从一个方向开始扫描,比如从左至右扫描,以A[0]为基准。
接下来从A[0],…,A[9]中找出最小的元素,将其与A[0]交换。
然后将基准位置右移一位,重复上面的动作,比如,以A[1]为基准,找出A[1]~A[9]中最小的,将其与A[1]交换。
一直进行到基准位置移到数组最后一个元素时排序结束(此时基准左边所有元素均递增有序,而基准为最后一个元素,故完成排序)。
以下为一个用C描述的函数实现上述排序:
void sort(int array[],int n)
{ // n 为数组元素个数
int i,j,k,temp; // i 为基准位置,j 为当前被扫描元素位置,k 用于暂存出现的较小的元素的位置
for(i=0;i<n-1;i++)
{k=i;//初始化为基准位置
for(j=i+1;j<n;j++)
{
if (array[j]<array[k]) k=j ; // k 始终指示出现的较小的元素的位置
if(k!=i)
{ temp=array[i];
array[i]=array[k];
rray[k]=temp; // 将此趟扫描得到的最小元素与基准互换位置
}
} //for
}
}
其实现相对简单,效率比较低,时间复杂度为O(n2) (n 的平方) ,为就地排序。