选择排序原理证明及Java实现

简单介绍

选择排序是较为简单的排序算法之一，它的原理就是每次把剩余元素中最小的那个挑选出来放在这些剩余元素的首位置，举个栗子：

长度为5的一个数组：3，0，-5，1，8

第一次选择后： -5，0，3，1，8

第二次选择后： -5，0，3，1，8

第三次选择后： -5，0，1，3，8

第四次选择后： -5，0，1，3，8

最后一次选择： -5，0，1，3，8

注：标记红色字体的为发生交换的元素，下划线标记的为剩余元素

简单证明

设数组a共有N个元素，对其进行选择排序：

第一次选择将最小元素放在的位置，即此刻最小

第二次选择将上一步操作后的剩余元素中的最小元素放在 的位置，因此必然小于等于，由于此刻的是从上一步操作后的剩余元素中选出的，必然也大于等于

同理，共经过N次选择后：

Java代码实现

public class SelectionSort {
    public static void sort(Comparable[] a){         //排序操作
        int min,i,j;
        for (i=0;i<=a.length-1;i++){    //从头到尾选择length次
            min=i;                      
            for (j=i+1;j<=a.length-1;j++){
                if (isLess(a[j],a[min]))
                {
                    min=j;
                }                          //采用打擂原理获取最小值的索引
            }
            exchange(a,i,min);
        }
    }
    public static boolean isLess(Comparable x,Comparable y){
        return x.compareTo(y)<0;
    }  //判断x是否小于y
    public static void exchange(Comparable[] a,int i,int j){   //交换数组a中索引i和j所指的元素的值
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public static boolean isOrdered(Comparable[] a){    //判断数组是否有序
        for (int i=0;i<=a.length-2;i++){
            if (a[i].compareTo(a[i+1])<=0)
            {
                continue;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
    public static void show(Comparable[] a){    //打印数组
        for (int i=0;i<=a.length-2;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println(a[a.length-1]);
    }
}

import java.util.Scanner;
import java.util.Random;

public class SelectionSortTest {
    public static void main(String[] args){
        Scanner sb=new Scanner(System.in);
        int length;
        int choice;
        System.out.println("请输入数组元素的个数：");
        length=sb.nextInt();
        Integer[] a=new Integer[length];        //任意实现Comparable接口的数组皆可为参数，这里以Integer型数组为例
        System.out.println("请选择创建数组的方式：1.手动  2.自动");
        choice=sb.nextInt();
        if (choice==1)
        {
            for (int i=0;i<=a.length-1;i++){
                a[i]=new Integer(sb.nextInt());
            }
        }
        else
        {
            Random r=new Random();
            for (int i=0;i<=a.length-1;i++){
                a[i]=new Integer(r.nextInt(length*length));   //随机生成[0,length*length)范围内一个整数
            }                                                        //并初始化一个Integer对象
        }
        SelectionSort.sort(a);
        System.out.println("数组是否有序："+SelectionSort.isOrdered(a));
        System.out.println("是否打印数组：1.是  2.否");
        choice=sb.nextInt();
        if (choice==1)
        {
            SelectionSort.show(a);
        }
        sb.close();
    }
}

请输入数组元素的个数：
30
请选择创建数组的方式：1.手动  2.自动
2
数组是否有序：true
是否打印数组：1.是  2.否
1
19 23 47 68 72 99 130 206 248 326 326 338 338 365 403 417 461 466 517 541 555 593 625 626 704 806 833 849 871 873

Process finished with exit code 0

效率分析

通过查看代码我们可以精确地得到，0到N-1（length-1）的任意i都会进行一次交换和N-1-i次比较，因此共有N次交换以及（N-1)+(N-2)+...+2+1=N(N-1)/2次比较。算法的时间复杂度为。

用的IDE是IntelliJ IDEA