选择排序 Java 带有示例的程序

选择排序如何工作？

选择排序实现了一个简单的排序算法，如下所示：

• 算法重复搜索最低元素。
• 将当前元素与具有最低值的元素交换
• 每次选择排序的迭代/传递都会交换元素。

因此，每一次传递都会处理 排列 数据被分为两个区域：一个从左侧增长的有序块和一个从右侧缩小的无序块。算法遍历无序块，记住遇到的最小值的索引，并将该值与第一个无序位置交换。

由于每次循环只进行一次交换，因此最多经过 n-1 次交换，n 个元素的数组即可排序。正是这一特性使该例程区别于其他入门级例程。 Java 排序算法会更频繁地移动数据。

此 trac下面 e 遵循示例数组 {860, 8, 200, 9}，与下一节中的程序在运行时打印它的方式完全相同。

其中有两个细节 trac值得仔细观察。首先，即使顺序没有改变，第三次迭代仍然报告了交换操作，因为剩余元素中最小的值已经位于当前索引处，程序会将该元素与自身交换。其次，每次迭代的比较次数都减少一次（三次，两次，一次），这与页面下方复杂度数据的规律相符。

Java 实现选择排序的程序

下面这个类名为 SelectionSortAlgo，位于 com.guru99 包中。`main()` 方法声明了一个示例数组，打印出来，然后将其传递给 `selection()` 函数进行排序，最后再次打印出来。辅助函数 `printArray()` 将所有元素写入一行，从而生成易于阅读的逐行日志。

在 selection() 函数内部，外层循环标记了已排序区域和未排序区域之间的边界，变量 index 保存了迄今为止看到的最小值的位置，每次循环结束时的三个赋值操作执行交换。

package com.guru99;
 
public class SelectionSortAlgo {
 
	public static void main(String a[])
	{  
		int[] myArray = {860,8,200,9}; 
		
		System.out.println("------Before Selection Sort-----");
 
		printArray(myArray);
 
 
		selection(myArray);//sorting array using selection sort  
 
		System.out.println("-----After Selection Sort-----");  
 
		printArray(myArray); 
	} 
	
		public static void selection(int[] array)
	{  
		for (int i = 0; i < array.length - 1; i++)  
		{  System.out.println("Sort Pass Number "+(i+1));
			int index = i;  
			for (int j = i + 1; j < array.length; j++)
			{   
			    System.out.println("Comparing "+ array[index]  + " and " + array[j]);  
				if (array[j] < array[index]){ 
				System.out.println(array[index]  + " is greater than " + array[j] );
					index = j;
				
				
				}  
			}  
 
			int smallerNumber = array[index];   
			array[index] = array[i];  
			array[i] = smallerNumber;  
			System.out.println("Swapping Elements: New Array After Swap");
			printArray(array);
		}  
	}  
	static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
 
}

输出：

编译并运行该类后，会生成以下控制台日志，每次运行输出一个块。

------Before Selection Sort-----
860 8 200 9 
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Comparing 8 and 200
Comparing 8 and 9
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 860 and 200
860 is greater than 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860 
Sort Pass Number 3
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 9 200 860 
-----After Selection Sort-----
8 9 200 860

初学者在首次运行此示例时会遇到两个问题。因为该文件声明了 package com.guru99;源必须位于匹配的 com/guru99 否则，编译器会报告包名或类名不匹配。此时，必须使用类的完全限定名来启动该类。 java com.guru99.SelectionSortAlgo因为朴素 java SelectionSortAlgo 引发 NoClassDefFoundError 错误。

循环边界是另一个常见的陷阱。外层循环会在以下位置停止： array.length - 1 内循环从 i + 1更改任一边界都会导致额外的空传递或 ArrayIndexOutOfBoundsException 异常。

选择排序的时间和空间复杂度

程序中的内层循环总是运行到数组末尾，因此无论数据如何变化，算法执行的比较次数都相同。对于一个包含 n 个元素的数组，比较次数总共为 n(n-1)/2，对于包含四个元素的样本，则比较次数为 6 次，而上面的输出也确实打印了 6 行比较结果。

由这组均匀分布的数字可以得出三个结论：

• 选择排序不具备自适应性。已排序的输入和已逆序输入的成本完全相同，因此不存在提前退出的捷径。 气泡排序 提供。
• 交换次数是该算法的优势所在。最多只发生 n-1 次交换，远少于其他简单排序算法可能需要进行的二次方级的移动次数。
• 内存使用量是恒定的。只需要循环计数器和两个临时变量 index 和 smallerNumber，因此辅助空间为 O(1)，排序操作直接在原地进行。

二次增长是实际应用中的极限。数组大小翻倍，比较工作量大致翻四倍，因此选择排序更适合教学、小型数组和嵌入式代码，而非生产数据集，在生产数据集中，O(n log n) 算法才是正确的选择。

选择排序的优点和缺点

了解算法在哪些方面有所帮助，在哪些方面会造成损害，可以更容易地决定何时使用算法才是合理的。

优势

• 逻辑简洁易懂，因此它是一种标准的初级排序练习。 插入排序.
• 它进行原地排序，因此不会分配第二个数组，内存使用量也不会随着输入而增长。
• 它最多对数组执行 n-1 次写入操作，这对于写入速度慢或会磨损介质的存储设备来说很重要。
• 它的运行时间完全可预测，因为比较次数仅取决于数组长度。

缺点

• 每个案例的时间复杂度都是 O(n²)，因此该算法无法扩展到大型数据集。
• 它无法检测到已排序的数组，因此永远不会提前完成。
• 上面所示的经典形式是不稳定的，因此两个相等的值最终可能会以相反的顺序排列。
• 在近乎有序的数据上，插入排序的比较频率比插入排序更高，而插入排序的时间接近线性时间。

简而言之，当数组较小且每次写入成本较高时，选择选择排序；而当数据集较大或已接近排序时，则避免选择排序。

选择排序与 Bubble排序与插入排序

这三种算法都是二次原地比较排序算法，但一旦输入的形状发生变化，它们的行为就会有所不同。

表格解释了一个常见的面试答案。选择排序的优势在于交换次数少，冒泡排序的优势在于能够识别已排序的输入，而插入排序在实践中通常是最快的，因为实际数据往往是部分有序的。一旦数组元素超过几十个，它们都无法与归并排序或快速排序相媲美。

常见问题