选择排序 Java 示例

选择排序 Java 示例

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

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

选择排序算法

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

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

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

数据元素分为两部分：一个已排序的部分（最初为空）和一个未排序的部分（最初为完整数组）。

假定排序顺序是从低到高，请从未排序部分中找到可比较顺序最低的元素。

将找到的元素放在已排序部分的末尾。

重复步骤 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]

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