常见数据结构与算法-选择排序

　　　　　　　　　常见数据结构与算法-选择排序

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　作者：尹正杰

一.选择排序概述

1>.选择排序总结

　　选择排序
　　　　属于选择排序
　　　　两两比较大小，找出极值（极大值或极小值）被放置在固定的位置，这个固定位置一般指的是某一端
　　　　结果分为升序和降序排列

　　降序
　　　　n个数从左至右，索引从0开始到n-1，两两依次比较，记录大值索引，此轮所有数比较完毕，将大数和索引0数交换，如果大数就是索引1，不交换。第二轮，从1开始比较，找到最大值，将它和索引1位置交换，如果它就在索引1位置则不交换。依次类推，每次左边都会固定下一个大数。

　　升序
　　　　和降序相反

　　选择排序总结：
　　　　简单选择排序需要数据一轮轮比较，并在每一轮中发现极值
　　　　没有办法知道当前轮是否已经达到排序要求，但是可以知道极值是否在目标索引位置上
　　　　遍历次数1,...,n-1之和n(n-1)/2
　　　　时间复杂度O(n2)
　　　　减少了交换次数，提高了效率，性能略好于冒泡法

2>.选择排序原理

初始值：[1 9 8 5 6 7 4 3 2]　　　　　　　　

第一趟：[9 1 8 5 6 7 4 3 2]　　　　#选择出此轮最大数9，和索引0数交换选择

第二趟：[9 8 1 5 6 7 4 3 2]　　　　#选择出次轮最大数8，和索引1数交换，下面的工作方式以此类推。

第三趟：[9 8 7 5 6 1 4 3 2]

第四趟：[9 8 7 6 5 1 4 3 2]

第五趟：[9 8 7 6 5 1 4 3 2]

第六趟：[9 8 7 6 5 4 1 3 2]

第七趟：[9 8 7 6 5 4 3 1 2]

第八趟：[9 8 7 6 5 4 3 2 1]

二.使用编程语言实现选择排序

1>.Python实现版本

　　博主推荐阅读:
　　　　https://www.cnblogs.com/yinzhengjie/p/10958697.html

2>.Java实现版本

/**
 *    选择排序
 *     @author 尹正杰
 */
public class ArrayDemo3 {
    public static void main(String[] args) {
        int[] arr = {1,20,3,80,5,200,175,10};
        System.out.println("排序前:"); 
        printArray(arr);
        selectSort(arr);
        System.out.println("排序后:");
        printArray(arr);
    }
    
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1 ; i++) {
            //每一次比较,都是索引i和下一个元素(i + 1)进行比较
            for (int j = i + 1; j < arr.length; j++) {
                //当前一个元素比另一个元素大的时候,进行位置互换
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
    
    public static void printArray(int[] arr) {
        System.out.print("	");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "	");
        }
        System.out.println();
    }
}