2011年软考程序员考试复习笔试知识点整理(5)7

 　直接选择排序

　　算法思想：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中的第i个记录

　　时间复杂度 o(n^2)

　　空间复杂度 o(1) ?

　　比较次数 n(n+1)/2

　　*/

　　int SelectMinKey(int array[],int iPos,int len)

　　{

　　int ret = 0;

　　for (int i = iPos; i < len; i++)

　　{

　　if (array[ret] > array[i])

　　{

　　ret = i;

　　}

　　}

　　return ret;

　　}

　　void select_sort(int array[],int len)

　　{

　　for (int i = 0; i < len; i++)

　　{

　　int j =SelectMinKey(array,i,len);

　　if (i != j)

　　{

　　swap(array[i],array[j]);

　　}

　　}

　　}

　　/*