选择排序是八大排序算法之一,其排序原理是:
比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换其数据的索引位置,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成。选择排序与冒泡排序有点不同的是,选择排序是先交换下标,然后在交换数值。用文字叙述是讲不清楚的,还是通过流程来分析吧。
如现在有一组数据:[3, 1, 8, 6, 2, 5, 9, 4, 7]
使用选择排序对这组数据进行排序,具体流程:
第一趟排序: 定义一个下标 int index = 0; 即先指向第一个数3,感叹号代表下标。
3 1 8 6 2 5 9 4 7
!
(1) 把index指向的数和下标从1开始往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。即3>1,1的下标是1,所以index=1; 这时候下标index指向下标就是1。
3 1 8 6 2 5 9 4 7
!
(2) 把index指向的数和下标从2开始往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。后面的数字都比1大,这时候下标index指向的下标还是1。
3 1 8 6 2 5 9 4 7
!
.............继续上面的步骤把循环走完,一直走到下标从8开始往后面依次遍历的数字进行比较的时候,发现还是没有数字比index 1指向的数字1小,那就退出了循环,开始进行数字的交换。
1 3 8 6 2 5 9 4 7 第一趟排序的结果
把第一个数和下标为index的数进行交换,这样一来就相当于把最小的数找到了并且放在第一位,接下来我们只需要对后面的8个数进行排序即可。
第二趟排序:定义一个下标 int index = 1; 即先指向第二个数3,感叹号代表下标。
1 3 8 6 2 5 9 4 7
!
(1)把index指向的数和从下标为2开始的往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。即3>2, 2的下标是4,所以 index = 4; 这时候下标index指向下标就是4。
1 3 8 6 2 5 9 4 7
!
(2)把index指向的数和从下标为3开始的往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。后面的数字都比2大,这时候下标index指向的下标还是4。
1 3 8 6 2 5 9 4 7
!
.............继续上面的步骤把循环走完,一直走到下标从8开始往后面依次遍历的数字进行比较的时候,发现还是没有数字比index 4指向的数字2小,那就退出了循环,开始进行数字的交换。
1 2 8 6 3 5 9 4 7 第二趟排序的结果
第三趟排序:定义一个下标 int index = 2; 即先指向第三个数8,感叹号代表下标。
1 2 8 6 3 5 9 4 7
!
(1)把index指向的数和从下标为3开始的往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。即8>6, 6的下标是3,所以 index = 3; 这时候下标index指向下标就是3。
1 2 8 6 3 5 9 4 7
!
(2)把index指向的数和从下标为4开始的往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。即6>3, 3的下标是4,所以 index = 4; 这时候下标index指向下标就是4。
1 2 8 6 3 5 9 4 7
!
(3)把index指向的数和从下标为5开始的往后面依次遍历的数字进行比较,如果有数字比index指向的数小,则把那个数的下标赋值给index。后面的数字都比3大,这时候下标index指向的下标还是4。
.............继续上面的步骤把循环走完,一直走到下标从8开始往后面依次遍历的数字进行比较的时候,发现还是没有数字比index 4指向的数字3小,那就退出了循环,开始进行数字的交换。
1 2 3 6 8 5 9 4 7 第三趟排序结果
根据这样的流程一直循环下去,最终就会实现这样的排序结果,后面的流程我就不继续写下去了。
直接上代码:
public static void selectSort(int[] array){
for(int i = 0;i < array.length-1; i++){
int index = i;
for(int j = i+1;j < array.length; j++){
if(array[index] > array[j]){
index = j; //说明找到了比Index小的数的下标
}
}
if(index != i){ //如果最小的数位置发生了变化就交换
int temp = array[index];
array[index] = array[i];
array[i] = temp;
}
}
}
选择排序应用场景:也是应用在数据量小的情况下。
网友评论