Java常见经典算法详解-选择排序(Selection Sort)

  选择排序是利用逐个选择的方式进行排序，逐个选择出数组中的最小（或最大）的元素，顺序放在已排好序的序列后面，直到全部记录排序完毕。

例如我们有一个数组，我们需要把较小的元素排在前面，把较大的元素排在后面，那么需要选择出最小元素并将其排在序列最前：

举例说明：

现在需要对数组序列 6 1 7 8 9 3 5 4 2 运用选择排序算法从小到大排序。

第一轮：最小元素为1，把1放在首位，也就是1和6互换位置：1 6 7 8 9 3 5 4 2 

第二轮：将排序好的元素以外的序列6 7 8 9 3 5 4 2进行比较，最小元素为2，将2与第二位的6互换位置：1 2 7 8 9 3 5 4 6 

第三轮：将排序好的元素以外的序列7 8 9 3 5 4 6 进行比较，最小元素为3，将3与第三位的7互换位置：1 2 3 8 9 7 5 4 6 

.................

第n轮：重复同样的操作直到所有数字都归位为止，排序完成。

public class Demo { public static void main(String[] args) { int[] array= {6,1,7,8,9,3,5,4,2}; int[] newarray=selectionSort(array); for(int arr:newarray) { System.out.print(arr+" "); } } public static int[] selectionSort(int[] array){ //外层循环,控制选择的次数 for(int i=0;i<array.length-1;i++) { int min_index=i; //内存循环 for(int j=i+1;j<array.length;j++) { if(array[j]<array[min_index]) { min_index=j; } } if(min_index!=i) { int temp=array[i]; array[i]=array[min_index]; array[min_index]=temp; } } return array; } } 选择排序(Selection Sort)的时间复杂度：

选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较n-1个数字，第2轮需要比较n-2个数.....到第n-1轮的时候就只需比较1个数字了。因此，总的比较次数与冒泡排序的相同，都是(n-1)+(n-2) +...+1≈n²/2次。每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为O(n²)。

誉邦双鱼儿 原创文章 12获赞 6访问量 1381 关注 私信 展开阅读全文
作者：誉邦双鱼儿

JAVA 选择排序 选择 sort 算法 排序