数据结构-选择排序法

佚名 4年前 (2020-04-12) 算法 808人围观抢沙发百度已收录

　　选择排序法可使用两种方式排序，一为在所有的数据中，当由大到小排序，则将最大值放入第一个位置；若由小至大排序时，则将最大值放入位置末端。

　　例如当 N 个数据需要由小到大排序时，首先以第一个位置的数据，依次向 2、3、4......N 个位置的数据做比较。如果数据小于或者等于其中一个位置，则两个位置的数据不变；若大于其中一个位置，则两个位置的数据互换。互换后的第一个位置新数据，继续找下一个位置数据作比较，直到位置最末端，此时第一个位置的数据即为此排序数列的最小值。接下来选择第二个位置数据，依次向 3、4、5......N 个位置的数据作比较，将剩余排序的最小值放入第二个位置。依循此方法直到 (N-1) 个位置最小值找到后，就完成选择排序法由小至大的排序。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

演算过程

选择法分析

无论是最坏情况，最佳情况还是平均情况都需要找到最小值（最大值），因此其比较次数为 (n-1)+(n-2)+(n-3)+...+3+2+1=n(n-1)/2 次；时间复杂度为 O(n^2)。
由于选择排序是以最小或最大值直接与最前方未排序的键值交换，数据排列顺序很有可能被改变，故不是稳定排序法。
只需一个额外的空间，所以空间复杂度为最佳。
此排序法适用于数据量小或有部分数据已经过排序的情况。

example1

/**
 * 选择排序法
 *
 */
public class SelectionSort {

    public static void main(String[] args) {
        int data[] = new int[] {9, 7, 5, 3, 4, 6};
        System.out.print("原始数据：");
        showData(data);
        select(data);
        System.out.print("排序后的数据：");
        showData(data);
    }
    
    private static void select(int data[]) {
        int i, j, tmp;
        for (i = 0; i < data.length - 1; i++) {
            for (j = i + 1; j < data.length; j++) {
                if (data[i] > data[j]) {
                    tmp = data[i];
                    data[i] = data[j];
                    data[j] = tmp;
                }
            }
            showData(data);
        }
    }
    
    private static void showData(int data[]) {
        for (int i = 0; i < data.length; i++) {
            System.out.printf("[%d]", data[i]);
        }
        System.out.printf("%n");
    }

}