Java 选择排序
我们可以创建一个Java程序来使用选择排序对数组元素进行排序。在选择排序算法中，我们搜索最低的元素并将其排列到正确的位置。我们将当前元素与第二个最低的数字交换。
选择如何排序
选择排序算法的工作方式非常简单。它为给定的数组维护两个子数组。
该子数组已经排序。
第二个子数组未排序。
每次选择排序迭代时，都会从未排序的子数组中选取一个元素，然后将其移至已排序的子数组。
arr[] = 25 35 45 12 65 10
// Find the minimum element in arr[0...5] and place it at beginning.10 25 35 45 12 65
// Find the minimum element in arr[1...5] and place it at beginning of arr[1...5]10 12 25 35 45 65
// Find the minimum element in arr[2...5] and place it at beginning of arr[2...5]No, you can see that the array is already sorted. 10 12 25 35 45 65
时间复杂度
最佳: ？(n ^ 2)
平均值: ？(n ^ 2)
最差: O(n ^ 2)
空间复杂度
O(1)
选择排序Java示例
public class SelectionSortExample {
public static void selectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < arr[index]){
index = j;
//searching for lowest index }
}
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
public static void main(String a[]){
int[] arr1 = {
9,14,3,2,43,11,58,22}
;
System.out.println("Before Selection Sort");
for(int i:arr1){
System.out.print(i+" ");
}
System.out.println();
selectionSort(arr1);
//sorting array using selection sort System.out.println("After Selection Sort");
for(int i:arr1){
System.out.print(i+" ");
}
}
}
输出:
Before Selection Sort9 14 3 2 43 11 58 22 After Selection Sort2 3 9 11 14 22 43 58
选择Java排序(另一种方式)
您还可以使用未预定义数组的方法。在这里，用户必须将元素作为输入。
在下面的Java程序中，我们要求用户输入数组元素或数字，现在比较数组的元素并开始使用变量temp进行交换。将第一个元素放在temp中，将第二个元素放在第一个中，然后将temp放在第二个数字中，并继续进行下一个匹配以按升序对整个数组进行排序。
import java.util.Scanner;
public class SelectionSortExample2{
public static void main(String args[]) {
int size, i, j, temp;
int arr[] = new int[50];
Scanner scan = new Scanner(System.in);
System.out.print("Enter Array Size : ");
size = scan.nextInt();
System.out.print("Enter Array Elements : ");
for(i=0; i<size; i++) {
arr[i] = scan.nextInt();
}
System.out.print("Sorting Array using Selection Sort Technique..\n");
for(i=0; i<size; i++) {
for(j=i+1; j<size; j++) {
if(arr[i] > arr[j]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.print("Now the Array after Sorting is :\n");
for(i=0; i<size; i++) {
System.out.print(arr[i]+ " ");
}
}
}
