转载:算法:选择排序SelectionSort
原文链接:https://zhuanlan.zhihu.com/p/104109752
我脱下短袖
公众号『算法无遗策』
已关注
简单选择排序属性
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
回顾一下上次快速排序的优化,减少不必要的交换,以后在解决过程中可以把符合条件的元素位置标记下来,因此可以定义一个标记变量,来标记本轮比较中最符合条件的元素,本轮结束时才进行最后一步的是否交换。
视频动画:简单选择排序
算法动画视频 地址 https://www.bilibili.com/video/av79595402/
[高清 720P] 选择排序.flv
Code
package cn.study.sort;
import java.util.Arrays;
public class SelectionSort1 {
public static void selectSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int min = i;
for (int j = i + 1; j < array.length; j++) {
if(array[min] > array[j]){
min = j;
}
}
swap(array, i, min);
}
}
public static void swap(int[] array, int i, int j){
if(i == j){return;}
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
System.out.println("下标" + i + ", " + j + "已交换。" + Arrays.toString(array));
}
public static void main(String[] args) {
int[] array = {5,1,9,3,7,4,8,6,2};
System.out.println("初始状态:" + Arrays.toString(array));
selectSort(array);
System.out.println(Arrays.toString(array));
}
}
Result
初始状态 [5, 1, 9, 3, 7, 4, 8, 6, 2]下标0,1已交换[1, 5, 9, 3, 7, 4, 8, 6, 2]下标1,8已交换[1, 2, 9, 3, 7, 4, 8, 6, 5]下标2,3已交换[1, 2, 3, 9, 7, 4, 8, 6, 5]下标3,5已交换[1, 2, 3, 4, 7, 9, 8, 6, 5]下标4,8已交换[1, 2, 3, 4, 5, 9, 8, 6, 7]下标5,7已交换[1, 2, 3, 4, 5, 6, 8, 9, 7]下标6,8已交换[1, 2, 3, 4, 5, 6, 7, 9, 8]下标7,8已交换[1, 2, 3, 4, 5, 6, 7, 8, 9]
喜欢本文的朋友,微信搜索「算法无遗策」公众号,收看更多精彩的算法动画文章