经典算法——直接选择排序

风会熄灭蜡烛，却能使火越烧越旺。你要成为火，渴望得到风的吹拂???

文章目录

• 1. 什么是算法？
• 2. 算法的效率
• 3. 选择排序
  • 3.1 代码实现
  • 3.2 算法效率

1. 什么是算法？

任何被明确定义的计算过程都可以称作 算法 ，它将某个值或一组值作为输入，并产生某个值或一组值作为输出。所以 算法可以被称作将输入转为输出的一系列的计算步骤 。

说白了就是步骤明确的解决问题的方法。由于是在计算机中执行，所以通常先用伪代码来表示，清晰的表达出思路和步骤，这样在真正执行的时候，就可以使用不同的语言来实现出相同的效果。

2. 算法的效率

算法效率是指算法 执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。在现在的计算机硬件环境中，比较少需要考虑这个问题了，特别是pc机的编程， 内存空间 越来越大，所以被考虑得也越来越少，不过一个好的程序员，都应该对自己的程序有要求，每一个for比别人少一次判断1000个for就能够少掉很多的运行时间。所以能够理解，能够大概的去运用"效率度量"还是有很大意义的。我们一般通过两个方面来衡量一个算法的效率

• 时间复杂度?

算法的时间复杂度是一个函数，它定性描述一个算法的运行时间。 一个算法的执行所需要的时间，从理论上来说是算不出来的，必须通过上机测试才能得到，但这并不是说我们对于每个算法都要上机测试，我们只需要知道哪个算法所花的时间多，哪个算法所花的时间少就行。 一个算法花费的时间与算法中的语句执行次数成正比，算法中的语句执行次数越多，它花费的时间就越多。一个算法中的语句执行次数成为语句频度或时间频度，记为T(n)，n为问题的规模。

• 空间复杂度?

空间复杂度是指执行这个算法所需要的内存空间。 空间复杂度需要考虑在运行过程中为 局部变量分配的存储空间的大小 ，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。 空间复杂度也就是对一个算法在运行过程中 临时占用存储空间大小 的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2)，空间复杂度是O(1) 。

3. 选择排序

选择排序的核心思想是：每一趟从无序区中选出关键字最小的元素，按顺序放在有序区的最后（生成新的有序区，无序区元素个数减1），直到全部排完为止。

• 直接选择排序

也称简单选择排序，过程是每次从无序区中找出最小的元素，按顺序放在有序区的最后（刚开始有序区的元素为零）

• 输入

n个数的序列，通常存放在数组中，可以是任何顺序。

• 输出

输入序列的一个新排列的序列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序排列）。

• 算法流程

如果使用直接选择排序对元素个数为n的序列进行排序，需要进行n-1趟排序。

以数组[91,6,96,69,61]为例:

1️⃣第1次，找出元素最小的数字6，与第一个元素91交换得到=》[6,91,96,69,61] 2️⃣第2次，找出元素最小的数字61，与第二个元素交换得到=》[6,61,96,69,91] 3️⃣第3次，找出元素最小的数字69，与第三个元素交换得到=》[6,61,69,96,91] 4️⃣第4次，找出元素最小的数字91，与第四个元素交换得到=》[6,61,69,91,96]

3.1 代码实现

Java代码☕️☕️☕️

@Test
public void main() {
    // input data
    int[] a = {91,6,96,69,61};
    // 调用选择排序
    sort(a);
    // 查看排序结果
    for (int data : a) {
        System.out.print(data + "\t");
    }
}

public void sort(int[] a) {
    // 外层循环用于控制循环的趟数
    for (int i = 0; i < a.length - 1; i++) {
        int k = i;
        // 内层循环的作用是在无序区中选出最小的元素并记录
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[k]) {
                k = j;
            }
        }
        // 如果本轮选出的最小元素没有在对应的位置上则交换
        if (k != i) {
            int tmp = a[i];
            a[i] = a[k];
            a[k] = tmp;
        }
    }
}

输入数据：91，6，96，69，61 输出：6，61，69，91，96

3.2 算法效率

• 时间复杂度

最好的情况是数据本来就有序，复杂度为O(n)；最差的情况是O(n²)，属于不稳定算法

• 空间复杂度

算法在执行过程中只需要定义的几个临时变量，所以空间复杂度为常数级：O(1)