选择排序是指不断地从待排序的记录序列中选取关键字最小的记录，依次放到已排好序的子序列的最后，直到全部记录排好序。
选择排序的基本思想：第一趟从所有的n个记录中，通过顺序比较各关键字的值，选取关键字值最小的记录与第一个记录交换；第二趟从剩余的n-1个记录中选取关键字值最小的记录与第二个记录交换；……，第i趟从剩余的n-i+1个记录中选取关键字值最小的记录，与第i个记录交换；……；经过n-1趟排序后，整个序列就成为有序序列。
选择排序的具体实现过程如下：
（1）将整个记录序列划分为有序区和无序区，有序区位于最左端，无序区位于右端，初始状态的有序区为空，无序区中有未排序的所有n个记录。
（2）设置一个整型变量index，用于记录一趟里面的比较过程中当前关键字值最小的记录位置。开始将index设定为当前无序区的第一个位置，即假设这个位置的关键字值最小，然后将它与无序区中其他记录进行比较，若发现有比它的关键字值小的记录，就将index修改为这个新的最小记录位置。随后再将R[index]与后面的记录进行比较，并随时修改index的值，一趟结束后，index中保留的就是本趟选择的关键字值最小的记录位置。
（3）将index位置的记录交换到有序区的最后一个位置，使有序区增加了一个记录，而无序区减少了一个记录。
（4）不断重复步骤（2）和（3），直到无序区只剩下一个记录为止，此时所有的记录已经按关键字值从小到大的顺序排列就位。(www.xing528.com)
选择排序算法如下：
【例9.3】假定n=8，文件中各个记录的关键字为（47，36，64，95，73，11，27，47），其中有两个相同的关键字47，后一个用下画线标记。
每次进行选择和交换后的记录排列情况如下所示，假设[…]为有序区，{…}为无序区。
由算法可以发现，不论关键字的初始状态如何，在第i趟排序中选出最小关键字的记录，都需做n-i次比较。因此，总的比较次数为：
当初始状态为正序时，不需要移动记录，即移动次数为0；当初始状态为逆序时，每趟排序均要执行交换操作，每趟交换操作需做3次移动操作，总共进行n-1趟排序，所以总的移动次数为3（n-1）次。可见，选择排序算法的时间复杂度为O（n2）。整个排序过程只需要一个记录大小的辅助存储空间用于记录交换，其空间复杂度为O（1）。选择排序会使关键字值相同的记录交换相对位置，所以选择排序是不稳定的排序方法。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
