选择排序

程序员文章站 2022-03-01 15:12:02

...

算法思想

找到数组中第i小的元素并将该元素与当前i位置上的元素进行交换

Java实现

import java.util.Arrays;

public class Selection {
    /* 选择排序,升序 */
    public static void sort(Comparable[] a) {
        for (int i = 0, len = a.length; i < len; i++) {
            // 寻找第i小元素的下标
            int min = i;
            for (int j = i + 1; j < len; j++) {
                if (a[j].compareTo(a[min]) < 0) {
                    min = j;
                }
            }
            // 把第i小的元素放在数组下标为i的位置
            // 交换元素的代码写在内层循环之外
            exchange(a, i, min);
        }
    }

    /* 交换指定下标元素的位置 */
    private static void exchange(Comparable[] a, int i, int j) {
        Comparable tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    /* 测试 */
    public static void main(String[] args) {
        Integer[] a = new Integer[] { 9, 2, 3, 4, 1, 1, 7, 3, 4, 16, 22, 10 };
        System.out.println(Arrays.toString(a));
        Selection.sort(a);
        System.out.println(Arrays.toString(a));
        System.out.println("end");
    }
}