选择排序(Selection sort）跟插入排序一样，也是O(n^2)的复杂度，这个排序方式也可以用我们的扑克牌来解释。

概念

桌面上有一堆牌，也是杂乱无章的，现在我们想将牌由小到大排序，如果使用选择排序来做，应该是这样来做。

1. 遍历桌面牌堆里的牌，从第一张牌到最后一张，找到牌面最小的一张，然后将抽出，并扣在手上。
2. 第二次遍历桌面牌堆里的牌，从第一张牌到最后一张，仍然去找现在桌面上牌面最小的一张，找出来，还是扣在手上。
3. 第三次遍历……重复步骤。虽然桌面上的牌是无序的，但是我们扣在手上的牌是有序的。
4. 第N次遍历……重复直到结束，现在桌面上没有牌，所有的牌都抓在手里，而且手上的牌全是排序排好的。
   
   这个过程就是选择排序。

伪代码 - SelectionSort(seq)

n = seq.length

for j=1 to n-1

	smallest = j

	for i = j+1 to n

		if seq[i] < seq[smallest]

			smallest = i

	exchange seq[j] with seq[smallest]

注：

j=1指的是第一个元素，即我们常常的seq[0]。

套用一种语言来实现算法。

Python版

def sort(seq):

	n = len(seq)

	for j in range(n - 1):

		smallest = j

		for i in range(j + 1, n):

			if seq[i] < seq[smallest]:

				smallest = i

		if smallest != j:

			seq[j], seq[smallest] = seq[smallest], seq[j]

	return seq

Python版源码：Github-Syler-Fun-Selectionsort-Python

Java版

public static int[] sort(int[] seq)

{

 int n = seq.length;

 for(int j = 0; j < n - 1; j++){

   int smallest = j;

   for(int i = j + 1; i < n; i++){

     if(seq[i] < seq[smallest]){

       smallest = i;

     }

     if(smallest !=j) {

       int temp = seq[smallest];

       seq[smallest] = seq[j];

       seq[j] = temp;

     }

   }

 }

 return seq;

}

Java版源码：Github-Syler-Fun-Selectionsort-Java

看起来还是Python写起来比较短一点呢。