图解选择排序
1. 图示过程
选择排序图示
2. 文字叙述过程
- 第1趟比较：拿第1个元素依次和它后面的每个元素进行比较，如果第1个元素大于后面某个元素，交换它们，经过第1趟比较，数组中最小的元素被选出，它被排在第一位
- 第2趟比较：拿第2个元素依次和它后面的每个元素进行比较，如果第2个元素大于后面某个元素，交换它们，经过第2趟比较，数组中第2小的元素被选出，它被排在第二位
- ......
- 第n-1趟比较：第n-1个元素和第n个元素作比较，如果第n-1个元素大于第n个元素，交换它们
3. Java代码实现
public static void selectionSort(int[] nums) {
int temp;
for(int i = 0; i < nums.length - 1; i++) {
for(int j = i + 1; j < nums.length; j++) {
if(nums[i] > nums[j]) {
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
}4. 复杂度
- 时间复杂度：O(n²)
- 空间复杂度：O(1)，只需要一个附加程序单元用于交换
- 稳定性：不稳定 因为算法的时间效率与初始数组的顺序性有很大关系，所有选择排序是不稳定的排序算法
5. 优化
上面的算法的缺点：在每趟比较过程中，一旦发现某个元素比第1位的元素小，就交换它们，但这是没必要的，徒增了交换的次数 优化：选择排序的核心是，在每趟比较中，找到本趟中最小的元素放在本趟比较的第1个位置，所以选择排序的每趟比较只需要交换一次即可，只要找到本趟比较中最小的元素和本趟比较中第1位置的元素交换即可
public static void selectionSort(int[] nums) {
for(int i = 0; i < nums.length - 1; i++) {
int minIndex = i;
for(int j = i + 1; j < nums.length; j++) {
if(nums[minIndex] > nums[j]) {
minIndex = j;
}
}
if(minIndex != i) {
int tmp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = tmp;
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.09.12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录