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

选择排序(Selection Sort)算法简介:

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

选择排序(Selection Sort)算法原理:

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

  • 从待排序列中选出最小(或最大)的一个元素,记录其下标的位置;
  • 将记录的下标值与待排序列的第一个元素进行交换;
  • 以此类推,直到全部待排序列的元素排完。

举例说明:

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

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

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

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

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

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

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

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

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

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

选择排序(Selection Sort)代码实现:

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²)。

上一篇:the selection cannot be run on any server错误解决方法


下一篇:Codeforces Round #646 (Div. 2) A. Odd Selection(思维/分类讨论)