【数据结构与算法】【算法】三种简单的排序算法

简单排序

相对比较简单，但复杂度比较高，时间复杂度都为O(N^2)，但空间内存占用小，是一种以时间换空间的排序想法。

排序顾名思义就是想办法让全部数据有序为止；排序需要经过以下两个基本步骤：

• 比较两个数据项
• 交换两个数据项或复制其中一项

完成排序需要循环执行以上两个步骤，循环的次数和快慢决定这排序的时间复杂度（大O表示法），即排序的速度和效率。简单排序主要有以下三种：

冒泡排序

• 什么是冒泡排序

冒泡排序就拿其中一个数据项与剩下的数据项比较，比较出最大的一项放在最右边，循环重复，知道所有数据项都排序完成。冒泡排序是最简单的排序算法，速度也是最慢的。

• 如何实现冒泡排序

public class TestMain {

    public static void main(String[] args) {

        Integer[] sortArr = {2, 3, 5, 2, 5, 7, 8, 2, 2, 4, 5, 12, 34, 45, 33, 44, 55, 32, 546};

        int in, out;

        for (out = sortArr.length - 1; out > 1; out--) {

            for (in = 0; in < out; in++) {

                if (sortArr[in] > sortArr[in + 1]) {

                    int temp = sortArr[in];

                    sortArr[in] = sortArr[in + 1];

                    sortArr[in + 1] = temp;

                }

            }

        }

        Arrays.asList(sortArr).stream().forEach(a-> System.out.print(a+" "));

    }

}

输出：2 2 2 2 3 4 5 5 5 7 8 12 32 33 34 44 45 55 546

• 冒泡排序的优缺点

时间复杂度为O(N^2)，交换的次数也为O(N^2)，效率最差，但是比较简单，适合入门练手，实际工作中很少使用，一般适用已经确定数据量很少的排序中，否则一般不会选择冒泡排序算法。

选择排序

• 什么是选择排序

选择排序针对冒泡排序进行改良的算法，从最左边位置开始，比较选择出最小的数据项，将最小的数据项交换放在最左边的位置，依次循环，这样最左边的数据项就有序了，就不需要再进行比较了，将交换的次数降低到O(N)。

• 如何实现选择排序

public class TestMain {

    public static void main(String[] args) {

        Integer[] sortArr = {2, 3, 5, 2, 5, 7, 8, 2, 2, 4, 5, 12, 34, 45, 33, 44, 55, 32, 546};

        int in, out;

        for (out = 0; out < sortArr.length; out++) {

            int min = out;

            for (in = out+1; in < sortArr.length; in++) {

                if (sortArr[min] > sortArr[in]) {

                    min = in;

                }

            }

            int temp = sortArr[out];

            sortArr[out] = sortArr[min];

            sortArr[min] = temp;

        }

        Arrays.asList(sortArr).stream().forEach(a-> System.out.print(a+" "));

    }

}

输出：2 2 2 2 3 4 5 5 5 7 8 12 32 33 34 44 45 55 546

• 选择排序的优缺点

时间复杂度还是O(N^2),算法也比较简单，但是交换次数降低为O(N)，比冒泡排序提高了效率，

插入排序

• 什么是插入排序

插入排序利用局部有序的思想，从左边开始，腾出一个位置，腾出的数据项就作为比较对象，左边的每个数据项都跟该对象比较，比它大的，就往空位置挪一步，依次循环，待到左边的都全部比较完了，最后将腾出的数据项填充到最后剩下的空位置上，这样左边的就全部有序了（其实就是将左边有序的数据项整体往右边移动合适的位置，空出来的位置就是下一个需要插入的经过比较的数据项）；然后继续往右，重复上面的逻辑，直到右边的最后一个数据项，这样就全部有序了。

• 如何实现插入排序

public class TestMain {

    public static void main(String[] args) {

        Integer[] sortArr = {2, 3, 5, 2, 5, 7, 8, 2, 2, 4, 5, 12, 34, 45, 33, 44, 55, 32, 546};

        int in, out;

        for (out = 1; out < sortArr.length; out++) {

            int temp = sortArr[out];

            in = out;//空位置

            while (in>0 && sortArr[in-1] > temp){

             sortArr[in] = sortArr[in-1];

             --in;

            }

            sortArr[in] = temp;

        }

        Arrays.asList(sortArr).stream().forEach(a-> System.out.print(a+" "));

    }

}

       输出：2 2 2 2 3 4 5 5 5 7 8 12 32 33 34 44 45 55 546

• 插入排序的优缺点

时间复杂度还是O(N^2)；当数据存在局部有序的情况下，插入排序比选择排序还要快，但是如果数据全都都是逆序的情况下，插入排序就跟冒泡排序的效率就不分仲伯了。但是插入排序还是这三种简单排序中最好的一种，也经常作为其他算法的一部分使用。