选择排序法:科学运算方法-中文百科频道

基本思想

排序定义。所谓计算机中的排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。而排序算法（Sorting algorithm）则是一种能将一串数据依照特定的方式进行排列的一种算法。n排序方式。利用所需重排记录的排序码（Sort Key）的值的大小，按照升序或降序将原纪录的顺序重新安排。排序类别。内排序可以分为插入排序（insertion sort）、选择排序（selection sort）、交换排序（exchange sort）、归并排序（merge sort）以及分配排序（distribution sort）。n选择排序法是在要排序的一组数中，选出最小（或最大）的一个数与第一个位置的数交换；在剩下的数当中找最小的与第二个位置的数交换，即顺序放在已排好序的数列的最后，如此循环，直到全部数据元素排完为止。

算法描述

选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换。

简单选择排序算法分析：在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n2)。

选择排序法是对定位比较交换法（也就是冒泡排序法）的一种改进。在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解，设有10个数分别存在数组元素a～a中。定位比较交换法是由大到小依次定位a～a中恰当的值（和武林大会中的比武差不多），a中放的自然是最小的数。如定位a,先假定a中当前值是最大数，a与后面的元素一一比较，如果a更大，则将a、a交换，a已更新再与后面的a～a比较，如果a还要大，则将a、a交换，a又是新数，再与a比较。一轮比完以后，a就是最大的数了，本次比武的武状元诞生了，接下来从a开始，因为状元要休息了，再来一轮a就是次大的数，也就是榜眼，然后从a开始，比出探花，真成比武大会了，当比到a以后，排序就完成了。

稳定性

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。