经典算法之选择排序(Selection Sort)

发表于 | 分类于

原理

选择排序是一种简单直观的排序算法，其基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录并与第二个位置记录交换；重复该过程，直到进行比较的记录只剩下一个为止。
举例说明：要排序数组：int[] arr = {6, 3, 8, 2, 9, 1};

第一趟排序：原始数据：6 3 8 2 9 1
最小数据为1，把1放在首位，也就是1和6交换位置，
排序结果：1 3 8 2 9 6

第二趟排序：除第一个元素以外的其他数据进行比较{3 8 2 9 6}, 2最小，2和3交换位置，
排序结果：1 2 8 3 9 6

第三趟排序：除1、2以外的其他数据进行比较{8 3 9 6}, 3最小，3和8交换位置，
排序结果：1 2 3 8 9 6

第四趟排序：除1、2、3以外的其他数据进行比较{8 9 6}, 6最小，6和8交换位置，
排序结果：1 2 3 6 9 8

第五趟排序：除1、2、3、6以外的其他数据进行比较{8 9}, 8最小，8和9交换位置，
排序结果：1 2 3 6 8 9

最终结果：1 2 3 6 8 9

注：每一趟排序获取最小数的方法：for循环进行比较，将当前下标定义为最小值下标值用临时变量temp保存，然后用temp再去跟剩下的数据比较，如果出现比temp小的数据，就用它代替temp中原有的数据。

时间复杂度

简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 n 个元素，则比较次数永远都是n (n - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3n (n - 1) / 2。

所以，综上，简单排序的时间复杂度为 O(n2)。

尽管与冒泡排序同为O(n2)，但简单选择排序的性能要优于冒泡排序。

代码实现

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
private static void SelectionSort(int[] nums) {
	int length = nums.length;
	for (int i = 0; i < length - 1; i++) {
		int k = i;  //临时变量k，假使k为最小元素
		for (int j = i+1; j < nums.length; j++) { // 选最小的记录
			if (nums[j] < nums[k]) {
			     k = j;  //记下目前找到的最小值所在的位置
			}
		}
		if (i != k) {
		     swapNums(nums, i, k);
		}
	}
		
	for (int i : nums) {
	    System.out.println(i + " ");
	}
}
	
private static int[] swapNums(int[] nums, int i, int j) {
//		int tmp = nums[i];
//		nums[i] = nums[j];
//		nums[j] = tmp;
		
	nums[i] = nums[i]^nums[j];
	nums[j] = nums[i]^nums[j];
	nums[i] = nums[i]^nums[j];
	return nums;
}