黑马程序员技术交流社区
标题:
Java中的经典算法之选择排序（SelectionSort）
[打印本页]
作者:
zhanglic_wb
时间:
2019-3-9 18:10
标题:
Java中的经典算法之选择排序（SelectionSort）
本帖最后由 zhanglic_wb 于 2019-3-9 18:19 编辑
a
)
原理：每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。也就是：每一趟在n
-
i
+
1
(
i
=
1
，
2
，…n
-
1
)
个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。（这里只介绍常用的简单选择排序）
b
)
简单选择排序的基本思想：给定数组：
int
[]
arr
=
{
里面n个数据
}
；第1趟排序，在待排序数据arr
[
1
]
~
arr
[
n
]
中选出最小的数据，将它与arrr
[
1
]
交换；第2趟，在待排序数据arr
[
2
]
~
arr
[
n
]
中选出最小的数据，将它与r
[
2
]
交换；以此类推，第i趟在待排序数据arr
[
i
]
~
arr
[
n
]
中选出最小的数据，将它与r
[
i
]
交换，直到全部排序完成。
c
)
举例
int
arr
[]
=
{
7
,
6
,
4
,
3
,
45
,
12
}
;
int
count
=
0
;
for
(
int
i
=
0
;
i
<
arr
.
length
-
1
;
i
++
) {
count
++;
System
.
out
.
println
(
"第"
+
count
+
"轮循环："
)
;
for
(
int
j
=
i
+
1
;
j
<
arr
.
length
;
j
++
) {
if
(
arr
[
i
]
>
arr
[
j
]) {
int
temp
=
arr
[
i
]
;
arr
[
i
]
=
arr
[
j
]
;
arr
[
j
]
=
temp
;
}
System
.
out
.
println
(
Arrays
.toString
(
arr
))
;
}
}
//System.out.println(Arrays.toString(arr));
int
arr
[]
=
{
7
,
6
,
4
,
3
,
45
,
12
}
;
第1轮循环：数组个数arr.length，外层循环arr.length-1次
内循环循环一次 数组arr[j]和arr[0]进行比较[比较5次]，进行交换
[6, 7, 4, 3, 45, 12]
[4, 7, 6, 3, 45, 12]
[3, 7, 6, 4, 45, 12]
[3, 7, 6, 4, 45, 12]
[3, 7, 6, 4, 45, 12]
第2轮循环：
内循环循环 数组arr[j]和arr[1]进行比较[比较4次]，进行交换
[3, 6, 7, 4, 45, 12]
[3, 4, 7, 6, 45, 12]
[3, 4, 7, 6, 45, 12]
[3, 4, 7, 6, 45, 12]
第3轮循环：
内循环循环 数组arr[j]和arr[2]进行比较[比较3次]，进行交换
[3, 4, 6, 7, 45, 12][3, 4, 6, 7, 45, 12][3, 4, 6, 7, 45, 12]
第4轮循环：
内循环循环 数组arr[j]和arr[3]进行比较[比较2次]，进行交换
[3, 4, 6, 7, 45, 12][3, 4, 6, 7, 45, 12]
第5轮循环：
内循环循环 数组arr[j]和arr[4]进行比较[比较4次]，进行交换得到最终结果
[3, 4, 6, 7, 12, 45]
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2