Java基础算法-排序-简单选择排序

排序算法之简单排序算法

算法原理

//原理：每次都找到当次最大的数，按大小顺序依次放入数组相应位置
//比如：第一次先找到最大的数并记下其位置，如果其不在数组第一位，
//则将其与第一位交换，使最大数置于第一位
//第二次再循环查找第二大的数并记下其位置，如果其不在数组第二位，
//则将其与第二位交换，使最大数置于第二位
//依次类推…………………………………..
//第i次再循环查找第i大的数并记下其位置，如果其不在数组第 i位，
//则将其与第 i位交换，使最大数置于第 i位

时间复杂度

平均、最坏、最好的时间复杂度都为O（n^2）,且是不稳定的排序算法

java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package zju.zsq.selectionsort;
import org.junit.Test;
public class SeletionSort {
	
	public void selectionSort(int[] num){
		int min = 0;
		int temp = 0;
		for (int i = 0; i < num.length; i++) {
			min = i;
			for (int j = i+1; j < num.length; j++) {
				if(num[min] > num[j]){
					min = j;
				}
			}
			if(i != min){
				temp = num[i];
				num[i] = num[min];
				num[min] = temp;
			}
		}
	}
	
	@Test
	public void testSelectionSort(){
		int[] nums = {4,2,1,3,7,8,9,11,6};
		selectionSort(nums);
		for(int num : nums){
			System.out.print(num+" ");
		}
	}
}
//输出如下：
1 2 3 4 6 7 8 9 11

简单选择排序是不是非常简单啊！

Algorithms
排序算法