logo头像
Snippet 博客主题

【庖丁解题】排序算法之选择排序剖析

选择排序

从0索引开始,依次和后面元素比较,小的往前放,第一次完毕,最小值出现在了最小索引处。其它的同理,即可得到一个排好序的数组。

图解

第一轮:索引为0的元素按照顺序分别与其他索引元素进行比较,如果arr[0]>arr[i],交换他们之间的元素值,如下图

第二轮:索引为1的元素按照顺序分别与其他索引元素进行比较,如果arr[1]>arr[i],交换他们之间的元素值,如下图

第三轮:索引为2的元素按照顺序分别与其他索引元素进行比较,如果arr[2]>arr[i],交换他们之间的元素值,如下图

第四轮:索引为3的元素按照顺序分别与其他索引元素进行比较,如果arr[3]>arr[i],交换他们之间的元素值,如下图

经过四轮排序,可以发现我们的数组已经按照升序排好序了。

代码实现

根据上述图片,可以先把每轮的有代码实现

第一轮

1
2
3
4
5
6
7
8
9
int x=0;//标记用于比较的起始索引
for (int y=x+1;y<arr.length;y++) {//y表示用于和x比较的索引值
if (arr[x] > arr[y]) {//比较大小
//交换元素
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}

第二轮

1
2
3
4
5
6
7
8
9
int x=1;//标记用于比较的起始索引
for (int y=x+1;y<arr.length;y++) {//y表示用于和x比较的索引值
if (arr[x] > arr[y]) {//比较大小
//交换元素
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}

第三轮

1
2
3
4
5
6
7
8
9
int x=2;//标记用于比较的起始索引
for (int y=x+1;y<arr.length;y++) {//y表示用于和x比较的索引值
if (arr[x] > arr[y]) {//比较大小
//交换元素
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}

第四轮

1
2
3
4
5
6
7
8
9
int x=3;//标记用于比较的起始索引
for (int y=x+1;y<arr.length;y++) {//y表示用于和x比较的索引值
if (arr[x] > arr[y]) {//比较大小
//交换元素
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}

最终版

转化成循环表示如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 选择排序
* @param arr
* @return
*/
public static int[] selectSort(int[] arr){
for (int x = 0; x < arr.length - 1; x++) {//控制的是排序的轮数
for (int y = x + 1; y < arr.length; y++) {//控制每轮比较的次数
if (arr[x] > arr[y]) {//比较大小
//交换元素
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
}
return arr;
}
微信打赏

赞赏是不耍流氓的鼓励