关于算法:排序算法的简单认识

在进行很多便捷算法之前总是要实现对象的有序化，而这就将应用到排序相干的算法，即便目前诸多高级语言未然实现对于排序算法的封装，用户只需导入对应库文件即可调用排序算法实现排序，无需手写排序算法，但具体的排序算法的抉择就必须对于排序算法有所意识。本文就将介绍两个简略的排序算法：抉择排序与冒泡排序。

为什么称为抉择排序？
该算法每次都是对于未排序的关键字进行比拟，抉择出最小或最大的关键字，再对其替换地位，实现一次排序，需进行屡次比拟。

抉择排序法是一种不稳固的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，寄存在序列的起始地位，而后，再从残余未排序元素中持续寻找最小（大）元素，而后放到已排序序列的开端。以此类推，直到全副待排序的数据元素排完。
抉择排序是一种简略直观的排序算法，无论什么数据进去都是 O(n²) 的工夫复杂度。所以用到它的时候，数据规模越小越好。在复杂度剖析上，它最大的特点就是替换挪动数据的次数较少，无需占用较大的内存空间。

假如存在一个长度为 n 的数组，须要进行抉择排序，每次下标变量设为 i，即 1<=i<=n。算法实现的基本思路是将数组进行 n-1 次关键字的比拟，即对于数组下标对应值的比拟，记录下标存进 min 或 max，最初将其关键字与第 i 个关键字进行替换，实现一次抉择。

抉择排序根本存在两层 for 循环嵌套，最外层循环是为了保障 n-1 次排序，第二层 for 循环是为了在每一次排序的过程中寻找最值的下标，并且防止死循环，内层循环将从 i+1 开始进行比拟。它们对于循环的判断条件区别如下：

外层循环：从零开始且小于数组长度减一，迭代语句为迭代标记加一
内层循环：从 i+1 开始小于数组长度，迭代语句为迭代标记加一

内层循环中的抉择语句是以后迭代标记对应的数组元素与记录以后残余局部最值下标的对应数组元素的比拟，按排序要求抉择大小关系，进入抉择语句，将最值下标赋给记录变量。

排序程序次要看你的下标记录值的状况，在每一次比拟中，下标记录较大值，为降序排序，下标记录较小值，为升序排序，上面将展现升序排序代码实现。

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 总共要通过 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[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和 i 地位所在的值进行替换
            if (i != min) {int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }

        }
        return arr;
    }
}

与抉择排序同属根底排序算法的还有冒泡排序，它也是基于比拟与替换实现对于对象的排序的算法，思路非常简略。开始介绍吧！

冒泡排序也是一种简略直观的排序算法。它反复地走访过要排序的数列，一次比拟两个元素，如果他们的程序谬误就把他们替换过去。走访数列的工作是反复地进行直到没有再须要替换，也就是说该数列曾经排序实现。这个算法的名字由来是因为越小的元素会经由替换缓缓 ” 浮 ” 到数列的顶端。

假如所需排序的数组为 [2,1,3,4,5,6,7,8,9]，尝试应用以上思路下的冒泡排序算法来进行的话，将会发现除了第一次替换数据有所意义之外，对于前面未然有序的数组而言，应该完结循环，实现排序，但它没有，它还是义无反顾地执行了 n-2 次循环。这将有肯定地优化空间。

优化算法思路就是立一个 flag 作为标记，当在一趟序列遍历中元素没有产生替换，则证实该序列曾经有序，无需反复进行屡次循环，在数据规模微小的状况下，这种优化所起到的作用是弱小的。

与抉择排序统一，领有两层 for 循环，外层循环决定排序次数，内层循环决定排序做法。冒泡排序经常是从左到右进行挪动元素，所以，内层循环迭代标记需小于数组长度减已排序次数。内层循环每次比拟，只有反序，间接替换地位。

public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不扭转参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        for (int i = 1; i < arr.length; i++) {for (int j = 0; j < arr.length - i; j++) {if (arr[j] > arr[j + 1]) {int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
        return arr;
    }
}

public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不扭转参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记，若为 true，则示意此次循环没有进行替换，也就是待排序列曾经有序，排序曾经实现。boolean flag = true;

            for (int j = 0; j < arr.length - i; j++) {if (arr[j] > arr[j + 1]) {int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    flag = false;
                }
            }

            if (flag) {break;}
        }
        return arr;
    }
}

算法的比拟，无非从算法复杂度（即工夫复杂度与空间复杂度）剖析以及算法稳定性下手，简略讲一下这些概念：

算法复杂度：算法复杂度可分为工夫复杂度与空间复杂度，是作为一个算法评判一个优质算法的根本规范，往往一个优质算法，是能够做到一个工夫复杂度与空间复杂度的很好均衡，但在某些状况下，一个极其偏差其中一个复杂度的算法也不为一个优质算法。
工夫复杂度：算法所消耗工夫，经常应用大写 O() 示意，可分为常数阶，即 O( 常数)，函数阶，如线性阶 O(f(n))、平方阶 O(f(n^2)) 等等
空间复杂度：算法代码运行消耗的内存空间。
算法稳定性：对于运行算法代码前后的无需扭转局部的判断，如果产生了肯定扭转，即便根本性质不变，它也是不稳固的。
举个例子 5，8，5，2，9 咱们晓得第一遍抉择第一个元素 5 会和 2 替换，那么原序列中 2 个 5 的绝对地位前后程序就毁坏了，就是不稳固的。

冒泡排序优缺点：

长处: 比较简单，空间复杂度较低，是稳固的；
毛病: 工夫复杂度太高，效率慢；

抉择排序优缺点：

长处：一轮比拟只须要换一次地位；
毛病：效率慢，不稳固

关于算法:排序算法的简单认识

抉择排序

算法代码实现

冒泡排序

算法代码实现

简略算法

优化算法：

算法比拟