三、选择排序

依次从剩余记录中找出第i小的记录，不过它是先找到最小记录所在位置，然后直接交换到正确位置（本趟待排子序列的最前端），因此选择排序可以看作是对冒泡排序的一种改进。选择排序的算法思想与冒泡排序很类似，但与冒泡排序不同的是：冒泡排序不断比较并交换相邻记录，因此第i小的记录是一步步地越过前面比它大的那些记录，最后到达正确位置；而选择排序则是直接找出剩下的未排序记录中的最小记录，然后直接与数组中第i个记录交换，一步到位。这样，整个排序过程最多需要n-1次交换，而冒泡排序平均交换次数未O(n×n)，相比之下，选择排序的交换次数少多了。选择排序是不稳定的算法。