选择排序算法的实现和优化

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

初识选择排序：

算法思想[以升序为例]：

第一趟选择排序时从第一个记录开始通过n-1次关键字的比较从第n个记录中选出关键字最小的记录并和第一个记录进行交换

第二趟选择排序时从第二个记录开始通过n-2次关键字的比较从第n-1个记录中选出关键字最小的记录并和第二个记录进行交换

…

第i趟选择排序时从第i个记录开始通过n-i次关键字的比较从n-i+1个记录中选择出关键字最小的记录并和第i个记录进行交换

反复进行上述步骤经过n-1趟选择排序将把n-1个记录排到位最后剩下的那个元素同样已经就位所以共需进行n-1趟选择排序

文字描述[以升序为例]：

将数组分为两个子集排序的和未排序的每一轮从未排序的子集中选出最小的元素放入排序子集重复上述步骤直至整个数组有序

算法实现：

代码如下：

package bin_find;
import java.util.Arrays;

public class selectionSort {
    public static void main(String[] args) {
        int[] a={5,3,7,2,1,9,8,4};
        selection(a);
    }

    private static void selection(int[] a){
        for(int i=0;i<a.length-1;i++) {//n个元素参与排序需要进行n-1次
            for (int j = i + 1; j < a.length; j++) {//每轮i+1---a.length个元素之间相比较
                if (a[i] > a[j]) {//前者大于后者则进行交换
                    swap(a, i, j);
                }
            }
            System.out.println("第"+(i+1)+"轮选择排序的结果"+Arrays.toString(a));
        }
    }
    public static void swap(int arr[],int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }
}

输出如下：

第1轮选择排序的结果[1, 5, 7, 3, 2, 9, 8, 4]
第2轮选择排序的结果[1, 2, 7, 5, 3, 9, 8, 4]
第3轮选择排序的结果[1, 2, 3, 7, 5, 9, 8, 4]
第4轮选择排序的结果[1, 2, 3, 4, 7, 9, 8, 5]
第5轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7]
第6轮选择排序的结果[1, 2, 3, 4, 5, 7, 9, 8]
第7轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]

优化后的算法实现：

优化思路

减少交换次数每一轮可以先找到最小的索引再每轮最后再交换元素

代码如下：

package bin_find;
import java.util.Arrays;

public class selectionSort {
    public static void main(String[] args) {
        int[] a={5,3,7,2,1,9,8,4};
        selection(a);
    }

    private static void selection(int[] a){
        //代表每轮选择最小元素要交换到的目标索引
        for(int i=0;i<a.length-1;i++) {

            int s = i;//代表最小元素的索引[这里是升序]---第一次最小元素的索引为1第二次最小元素的索引为2.....

            //从当前最小元素的下一位元素开始直到最后一个元素---完成一次选择排序
            for (int j = s + 1; j < a.length; j++) {
                //[这里是升序]前者大于后者则将更小数的索引值赋值给s,因为变量s本身代表的含义为最小元素的索引
                if (a[s] > a[j]) {
                    s = j;
                }
            }
            if (s != i) {//若不是同一个数则进行交换
                swap(a, s, i);
            }
            System.out.println("第"+(i+1)+"轮选择排序的结果"+Arrays.toString(a));
        }
    }
    public static void swap(int arr[],int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }
}

输出：

第1轮选择排序的结果[1, 3, 7, 2, 5, 9, 8, 4]
第2轮选择排序的结果[1, 2, 7, 3, 5, 9, 8, 4]
第3轮选择排序的结果[1, 2, 3, 7, 5, 9, 8, 4]
第4轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7]
第5轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7]
第6轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]
第7轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]