Java的选择排序

1 说明

我们可以创建一个Java程序来使用选择排序对数组元素进行排序。在选择排序算法中，我们搜索最低的元素并将其排列到正确的位置。我们将当前元素与下一个最低编号交换。

2 选择排序算法

选择排序算法以非常简单的方式工作。它为给定的数组维护两个子数组。

• 子数组已经排序。
• 第二个子数组是未排序的。

在每次选择排序迭代时，都会从未排序的子数组中选取一个元素，然后将其移至已排序的子数组。

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   

3 时间复杂度

Best: ?(n^2)
Average: ?(n^2)
Worst: O(n^2)

4 空间复杂度

O(1)

5 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
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 Sort
9 14 3 2 43 11 58 22 
After Selection Sort
2 3 9 11 14 22 43 58