选择排序 #
1. 选择排序算法思想 #
选择排序(Selection Sort)基本思想:
对
n
个元素,进行n-1
趟排序,第i (i = 1, 2, …)
趟排序时从数组下标为i - 1
的元素M开始遍历,直至数组最后一个元素,将其中值最小的元素与元素M进行交换。
简单来说,「选择排序法」关键在于每次遍历都选出一个最大/最小值,最终使整个数组有序。
2. 选择排序算法步骤 #
-
第
1
趟排序,从数组中下标为0
的元素开始,依次向后遍历整个数组;-
假定一个变量
min
,表示第1
趟排序中,最小值的下标,初始值设置为0
; -
依次向后遍历,同时比较每一个元素与
arr[min]
的大小,如果某个元素值比arr[min]
小,则将该元素的下标赋值给min
。 -
遍历结束后,将数组中下标为
0
和下标为min
的元素交换位置;
-
-
第
2
趟排序,从数组中下标为1
的元素开始,依次向后遍历整个数组;- 假定一个变量
min
,表示第2
趟排序中,最小值的下标,初始值设置为1
; - 依次向后遍历,同时比较每一个元素与
arr[min]
的大小,如果某个元素值比arr[min]
小,则将该元素的下标赋值给min
。 - 遍历结束后,将数组中下标为
1
和下标为min
的元素交换位置;
- 假定一个变量
-
依次类推,将上述过程进行
n-1
次,结束。
3. 选择排序动画演示 #
4. 选择排序代码实现 #
public static void selectSort(int[] arr){
if(null==arr || arr.length==0){
return;
}
for(int i=0;i<arr.length-1;i++){
int min = i;
for(int j=i+1;j<arr.length;j++){
if(arr[min] > arr[j]){
//记录本趟排序最小值的下标
min = j;
}
}
//交换
if(i != min){
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
}