选择排序 Java 示例

原文： https://howtodoinjava.com/algorithm/selection-sort-java-example/

选择排序是一种简单且缓慢的排序算法，反复从未排序部分中选择最低或最高元素，然后将其移至已排序部分的末尾。 通常，从性能角度来看，它甚至比插入排序还要慢。 它不会以任何方式适应数据，因此其运行时间始终是二次的。

但是，您不应得出结论，永远不要使用选择排序。 好东西是选择排序具有的属性，可将每次迭代的交换次数减至最少。 在交换项目成本很高的应用中，选择排序可能是很好的选择算法。

选择排序算法

以下是逻辑代码结构或通常的选择排序的伪代码。

for i = 1:n,
k = i
for j = i+1:n, if a[j] < a[k], k = j
//-> invariant: a[k] smallest of a[i..n]
swap a[i,k]
//-> invariant: a[1..i] in final position
end

用简单的英语来说，会发生以下情况：

1. 数据元素分为两部分：一个已排序的部分（最初为空）和一个未排序的部分（最初为完整数组）。
2. 假定排序顺序是从低到高，请从未排序部分中找到可比较顺序最低的元素。
3. 将找到的元素放在已排序部分的末尾。
4. 重复步骤 2 和 3，直到未排序的部分中没有剩余的元素。

选择排序 Java 源代码

以下是 Java 中的示例选择排序实现。

public class SelectionSortExample 
{
    public static void main(String[] args) {
        // This is unsorted array
        Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };
        // Let's sort using selection sort
        selectionSort(array, 0, array.length);
        // Verify sorted array
        System.out.println(Arrays.toString(array));
    }
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static void selectionSort(Object[] array, int fromIndex, int toIndex) 
    {
        Object d;
        for (int currentIndex = fromIndex; currentIndex < toIndex; currentIndex++) 
        {
            int indexToMove = currentIndex;
            for (int tempIndexInLoop = currentIndex + 1; tempIndexInLoop < toIndex; tempIndexInLoop++) 
            {
                if (((Comparable) array[indexToMove]).compareTo(array[tempIndexInLoop]) > 0) 
                {
                    //Swapping
                    indexToMove = tempIndexInLoop;
                }
            }
            d = array[currentIndex];
            array[currentIndex] = array[indexToMove];
            array[indexToMove] = d;
        }
    }
}
Output: [3, 6, 10, 12, 13, 24, 70, 90]

如果你们知道有什么方法可以提高选择排序的性能，请分享。 我无能为力。

学习愉快！