常见排序算法

各种算法以及时间复杂度和空间复杂度

可视化网站（超级直观）：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

算法稳定性：算法稳定性指的是排序序列中有两个元素相等，而且在排序前和排序后两个相等的元素的相对位置不变

时间复杂度和空间复杂度一览：

冒泡排序：https://www.cnblogs.com/jingmoxukong/p/4302718.html

    public void bubbling(int[] list) {
        for (int i = 0; i < list.length-1; i++) {
            for (int j = 0; j < list.length-i-1; j++) {
                if (list[j] > list[j+1]) {
                    int temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
        }
    }

选择排序（和冒泡类似）：

选择排序，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列（和冒泡不同的是，冒泡一直都在判断并且交换，而选择排序是先找到下标，然后再交换）。

    public void selectSort(int[] arrays) {
        for (int i = 0; i < arrays.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arrays.length; j++) {
                if (arrays[j] < arrays[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = arrays[i];
                arrays[i] = arrays[min];
                arrays[min] = temp;
            }
        }
    }

快速排序（设置left，right和基准数）：

　　①先从队尾开始向前扫描且当low < high时,如果a[high] > tmp,则high–,但如果a[high] < tmp,则将high的值赋值给low,即arr[low] = a[high],同时要转换数组扫描的方式,即需要从队首开始向队尾进行扫描了
②同理,当从队首开始向队尾进行扫描时,如果a[low] < tmp,则low++,但如果a[low] > tmp了,则就需要将low位置的值赋值给high位置,即arr[low] = arr[high],同时将数组扫描方式换为由队尾向队首进行扫描.
③不断重复①和②,知道low>=high时(其实是low=high),low或high的位置就是该基准数据在数组中的正确索引位置.

通过一张图更容易了解

private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int index = getIndex(arr, low, high);
            quickSort(arr, 0, index - 1);
            quickSort(arr, index + 1, high);
        }
    }
    private static int getIndex(int arr[], int low, int higt) {
        int temp = arr[low];
        while (low < higt) {
            while (low < higt && arr[higt] >= temp) {
                higt--;
            }
            arr[low] = arr[higt];
            while (low < higt && arr[low] <= temp) {
                low++;
            }
            arr[higt] = arr[low];

        }
        arr[low]=temp;
        return low;
    }

插入排序（直接插入排序）：

直接插入排序相当于是在一个有序的序列中一个一个的插入，使得总体有序。比冒泡和选择排序快，用户小规模排序和数据基本有序时的排序。如果数据规模较大且数据无序时还是使用希尔排序。

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j-1]) {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                j--;
            }
        }
    }

插入排序（希尔排序，基于直接插入排序）：

也叫缩小增量排序法，逐渐缩小增量，对选中的元素进行直接插入排序。

上面是一趟排序，然后逐渐缩小增量，最后实现增量为0，即对全部元素进行直接插入排序算法。第二个for循环开始，其实执行的就是直接插入排序，但是其并不是直接将增量中数字一次性排完，而是不同的分组之间交替排序。因为在第二个for循环中是i++（这里可能描述的有点混淆，可以先看代码，第一次看此代码的时候被困在这个地方）

public static void shellSort(int[] arrays) {
        //增量每次都/2
        for (int step = arrays.length / 2; step > 0; step /= 2) {
            //从增量那组开始进行插入排序，直至完毕
            for (int i = step; i < arrays.length; i++) {
                int j = i;
                // j - step 就是代表与它同组隔壁的元素
                while (j - step >= 0 && arrays[j - step] > arrays[j]) {
                    int temp = arrays[j];
                    arrays[j] = arrays[j - step];
                    arrays[j-step]=temp;
                    j = j - step;
                }
            }
        }
    }