选择排序（selection sort）的基本思想是：每一趟在序列 sq[1],sq[2],...,sq[length]中选取关键字最大的记录作为序列最后一个记录，然后再从剩下的记录中选取最大的记录作为序列倒数第二个记录...，直到整个序列有序。《数据结构》中如是描述：每一趟在 n-i+1 (i=1,2,...,n-1)个记录中选取最小的记录作为有序序列中第 i 个记录。常见的选择排序包括：简单选择排序，树形选择排序，堆排序。分别给予实现 2.简单选择排序 对 sq[1,2,...,n]中记录进行简单选择排序算法为：令 i 从1至n-1，进行n-1趟选择操作，每次选择最小的和 sq[i] 交换。代码如下： /* * 对sq+1,sq+2,sq+3,...,sq+length 进行简单选择排序 */ void SelectSort(int *sq,int length){ int min; for(int i=1;isq[i]*/ int tmp; tmp=sq[i]; sq[i]=sq[min]; sq[min]=tmp; } } } 可见，简单选择排序过程中需要进行移动记录的次数较少，最小值为0，最大时为3(n-1)。然而，无论记录的初始排列如何，所需进行的关键字之间的比较操作次数相同，均为 n(n-1)/2 ，因此总时间复杂度为 O(n^2)。

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。