选择排序也是一种比较排序,而与冒泡排序相近但不相同。
1.冒泡排序是通过相邻数字进行比较,交换从而得到一个有序的序列。(比较的同时进行交换)
2.选择排序是用一个变量比如m来记录最小(大)值得位置,然后将下标为m的数组元素交换到相应的位置。(比较和交换操作分开)
算法思想:
1.一个外循环,一个内循环,外循环中还有一个if判断语句,外循环控制排序需要的次数,内循环控制比较,if判断m的位置以及是否需要交换。
2.外循环每循环一次,内循环则需要找到最小值的位置并用m记录,if判断m的位置是否在相应的顺序上,不在则将m位置的元素交换到相应的位置上。
下面用代码演示:
public class happy {
public static void main(String[] args) {
int array[]= {1,3,64,23,97,65,45,2,78};
for(int i=0;i<array.length-1;i++) {
int m=i;//用变量m的值来记录此次循环找到最小值的位置。
for(int j=i+1;j<array.length;j++) {//外循环循环一次,该内循环就得到一个最小值并放置在数组前边。 if(array[j]<array[m]) { m=j;//只将最小值的下标记录给m,并未对数组元素的顺序进行更改。 }}
if(m!=i)//m的初始值为变量i的值,若m==i,则说明此次循环的i的位置就是最小值,则不需要交换其位置。 { int temp=array[m]; array[m]=array[i]; array[i]=temp; }}
for(int i=0;i<array.length;i++) { System.out.println(array[i]); } }}
需要注意的几点:
1.
外循环的循环次数i的次数为array.length-1。
2.
内循环j的初值是i+1(将排好序的i个数字排除在外),m在进入内循环之后,初值代表数组未排好序数字的第一个元素,之后就一直用来记录最小值元素的位置,j=i+1则代表未排好序的第二个元素.
PS:这里如果看懂的人肯定会想j的初值为什么不写成j=m+1呢?
因为m在进入内循环后就一直用来记录最小值元素的位置,其值会发生变化。j从i+1代表未排好序的第二个元素,j一直在与最小值元素(即m的位置)进行比较,若j位置的元素小于m位置的元素,就将j的位置记录给m。从而完成对最小值元素位置的记录。
3.
m每次循环的初值为i,也就是说m的初值为i的位置,若内循环未对m进行变动,则表明m的位置就是最小的元素且m==i,所以最小值元素在相应的位置上,无需对其进行交换。