几种经典的排序算法——选择排序

选择排序

原理：每次找出待排序的序列中最小的元素跟序列的第一个元素进行交换。

思路：

1. 从待排序中，找到关键字最小的元素。
2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换。
3. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

如下图示例： 排序[3,2,5,4,1]

1. 找到最小的元素为1，交换值第一个位置，结果为[1,2,5,4,3]
2. 此时待排序的序列为[2,5,4,3],然后重复上述工作，最小为2，不用移动，结果为[1,2,5,4,3]
3. 重复上述工作，第三轮为[1,2,3,4,5];
4. 经过N轮排序，完成排序[1,2,3,4,5]

代码如下：

核心代码：

    public static void selectSort(int[] target) {

        if (target == null || target.length < 2) {
            return;
        }

        // 这个for循环是决定要交换多少轮
        for (int i = 0; i < target.length; i++) {
            int min = i;
            // 这个for循环是找出最小的数过程中每一轮需要比较的次数
            for (int j = i+1; j < target.length; j++) {
                if(target [j] < target[min]) {
                    min = j; // 找出当前数组中最小数的index
                }
            }
            if (min != i) {
                int temp = target[i];
                target[i] = target[min];
                target [min] = temp;

            }
            System.out.println("第"+(i)+"轮排序后的结果为:");
            display(target);
        }
    }

完整测试代码：

public class Main {

    public static void main(String[] args) {
        int[] target = {3,2,5,4,1};
        System.out.println("未排序数组顺序为：");
        display(target);
        System.out.println("-----------------------");
        selectSort(target);
        System.out.println("-----------------------");
        System.out.print("最终的排序结果:");
        display(target);
    }

    public static void selectSort(int[] target) {

        if (target == null || target.length < 2) {
            return;
        }

        // 这个for循环是决定要交换多少轮
        for (int i = 0; i < target.length; i++) {
            int min = i;
            // 这个for循环是找出最小的数过程中每一轮需要比较的次数
            for (int j = i+1; j < target.length; j++) {
                if(target [j] < target[min]) {
                    min = j; // 找出当前数组中最小数的index
                }
            }
            if (min != i) {
                int temp = target[i];
                target[i] = target[min];
                target [min] = temp;

            }
            System.out.println("第"+(i)+"轮排序后的结果为:");
            display(target);
        }
    }

    //显示数组
    public static void display(int[] array){
        for(int i = 0 ; i < array.length ; i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}

最终结果：

未排序数组顺序为：
3 2 5 4 1 
-----------------------
第0轮排序后的结果为:
1 2 5 4 3 
第1轮排序后的结果为:
1 2 5 4 3 
第2轮排序后的结果为:
1 2 3 4 5 
第3轮排序后的结果为:
1 2 3 4 5 
第4轮排序后的结果为:
1 2 3 4 5 
-----------------------
最终的排序结果:1 2 3 4 5 

性能分析：

选择排序总的平均时间复杂度为：O(n*n)。

选择排序和冒泡排序执行了相同次数的比较：N*（N-1）/2，但是至多只进行了N次交换。

• 当 N 值很大时，比较次数是主要的，所以和冒泡排序一样，用大O表示是O(N2) 时间级别。但是由于选择排序交换的次数少，所以选择排序无疑是比冒泡排序快的。
• 当 N 值较小时，如果交换时间比选择时间大的多，那么选择排序是相当快的。