关于程序员:每日一算选择排序算法

大家好，我是易安！

明天咱们开始每日一算的篇章，明天带来的是抉择算法。

抉择排序 是一种简略而高效的排序算法，它通过从列表的未排序局部中反复抉择最小（或最大）元素并将其挪动到列表的已排序局部来工作。该算法重复从列表的未排序局部中抉择最小（或最大）的元素，并将其与未排序局部的第一个元素替换。对列表中残余的未排序局部反复此过程，直到整个列表排序结束。抉择排序的一种变体称为“双向选择排序”，它通过在最小元素和最大元素之间交替遍历元素列表，这种形式在某些状况下能够更快。

抉择排序算法

该算法在给定数组中保护两个子数组。

曾经排序的子数组。

残余的子数组未排序。

在抉择排序的每次迭代中，从未排序的子数组中选取最小元素（思考升序）并将其挪动到已排序子数组的结尾。

每次迭代后，已排序的子数组大小减少一，未排序的子数组大小缩小一。

在 N（数组的大小）次迭代之后，咱们将失去一个排序的数组。

让咱们以上面的数组为例：arr[] = {64, 25, 12, 22, 11}

第一步：

对于排序数组中的第一个地位，整个数组从索引 0 到 4 顺次遍历。以后寄存 64的第一个地位，遍历整个数组后显然 11 是最低值。

64 25 12 22 11

因而，将 64 替换为 11。通过一次迭代后，恰好是数组中最小值的 11 往往会呈现在排序列表的第一个地位。

11 25 12 22 64

第二步：

对于存在 25 的第二个地位，再次按程序遍历数组的其余部分。

11 25 12 22 64

遍历后发现 12 是数组中倒数第二的值，应该呈现在数组的第二位，因而替换这些值。

11 12 25 22 64

第三步：

当初，对于第三位，再次出现 25 的 中央遍历数组的其余部分并找到数组中第三小的值。

11 12 25 22 64

遍历时，22是第三小的值，它应该呈现在数组的第三位，因而将 22 与第三位的元素替换。

11 12 22 25 64

第四步：

同样，对于第四个地位，遍历数组的其余部分，找到数组中第四小的元素

因为 25 是第四低的值，因而它将排在第四位。

11 12 22 25 64

第五步：

最初，数组中存在的最大值主动搁置在数组的最初一个地位

后果数组是排序后的数组。

11 12 22 25 64

请依照以下步骤实现代码：

将最小值 (min_idx ) 初始化为地位 0。
遍历数组，找到数组中的最小元素。
在遍历时，如果找到任何小于min_idx 的元素，则替换两个值。
而后，递增 min_idx 以指向下一个元素。
反复直到数组被排序。

上面是上述办法的实现：

java版本

import java.io.*;
public class SelectionSort
{void sort(int arr[])
    {
        int n = arr.length;

        // 逐渐挪动未排序数组的边界
        for (int i = 0; i < n-1; i++)
        {
            // 查找未排序数组中的最小元素
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            // 将找到的最小元素与第一个元素进行替换
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    // 打印排序后的数组后果
    void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();}


    public static void main(String args[])
    {SelectionSort ob = new SelectionSort();
        int arr[] = {64,25,12,22,11};
        ob.sort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
    }
}

输入

排序数组：11 12 22 25 64

工夫复杂度：抉择排序的工夫复杂度为 O(N 2)，因为有两个嵌套循环：

一个循环一个一个地抉择 Array 的一个元素 = O(N)
将该元素与每个其余数组元素进行比拟的另一个循环 = O(N)

因而整体复杂度 = O(N) O(N) = O(NN) = O(N 2)

辅助空间： O(1) 作为惟一应用的额定内存用于长期变量，同时替换数组中的两个值。抉择排序永远不会进行超过 O(N) 次替换，并且在内存写入是一项代价昂扬的操作时十分有用。

稳定性 ：默认实现 不稳固。然而，它能够变得稳固。这个后续再讲。

简略易懂。
保留具备雷同键的我的项目的绝对程序，这意味着它是稳固的。
实用于小型数据集。
它实用于各种类型的数据类型。
抉择排序是一种就地排序算法，这意味着它不须要任何额定的内存来对列表进行排序。
它具备 O(n^2) 的最佳状况和均匀状况工夫复杂度，使其对于小型数据集十分无效。
很容易批改为按升序或降序排序。
它能够很容易地在硬件中实现，使其实用于实时利用。
它也能够用作更无效的排序算法中的子程序。
它不须要任何非凡的内存或辅助数据结构，使其成为轻量级解决方案。
该算法能够轻松并行，容许在多核处理器上进行高效排序。
它能够在无限的内存环境中应用，因为它须要起码的额定内存。
它易于了解，使其成为教学目标的热门抉择。
它实用于对惟一键很少的数据进行排序，因为它在这种状况下体现良好。

抉择排序在最坏和均匀状况下的工夫复杂度为 O(n^2)。
在大型数据集上成果不佳。
抉择排序算法须要屡次迭代列表，因而会导致不均衡分支。
抉择排序的缓存性能很差，因而对缓存不敌对。
不是自适应的，这意味着它没有利用列表可能曾经排序或局部排序的事实
对于具备慢速随机存取存储器 (RAM) 的大型数据集来说不是一个好的抉择
它不是比拟排序，也没有像合并排序或疾速排序那样的任何性能保障。
它的缓存性能很差
因为其高分支预测错误率，它可能导致分支预测不佳
它有很多写操作，导致在存储速度慢的零碎上性能不佳。
它不是可并行算法，这意味着它不能轻易拆分以在多个处理器或内核上运行。
它不能很好地解决具备许多反复项的数据，因为它会进行许多不必要的替换。
在大多数状况下，它能够被其余算法（如疾速排序和堆排序）超过。

抉择排序是一种简略易懂的排序算法，其工作原理是从列表的未排序局部反复抉择最小（或最大）的元素并将其挪动到列表的已排序局部。
对列表中残余的未排序局部反复此过程，直到整个列表排序结束。
在最坏和均匀状况下，它的工夫复杂度为 O(n^2)，这使得它对于大型数据集的效率较低。
抉择排序是一种稳固的排序算法。
它可用于对不同类型的数据进行排序。
它在特定应用程序中很有用，例如小型数据集和内存受限零碎。

本文由 mdnice 多平台公布

关于程序员:每日一算选择排序算法

抉择排序流程图：

抉择排序原理？

实战演练

抉择排序的复杂度剖析：

抉择排序算法是否稳固？

抉择排序算法的长处：

抉择排序算法的毛病：

总结：