Selection Sort

选择排序

The idea of the selection sort is to find the smallest element in the list and exchange it with the element in the first position. Then, find the second smallest element and exchange it with the element in the second position, and so on until the entire array is sorted.

选择排序就是在列表中找一个最小的元素，并且用第一个元素和它互换位置，然后找到第二小的元素用第二个位置的元素和它互换位置，直到整个数组都排好顺序；

Algorithm:

算法

For every index from 0 to number_of_elements-1, we find the element which is appropriate for that index and we swap the element which is already there with the element which has to be there. Finding the element which is appropriate for an index is simple. We just have to find the minimum value which is there from that index till number_of_elements-1.

每个索引从0到开始找到某个我们所需要的元素的索引，当找到这个合适的元素用另一个更应该适合这个索引的元素来替代它，我们只需要找到最小的元素，很简单就能找到合适元素索引，

1. minIndex denotes the index which has the minimum value which for now assumed to be

the value at current index and we update it in a for loop.

1.minIndex被认为对应着最小的值，用一个for循环更新现在索引对应的值

2. For elements from minIndex+1 to the last element of the list check if some index has got

element smaller than minimum then update minindex to be that index.

从列表中元素索引为minIndex+1到最后一个元素，看它们索引是否需要改变，当一个元素小于当前最小元素，那就将最小元素的索引进行跟新

3. Then swap the two elements i.e. the element at minidex in 1 and the element at the

updated minindex.

3然后交换索引为1和跟新索引的这两个元素

4. Follow the first three steps for every index from 0 to number_of_elements-1.

接着按照前三步的过程再去找

 Properties:

属性

Best case performance – When the list is already sorted O(n2).

Worst case performance - When the list is sorted in reverse order O(n2).

Average case performance – O(n2).

It does not require any extra space for sorting, hence O(1) extra space.

It is not stable.

O(n2) time complexity makes it difficult for long lists.

最好的情况下——当已排序列表O(n2)。

坏的情况下——当列表是按倒序排序O(n2)。

平均情况下——O(n2)。

它不需要任何额外的空间排序,因此额外的空间——O(1)。

它是不稳定的。

O(n2)时间复杂度很长。

选择排序