算法

算法

 算法如果不常使用，可能过段时间就点模糊了；这里总结几种常用的排序算法，帮助记忆并理解，举一反三。

冒泡排序

 冒泡排序(Bubble Sort):一种简单的排序算法，重复地走访过需要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作重复进行直到没有再需要交换为止。也即该数列已经完成排序。交换位置的过程中越小的数会慢慢“浮”到数列的左边(顶端)，也是算法名字的由来。

冒泡算法的主要流程:
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。(较小的左移)
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

Java实现

private static int[] array = {1, 4, 90, 36, 67, 23, 76, 87, 10, 9, 12};//数组为例
private static void bubbleSort(int[] array) {
        if (null == array || array.length < 1) {
            return;
        }

        for (int i = array.length; i > 0; i--) {
            for (int j = 0; j < i && (j + 1) < i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j]; //交换相邻两组数的位置
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    System.out.println(Arrays.toString(array));
                }
            }
        }
    }

以上述数组为例可以看到数据交换的情况:

从上图中可以观察到较小的数不断向上 浮出 最后完成对数组的排序。
冒泡排序作为最容易实现的排序算法，同时也是比较稳定的排序算法，如果被排序数组每次都需要交换位置，则将近需要遍历 n²/2次时间复杂度为O(n²)。
最好的情况是数组已经被排好序，则内循环遍历一遍(n次)时间复杂度为O(n)。平均情况下时间复杂度O(n²)。由于只有一个temp的临时变量作为值的交换媒介，因此空间复杂度为常量O(1)。

选择排序

 选择排序是一种简单直观的排序算法，对比与冒泡排序在排序过程中，所需移动的次数比较少。基本思想比较+交换(比较数值大小通过交换下标排序)。
选择排序主要流程:每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。

Java实现

private static int[] array = {12, 4, 90, 36, 67, 23, 76, 87, 10, 9, 1};//测试数组
private static void selectionSort(int[] array) {
        if (null == array || array.length < 1) {
            return;
        }
        for (int i = 0; i < array.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {//选出之后待排序中值最小的位置(下标)
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = array[min];//交换操作
                array[min] = array[i];
                array[i] = temp;
                System.out.println(Arrays.toString(array));
            }
        }
    }

数据排序变化情况:
原始数组( {12, 4, 90, 36, 67, 23, 76, 87, 10, 9, 1} )

无论最好还是最坏的情况时间复杂度均为O(n²)，空间复杂度为常量O(1)。虽然时间复杂度同冒泡排序一样，但是性能上是要优于冒泡排序的。

快速排序

 快速排序本质上采用了递归调用，包含了分治思想是对冒泡排序的一种改进，将待排序的数列一分为二。从中挑出一个元素作为基准，将比基准小的数左移，比基准大的数右移，直到递归结束即完成排序操作。
快速排序主要流程:
1.从数列中选出一个元素作为基准。
2.排序，将所有比基准小的元素左移，比基准大的数右移。
3.递归操作，直到数列大小为零或者一时结束，完成排序。

Java实现

private static int[] array = {12, 4, 90, 36, 67, 23, 76, 87, 10, 9, 1};
private static void quickSort(int[] array, int low, int high) {
        if (null == array || array.length < 1 || low >= high) {
            return;
        }
        int left = low;
        int right = high;

        //基准值
        int temp = array[left];
        while (left < right) {

            while (left < right && array[right] >= temp) {//从右向左找到比基准值小的元素
                right--;
            }
            array[left] = array[right];//找到比基准值小的元素，放入左侧

            while (left < right && array[left] <= temp) {//从左往右找到比基准值大的元素
                left++;
            }
            array[right] = array[left];//找到比基准值大的元素，放入右侧

        }
        array[left] = temp;
        System.out.println(Arrays.toString(array));
        quickSort(array, low, left - 1);
        quickSort(array, left + 1, high);
    }

数据排序情况:

快速排序通常情况下效率比较高，平均时间复杂度为O(nlog₂n)，最坏的情况下即变为冒泡排序时间复杂度为O(n²)。快速排序更适合处理杂乱无规律数据。

希尔排序

 希尔排序(递减增量排序算法)，是插入排序的一种更高效的改进版本，也是非稳定排序算法。
希尔排序主要流程:
1 设置gap序列即增量序列，最后一次gap必须是1。
2 将相距gap的一组数按照插入排序（注意 插入排序从第二个开始）。
3 插入排序 增量为gap 而不是1。

Java实现

private static int[] array = {12, 4, 90, 36, 67, 23, 76, 87, 10, 9, 1};
private static void shellSort(int[] array) {
        if (null == array || array.length < 1) {
            return;
        }
        int number = array.length / 2;
        int i;
        int j;
        int temp;
        while (number >= 1) {
            for (i = number; i < array.length; i++) {
                temp = array[i];
                j = i - number;
                while (j >= 0 && array[j] > temp) {
                    array[j + number] = array[j];
                    j = j - number;
                }
                array[j + number] = temp;
                System.out.println(Arrays.toString(array));
            }
            number = number / 2;
        }
    }

数组排序情况:
原始数组{12, 4, 90, 36, 67, 23, 76, 87, 10, 9, 1}

希尔排序的时间复杂度与步长有关，当步长为n/2^i时，最坏时间复杂度为O(n²)，步长为2^k - 1最坏时间复杂度为O(n^(3/2))；步长为2^i 3^j时，最坏时间复杂度为O(nlog²n)