关于算法:算法总结直接选择排序

算法定义

间接抉择排序是抉择排序的一种，是一种简略的排序办法，依据百科的定义，它的根本思维是：第一次从 R[0] ~ R[n – 1]中选取最小值，与 R[0]替换，第二次从 R[1] ~ R[n – 1]中选取最小值，与 R[1]替换 … 第 i 次从 R[i – 1] ~ R[n – 1]中选取最小值，与 R[i – 1]替换 … 第 n - 1 次从 R[n – 2] ~ R[n – 1]中选取最小值，与 R[n – 2]替换，总共通过 n – 1 次，失去一个按排序码从小到大排列的有序序列。

算法原理

间接抉择排序算法的原理如下：

1、在未排序序列中找到最小 (大) 元素，寄存到排序序列的起始地位。

2、再从残余未排序元素中持续寻找最小 (大) 元素，而后放到已排序序列的开端。

3、反复第二步，直到所有元素均排序结束。

代码实现

依照下面的思路，代码如下：

public class Main {// 间接抉择排序(抉择排序)，均匀工夫复杂度 O(n^2)，最好工夫复杂度 O(n^2)，最坏工夫复杂度 O(n^2)，空间复杂度 O(1)
    public void directlySelectSort(int[] arr) {
        // 获取数组的长度
        int n = arr.length;

        // 走 n - 1 趟，每趟确定以后的最小值
        for (int i = 0; i < n - 1; ++i) {
            // 定义以后的最小值下标
            int minIndex = i;

            // 最小值下标的值和前面的值一一比拟，找出这里的最小值下标
            for (int j = i + 1; j < n; ++j) {
                // 若以后下标的值比最小值下标的值还小，那么最小值下标设置为以后下标
                if (arr[j] < arr[minIndex]) {minIndex = j;}
            }

            if (minIndex != i) {
                // 若前面能找到比最小值下标的值更小的值，那么替换两个元素，否则最小值下标的值就是以后的最小值，无需替换元素
                arr[i] ^= arr[minIndex];
                arr[minIndex] ^= arr[i];
                arr[i] ^= arr[minIndex];
            }
        }
    }

}

算法效率

间接抉择排序是不稳固的排序算法。

工夫复杂度都是 O(n²)，因为无论数组是哪种状况，都须要进行两次 for 循环，都是确定数组前 n - 1 个最小值，即便数组是自身有序的。

空间复杂度为 O(1)，因为只应用无限个数的变量。

算法稳定性的意思是：如果在待排序的记录序列中，存在多个具备雷同的关键字的记录，若通过排序，这些记录的绝对秩序放弃不变，即在原序列中，r[i] = r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前，则称这种排序算法是稳固的；否则称为不稳固的。

例如：一堆商品，先按价格排序，再在价格排序好的根底上按销量排序，如果有两个商品的销量一样，那么依照常理，两个一样销量的商品就要依照原来价格的程序去排列，也就是说有两个排序属性了，先依照销量排序，再依照价格排序，如果算法是稳固的，那么就是雷同销量的商品还会依照原来价格的程序来排，如果算法不是稳固的，那么可能雷同销量的商品的程序会变得不确定，简略来说就是，稳固算法就是数组中相等的值在排序后还是放弃原来绝对的程序不变。

如果单纯就是依照一种属性的排序，那么算法是否稳固没有意义，然而现实生活中并不是都是依照繁多属性来排序的，很多是依照多属性来排序的，所以算法是否稳固是很重要的一个指标。

间接抉择排序，因为在每一次确定以后最小值时，有可能会毁坏数组中相等的值的绝对程序，例如数组：[3, 3, 1]，第一趟确定最小值后就变成[1, 3, 3]，原数组中的两个 2 的绝对程序就被扭转了，所以咱们说间接抉择排序是不稳固的。

均匀工夫复杂度：O(n^2)

最好工夫复杂度：O(n^2)

最坏工夫复杂度：O(n^2)

空间复杂度：O(1)

参考资料

间接抉择排序动图来自：间接抉择排序

原文链接

原文链接：算法总结 - 间接抉择排序