1. 前言
选择排序的基本思想是:首先在为排序的数列中找到最小/最大的元素,然后将其存放到数列的起始位置;接着再从剩余为排序的元素中继续寻找最小/最大元素,放到已排序序列的末尾,以此类推,直到所有元素均排序完成
2. 实现
下面以数列:{20,40,30,10,60,50}为例,演示它的排序过程:
3. 时间复杂度和稳定性
- 时间复杂度:O(N2);假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次呢? N-1!因此,选择排序的时间复杂度是O(N2)。
- 稳定性:用数组实现的选择排序是不稳定的,用链表实现的选择排序是稳定的,一般默认是数组实现,所以是不稳定的
4. 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
public class SelectSort {
public static void selectSort(int[] a){ int i; int j; int min; for(i = 0; i < a.length; i++){ min = i; for(j = i+1; j < a.length; j++){ if (a[j] < a[min]){ min = j; } } if (min != i){ int temp = a[i]; a[i] = a[min]; a[min] = temp; } } }
public static void main(String[] args) { int[] a = {20,40,30,10,60,50}; selectSort(a); for (int i = 0; i < a.length; i++) { System.out.printf("%d ", a[i]); } } }
|