简单选择排序(Select Sort),java版

转载：

 

http://blog.chenlb.com/2008/12/select-sort-for-java.html

简单选择排序(Select Sort),java版。

发表于：2008年12月28日 | 分类：算法 | 标签： sort | views(661)

版权信息: 可以任意转载, 转载时请务必以超链接形式标明文章原文出处, 即下面的声明.

 

原文出处：http://blog.chenlb.com/2008/12/select-sort-for-java.html

常用的简单排序方法中，除插入排序、冒泡排序，还有简单选择排序（有时候也直接说成是选排序）。

简单选择排序原理：从无序区域里选择最小（或最大）的添加到有序区里。一开始所有的数据都是在无序区里，排好一个，无序区个数就少一个。
时间复杂度：平均O(n²)，最坏情况O(n²)。

示例代码：

package com.chenlb.sort;

import java.util.Arrays;

public class SelectSort {

    public static int[] sort(int[] datas) {
        for(int i=0; i<datas.length-1; i++) {
            int minIndex = i;
            int min = datas[i];
            for(int j=i+1; j< datas.length; j++) {//在后面, 找最小的.
                if(datas[j] < min) {
                    minIndex = j;
                    min = datas[j];
                }
            }
            if(minIndex != i) {
                SortUtil.swap(datas, i, minIndex);
            }
        }
        return datas;
    }

    public static void main(String[] args) {
        int[] datas = {5,1,3,4,9,2,7,6,5};
        sort(datas);
        System.out.println(Arrays.toString(datas));

        datas = SortUtil.randomDates(10);
        sort(datas);
        System.out.println(Arrays.toString(datas));
    }

}

运行结果：

[1, 2, 3, 4, 5, 5, 6, 7, 9]
[67, 81, 122, 394, 452, 509, 533, 536, 608, 861]