DoubleRight The past of the world Blog's

选择排序 Java 示例

选择排序 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]

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

学习愉快！

搜索