选择排序

1.简介：

选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。它的最坏、最好、平均时间复杂度均为为O(n²)，选择排序是不稳定的排序方法。

2.算法原理：

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 重复第二步，直到所有元素均排序完毕。

结合动态图理解一下：

（图片来源：十大经典排序算法（动图演示））

3.代码实现：

选择排序大体思路就是一次循环找到最小或最大的，然后放在最前或最后面。

我是在循环中找到较小的数，记录其下标，等一次循环结束后再交换。

还有一种思路是找到较小的数两数交换，一次循环结束时，可能交换次数不止是一次，这种思路有点冒泡的感觉，并且其时间复杂度的系数较高。

    public static void xuanZe(int[] a){
        for(int i = 0;i < a.length-1;i++) {
            int temp=0,min = i;
            for(int j = a.length-1;j > i;j--) {
                if(a[j] < a[min]){
                    min = j;
                }
            }
            temp = a[min];
            a[min] = a[i];
            a[i] = temp;
        }
    }

测试一波：

package sort;

/**
 * @author yzh
 * @date 2019-07-15 17:12
 */
public class XuanZe {
    public static void xuanZe(int[] a){
        for(int i = 0;i < a.length-1;i++) {
            int temp=0,min = i;
            for(int j = a.length-1;j > i;j--) {
                if(a[j] < a[min]){
                    min = j;
                }
            }
            temp = a[min];
            a[min] = a[i];
            a[i] = temp;
        }
    }
    public static void main(String[] args) {
        int[] a = {4,97,64,3,19,-7,78,0,-90};
        xuanZe(a);
        for(int i = 0;i < a.length;i++){
            System.out.println(a[i]);
        }
    }
}

测试结果：

4.优缺点：

• 优点：移动数据的次数已知（n-1 次）；
• 缺点：比较的次数多，效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。