选择排序法是一种不稳定的排序算法。选择排序法也是比较简单的排序算法，其思路比较直观，即在每步中选取最小值来重新排列，从而达到排序的目的。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
选择排序法
排序算法
中文名
选择排序法外文名
Selection sort method适用领域
数据结构所属学科
计算机科学分 类
简单选择排序、树型选择排序特 点
不稳定简介
基本思想
排序定义
所谓计算机中的排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。而排序算法（Sorting algorithm）则是一种能将一串数据依照特定的方式进行排列的一种算法。
排序方式
利用所需重排记录的排序码（Sort Key）的值的大小，按照升序或降序将原纪录的顺序重新安排。排序类别。内排序可以分为插入排序（insertion sort）、选择排序（selection sort）、交换排序（exchange sort）、归并排序（merge sort）以及分配排序（distribution sort）。
选择排序法是在要排序的一组数中，选出最小（或最大）的一个数与第一个位置的数交换；在剩下的数当中找最小的与第二个位置的数交换，即顺序放在已排好序的数列的最后，如此循环，直到全部数据元素排完为止。
算法描述
选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换 。
类别
常见的选择排序可以分为直接选择排序（Straight selection sort）、树形选择排序（Tree-type selection sort）以及堆排序（Heap sort）。
（1）直接选择排序
①基本思想。实现思想是每步从排序记录中选出排序码最小（最大）的记录，放在已排序记录序列的最后（前）；
②算法特点。直接选择排序算法n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
（2）树形选择排序。
①基本思想。其实现思想是保存先前比较的结果以减少比较次数，是一种不稳定的排序方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。
（3）堆排序。
①基本思想。堆排序是一种树形选择排序，是对直接选择排序的有效改进；
②算法描述。从算法描述来看，堆排序需要两个过程，即建立堆和堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成，一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数；
③算法特点。堆排序可通过树形结构保存部分比较结果，可减少比较次数。但由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
性能分析
时间复杂度
选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。
交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。其中直接选择排序的时间复杂度为O（n*n），空间复杂度为O（1）。树形选择排序的时间复杂度为O（nlog2n），空间复杂度为O（n）。堆排序的平均时间复杂度为O（nlog2n），效率高，但是实现相对复杂，空间代价为O（1）。
稳定性
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。
那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法 。
代码示例
C语言
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | void swap(int *a,int *b) { int temp = *a; *a = *b; *b = temp; } void selection_sort(int arr[], int len) { int i,j;
for (i = 0 ; i < len - 1 ; i++) { int min = i; for (j = i + 1; j < len; j++) if (arr[j] < arr[min]) min = j; swap(&arr[min], &arr[i]); } } |
C++
1 2 3 4 5 6 7 8 9 10 | template<typename T> void selection_sort(std::vector<T>& arr) { for (int i = 0; i < arr.size() - 1; i++) { int min = i; for (int j = i + 1; j < arr.size(); j++) if (arr[j] < arr[min]) min = j; std::swap(arr[i], arr[min]); } } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def selection_sort(arr): for i in range(len(arr)-1): minIndex=i for j in range(i+1,len(arr)): if arr[minIndex]>arr[j]: minIndex=j if i==minIndex: pass else: arr[i],arr[minIndex]=arr[minIndex],arr[i] return arr
if __name__ == '__main__': testlist = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12] print(selection_sort(testlist)) |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | public static void selectionSort(int[] arr) { int min, temp; for (int i = 0; i < arr.length; i++) { // 初始化未排序序列中最小数据数组下标 min = i; for (int j = i+1; j < arr.length; j++) { // 在未排序元素中继续寻找最小元素，并保存其下标 if (arr[j] < arr[min]) { min = j; } } // 将未排序列中最小元素放到已排序列末尾 if (min != i) { temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } } } |