选择排序
思路
1、在每次遍历的过程中,都假定第一个索引处的元素是最小值,和其他索引处的值依次进行比较,如果当前索引处的值大于其他某个索引的值,则假定其他某个索引处的值为最小值,最后可以找到最小值所在的索引。
2、交换第一个索引处和最后一个索引处的值。
原始数据
第一轮遍历
本轮需要进行4次比较,也就是(数组的长度-1)次
第一次比较:
3比6小,所以假定最小值的索引为 0
第二次比较:
3比4小,所以假定最小值的索引为0
第三次比较:
3比1大,所以假定最小值的索引为3
第四次比较:
1比2小,所以假定最小值的索引为3
交换第一个索引的值和最小值的索引的值
第一轮遍历代码
public class SelectSort {
public static void main(String[] args) {
int[] value = {3,6,4,1,2};
new SelectSort().sort(value);
System.out.println("第一轮遍历");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value){
int index = 0;
int temp;
for (int i = 0; i < value.length - 1; i++) {
if (value[index] > value[i+1]){
index = i +1;
}
}
temp = value[0];
value[0] = value[index];
value[index] = temp;
}
}
第二轮遍历
第一个数字已经是最小的了,所以我们此时应该从第二个数字开始遍历,也就是从索引处为 1 的地方开始遍历。
本轮需要进行4次比较,也就是(数组的长度-2)次
第一次比较:
第二次比较:
第三次比较:
交换第一个索引(也就是我们开始遍历的索引位置,也就是索引1)的值和最小值的索引的值
第二轮遍历代码
public class SelectSort {
public static void main(String[] args) {
int[] value = {1,6,4,3,2};
new SelectSort().sort(value);
System.out.println("第二轮遍历");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value){
int index = 1;
int temp;
for (int i = 1; i < value.length - 1; i++) {
if (value[index] > value[i+1]){
index = i +1;
}
}
temp = value[1];
value[1] = value[index];
value[index] = temp;
}
}
第三轮遍历
二个数字已经是最小的了,所以我们此时应该从第三个数字开始遍历,也就是从索引处为 2 的地方开始遍历。
本轮需要进行2次比较,也就是(数组的长度-3)次
第一次比较:
第二次比较:
交换第一个索引(也就是我们开始遍历的索引位置,也就是索引2)的值和最小值的索引的值
第三轮遍历代码
public class SelectSort {
public static void main(String[] args) {
int[] value = {1,2,4,3,6};
new SelectSort().sort(value);
System.out.println("第二轮遍历");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value){
int index = 2;
int temp;
for (int i = 2; i < value.length - 1; i++) {
if (value[index] > value[i+1]){
index = i +1;
}
}
temp = value[2];
value[2] = value[index];
value[index] = temp;
}
}
第四轮遍历
前三个数字已经是最小的了,所以我们此时应该从第四个数字开始遍历,也就是从索引处为 3 的地方开始遍历。
本轮需要进行1次比较,也就是(数组的长度-4)次
第一次比较:
交换第一个索引(也就是我们开始遍历的索引位置,也就是索引3)的值和最小值的索引的值
第四轮遍历代码
public class SelectSort {
public static void main(String[] args) {
int[] value = {1,2,4,3,6};
new SelectSort().sort(value);
System.out.println("第四轮遍历");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value){
int index = 3;
int temp;
for (int i = 3; i < value.length - 1; i++) {
if (value[index] > value[i+1]){
index = i +1;
}
}
temp = value[3];
value[3] = value[index];
value[index] = temp;
}
}
规律
共进行4轮遍历,也就是(数组的长度-1)轮,每轮比较的次数是(数组的长度-1-索引)
所以我们可以用外层循环控制轮数,内层循环控制比较次数
public class SelectSort {
public static void main(String[] args) {
int[] value = {3,6,4,1,2};
new SelectSort().sort(value);
System.out.println("排序结果");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value){
for (int j = 0; j < value.length-1; j++) {
int index = j;
int temp = 0;
for (int i = j; i < value.length - 1; i++) {
if (value[index] > value[i + 1]) {
index = i + 1;
}
}
temp = value[j];
value[j] = value[index];
value[index] = temp;
System.out.println("第" + (j+1) + "轮:");
for (int i : value) {
System.out.print(i + ",");
}
System.out.println("");
}
}
}