读书笔记-《数据结构与算法》-摘要3[选择排序]

选择排序

核心：不断地选择剩余元素中的最小者。

1. 找到数组中最小元素并将其和数组第一个元素交换位置。
2. 在剩下的元素中找到最小元素并将其与数组第二个元素交换，直至整个数组排序。

性质：

• 比较次数=(N-1)+(N-2)+(N-3)+…+2+1~N^2/2
• 交换次数=N
• 运行时间与输入无关
• 数据移动最少

public class SelectioSort {public static void main(String[] args) {int unsortedArray[] = new int[]{8, 5, 2, 6, 9, 3, 1, 4, 0, 7};selectionSort(unsortedArray);System.out.println("After sort: ");for (int item : unsortedArray) {System.out.print(item + " ");}}public static void selectionSort(int[] array) {int len = array.length;for (int i = 0; i < len; i++) {for (int item : array) {System.out.print(item + " ");}System.out.println();int min_index = i;// 将最小值的下标找出来for (int j = i + 1; j < len; j++) {if (array[j] < array[min_index]) {min_index = j;}}int temp = array[min_index];array[min_index] = array[i];array[i] = temp;}}
}

输出：

8 5 2 6 9 3 1 4 0 7 
0 5 2 6 9 3 1 4 8 7 
0 1 2 6 9 3 5 4 8 7 
0 1 2 6 9 3 5 4 8 7 
0 1 2 3 9 6 5 4 8 7 
0 1 2 3 4 6 5 9 8 7 
0 1 2 3 4 5 6 9 8 7 
0 1 2 3 4 5 6 9 8 7 
0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 
After sort: 
0 1 2 3 4 5 6 7 8 9