image

愚昧者怨天尤人，无能者长吁短叹，儒弱者颓然放弃。

选择排序就是这么容易

welcome rodert一选择排序（Selection Sort）

科班的大多在学校时都学过数据结构和算法，不论是做算法还是做业务，排序都是经常要打交道的，还记得选择排序吗？前面写了冒泡排序，一起来选择排序看看

一介绍

image

【百度百科】：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法

实质：对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。

时间复杂度： O（n²）

一实现

算法描述（从小到大排序）：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

动态图演示：

image

选择排序流程图图片来源百度

图片.png

Java代码实现
、、、
@Test
public void selectionSort(){
int [] arr = {5, 0, 7, 1, 2};//新建数组

    // 总共要经过 N-1 轮比较
    for (int i = 0; i < arr.length - 1; i++) {
        int  min = i;

        // 每轮需要比较的次数 N-i
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                // 记录目前能找到的最小值元素的下标
                min = j;
            }
        }

        // 将找到的最小值和i位置所在的值进行交换
        if (min != i) {
            int tmp = arr[min]; //临时变量
            arr[min] = arr[i];
            arr[i] = tmp;
        }
    }

    // 返回结果
    for (int i:arr) {
        System.out.println(i);
    }
}

、、、

image

image

—END—rodert

更多文章后面会持续分享，有特别需要可以提前留言。