算法之排序-选择排序

文章目录
  1. 1. 算法描述
  2. 2. 命题A
  3. 3. 特点
  4. 4. 代码

算法描述

  1. 首先，找到数组中最小的元素
  2. 其次，将它和数组的第一个元素交换位置（如果第一个是最小的，就和自己交换）
  3. 再次，在剩下的元素中找到最小的元素，将它与第二个元素交换位置。
  4. 如此往复，直到将整个数组排序

命题A

对于长度为N的数组，选择排序需要大约N²/2次比较和N次交换

特点

  1. 运行时间和输入无关。

    为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点，一个已经有序的数组或者主键全部相等的数组和一个元素随机排列的数组所用的排序时间一样长！

  2. 数据移动是最少的。

    每次交换都会改变两个元素的位置的值，因此选择排序用了N次交换——交换次数和数组的大小是线性关系。其他任何算法都不具备这个特征（大部分的增长数量级都是线性对数或者平方级别）

代码

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
public class Selection {
    public static void sort(Comparable[] a) {
        //将a按升序排列
        int N = a.length;//数组长度
        for (int i = 0; i < N; i++) {
            //将a[i]和a[n+1...N]最小的元素交换
            int min = i;//最小元素的索引
            for (int j = i + 1; j < N; j++) {
                if (less(a[j],a[min])) {
                    min = j;
                }
            }

            exchange(a,i,min);
        }
    }

    public static void main(String[] args) {
        Character[] a = {'S','O','R','T','E','X','A','M','P','L','E'};
        sort(a);
        if (isSorted(a)) {
            show(a);
        }
    }
    //A E E L M O P R S T X 
}

其中less方法和exchange方法在工具类中，如下：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class SortUtils {

    /**
     * 比较两个对象大小
     *
     * @param v
     * @param w
     * @return
     */
    static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    /**
     * 交换数组元素位置
     *
     * @param a
     * @param i
     * @param j
     */
    static void exchange(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 打印数组元素
     *
     * @param a
     */
    static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    /**
     * 判断数组元素是否有序
     * @param a
     * @return
     */
    static boolean isSorted(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }
}