选择排序 介绍与java实现

排序是程序编码避不开的一个话题。

一组无规则有序数据，排序的方式有很多中，其中最笨的方法就是穷举，也就是全排列排序。n个数字的有n！种不同的排列方法，如果50个无规则数据进行全排列进行排序，及时一台高性能计算机，每秒计算1万亿 （ 10^12 ） 次，也需要超过 10^20 年。

那么选择排序又能快多少呢？

选择排序需要依次从剩余无规则数据组合中取出最大（小）的数值，放置到新的队列中的即为有序的数列了。计算次数要比全排列排序少得多。

50个数字排序，50^2 = 2500 ，对于一台高性能计算机而言，瞬间就执行完了。

代码实现

public class SelectSorted {

    
    public List select(List unSorted, boolean isReverse) {
        List sorted = new ArrayList<>();
        BigDecimal current = null;
        int currentIndex = 0;
        while (!ObjectUtils.isEmpty(unSorted)) {
            for (int i = 0; i < unSorted.size(); i++) {
                if (ObjectUtils.isEmpty(current)) {
                    current = unSorted.get(i);
                } else {
                    if (!isReverse) {
                        if (current.compareTo(unSorted.get(i)) <= 0) {
                            continue;
                        }
                    }else {
                        if (current.compareTo(unSorted.get(i)) >= 0) {
                            continue;
                        }
                    }
                    current = unSorted.get(i);
                    currentIndex = i;
                }

            }
            sorted.add(current);
            unSorted.remove(currentIndex);
            current = null;
            currentIndex = 0;
        }
        return sorted;
    }

    public static void main(String[] args) {
        List list = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            list.add(BigDecimal.valueOf(new Random().nextInt(1000)));
        }
        System.out.println("before sorting:n" + list);
        System.out.println("after sorting:n" + new SelectSorted().select(list,Boolean.TRUE));
    }
}

在main测试方法中，我们随机生成100个1000以内的正整数，通过select方法进行选择排序，第二个参数可以控制正序还是倒序。这里用的是BigDecimal类型，其他数值类型也是一样的。通过泛型，我们可以把这个选择排序的方法变得更加通用。

    public static  List select(List unSorted, boolean isReverse) {
        List sorted = new ArrayList<>();
        T current = null;
        int currentIndex = 0;
        while (!ObjectUtils.isEmpty(unSorted)) {
            for (int i = 0; i < unSorted.size(); i++) {
                if (ObjectUtils.isEmpty(current)) {
                    current = unSorted.get(i);
                } else {
                    if (!isReverse) {
                        if (new BigDecimal(current.toString()).compareTo(new BigDecimal(unSorted.get(i).toString())) <= 0) {
                            continue;
                        }
                    }else {
                        if (new BigDecimal(current.toString()).compareTo(new BigDecimal(unSorted.get(i).toString())) >= 0) {
                            continue;
                        }
                    }
                    current = unSorted.get(i);
                    currentIndex = i;
                }

            }
            sorted.add(current);
            unSorted.remove(currentIndex);
            current = null;
            currentIndex = 0;
        }
        return sorted;
    }

执行一下main方法，这里采用倒序排序，结果如下（部分展示）：