首页 > 代码库 > JAVA选择排序

JAVA选择排序

选择排序(Selection sort)是一种简单直观的排序算法。
它的工作原理如下。
首先,在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,
然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
以此类推,直到所有元素均排序完毕。

 

 如,有一个数组为 int[] arrs=new int[]{2,5,4,3,2,1}

 

首先,我们在数组里面找出最小的值,存放在数组的第一位arrs[0]
目前arrs[0]=2,分别和索引位置为1,2,3,4,5的元素比较,其中和arrs[5]=1比较时,得到了最小值,并进行交换
第一次排序的结果是{1,5,4,3,2,2}
然后,我们在数组的剩下的位置查找第二小的元素(即剩下数组中的最小元素),存放在数组的第一位后面,也就是arrs[1]的位置
由于经过了一次排序,所以数组现在是这样的{1,5,4,3,2,2}
拿arrs[1]元素的值(注,这个位置的值会变)分别和索引为2,3,4,5的元素比较
arrs[1]=5比较arrs[2]=4,交换位置得{1,4,5,3,2,2}
arrs[1]=4比较arrs[3]=3,交换位置得{1,3,5,4,2,2}
arrs[1]=3比较arrs[4]=2,交换位置得{1,2,5,4,3,2}
arrs[1]=2比较arrs[5]=2,没有交换为{1,2,5,4,3,2}
在此,我们已经在数组的第二个位置存放了第二小的值
下面我们为数组第三的位置,选择第三小的值
由于经过了上次的排序,所以数组现在是这样的{1,2,5,4,3,2}
拿arrs[2]元素的值(注,这个位置的值会变)分别和索引为3,4,5的元素的值比较
arrs[2]=5比较arrs[3]=4,发生的交换,得数组为{1,2,4,5,3,2}
arrs[2]=4比较arrs[4]=3,发生的交换,得数组为{1,2,3,5,4,2}
arrs[2]=3比较arrs[5]=3,发生的交换,得数组为{1,2,2,5,4,3}
在此,我们已经的数组第三的位置存放了第三小的值
依次循环
......

到最后得到的数组为{1,2,2,3,4,5} 

整个数组的长度为6,只要我们依次选择好前5个位置存放的值,那么最后一个位置的值就不用比较了,因为最后一个数只有最后一个位置放了,也只能放那个位置
整个数组排列的重点在于选择的时候,在这个位置的元素和其后面的元素比较的时候,在比较没有完成的时候,所选择的那个位置的值也不是固定的;
就好像我们在第二个位置选择值的时候,在没有和后面的元素分别比较完的时候,随着比较的进行,第二个位置arrs[1]的值也一直的变,直到数组比较后最后
才定下了第二小的值为2.

 

  1 code

 2 
 3 public class SelectSort {
 4 
 5     public static void main(String[] args) {
 6 
 7         int[] arrs = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
 8         System.out.println("数组排序前");
 9         printArray(arrs);
10 
11         selectSort(arrs);
12 
13         System.out.println("数组排序后");
14         printArray(arrs);
15 
16     }
17 
18     // 选择排序算法
19     private static void selectSort(int[] arrs) {
20         // 选择的索引
21         for (int i = 0; i < arrs.length - 1; i++) {
22             // 拿这个索引的元素分别和其后面的元素比较,其中,每比较一次,arrs[i]位置元素的值都有可能发生交换
23             for (int p = i + 1; p < arrs.length; p++) {
24                 if (arrs[i] > arrs[p]) {
25                     int temp = arrs[i];
26                     arrs[i] = arrs[p];
27                     arrs[p] = temp;
28                 }
29             }
30         }
31     }
32 
33     // 打印数组方法
34     public static void printArray(int[] arrs) {
35         System.out.print("[");
36         for (int i = 0; i < arrs.length; i++) {
37             System.out.print(arrs[i]);
38             if (i != arrs.length - 1) {
39                 System.out.print(",");
40             }
41         }
42         System.out.println("]");
43     }
44 
45 }

JAVA选择排序