排序算法之选择排序

选择排序法（selection sort）

来自维基百科
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序算法

Selection Sort:
Set current to the index of first item in the list
While (not sorted yet)
    Find the index of the smallest unsorted item
    Swap the current item with the smallest unsorted one
    Increment current to shrink unsorted part

Java实现

这里的算法实现是我自己通过自己的理解用Java写的，如有纰漏，错误或不合理的地方还请大家指出并包涵

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class SelectionSort{
    public static void main(String[] args) {
        List<Integer> notSorted = new ArrayList<Integer>();
        notSorted.add(44);
        notSorted.add(34);
        notSorted.add(14);
        notSorted.add(54);
        notSorted.add(24);

        int index = 0;
        while (index < notSorted.size()){

            //Find the index of the smallest unsorted item
            int minIndex = notSorted.indexOf(Collections.min(notSorted.subList(index, notSorted.size())));

            //Swap the current item with the smallest unsorted one
            int temp = notSorted.get(index);
            notSorted.set(index, notSorted.get(minIndex));
            notSorted.set(minIndex, temp);

            index++;

            System.out.println("-------------");
            for (int i = 0; i < notSorted.size(); i++) {
                System.out.println(notSorted.get(i));
            }
        }
    }
}

这里的输出结果是每循环一次就输出一次，以方便理解排序的具体过程。

最后希望能对大家在理解选择排序算法上有所帮助。