排序

冒泡排序

比较两个相邻元素的大小，如果前面的大于后面的，则调换位置。每次遍历会将最大的元素调换到最右边。

private static void bubbing(int[] a) {
        int len = a.length;
        for (int i = 0;i<len-1;i++) {
            for (int j = 0;j<len-1-i;j++) {
                if (a[j] > a[j+1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }

动态图

bubbing.jpeg

选择排序

先遍历整个列表，拿到最大或者最小的元素放到最前面，然后再遍历剩下的元素并找到最大或者最下的元素放到已排好序的末尾。

private static void selectionSort(int[] a) {
        int len = a.length;
        int temp,minVal,minIndex;
        for (int i = 0;i<len-1;i++) {
            // 作为比较的数据
            minVal = a[i];
            minIndex = i;
            // 遍历剩下的元素，找到最小值以及对应的下标
            for (int j = i+1;j<len;j++) {
                if (a[j]<minVal) {
                    minVal = a[j];
                    minIndex = j;
                }
            }
            // 切换位置
            temp = a[i];
            a[i] = minVal;
            a[minIndex] = temp;
        }
    }

动图

selectionSort.gif

插入排序

类似于斗地主扑克排序，右手获取新的牌，将新的牌在左手已经排好序的列表中找到对应的位置，并插入。

private static void insectionSort(int[] a) {
        int len = a.length;
        int preIndex,current;
        for (int i = 1;i<len;i++) {
            current = a[i];
            preIndex = i-1;
            // 前面已经排好序的队列中找到元素对应的位置，寻找过程中之前的序列都要顺序往后移动
            while (preIndex >=0 && a[preIndex] > current) {
                a[preIndex+1] = a[preIndex];
                preIndex--;
            }
            a[preIndex+1] = current;
        }
    }

动图

insertionSort.gif

希尔排序

在插入排序的基础上改进的，插入排序在基本有序的情况下效率会很高，但是也存在大量的元素移动。希尔排序的思想就是讲序列分割成多个子序列，并分别进行插入排序。再缩小子序列的数量，再次各个子序列分别排序。当子序列的数量缩小到1的时候，就完成了整个排序过程。

private static void shellSort(int[] a) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = new int[a.length];
        System.arraycopy(a,0,arr,0,a.length);

        int gap = 1;
        while (gap < arr.length) {
            gap = gap * 3 + 1;
        }

        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }
        print(arr);

    }

动图

shell.png

快速排序

使用分治法把一串序列分为两个串。处理大数据最快的排序法之一。

/** 
     *@Description 先从后往前找，再从前往后找
     *  1  2  3 4  5  6 7  8  9  10 11 下标
     *  5，3，7，6，4，1，0，2，9，10，8  i = 1, j = 11 后往前
     *  2，3，7，6，4，1，0，5，9，10，8  i = 1, j = 8  前往后
     *  2，3，5，6，4，1，0，7，9，10，8  i = 3, j = 8  后往前
     *  2，3，0，6，4，1，5，7，9，10，8  i = 3, j = 7  前往后
     *  2，3，0，5，4，1，6，7，9，10，8  i = 4, j = 7  后往前
     *  2，3，0，1，4，5，6，7，9，10，8  i = 4，j = 6  前往后
     *
     *@Param a:
     *@return void
     *@Throws       
     *@Author luochaoqun
     *@Date 2020-07-03
     **/ 
    private static int[] quickSort(int[] a, int start, int end) {
        int pivot = a[1];
        int i = start;
        int j = end;
        while (i < j) {
            while ((i < j) && (a[j]>pivot)) {
                j--;
            }
            while ((i<j) && (a[i]<pivot)) {
                i++;
            }
            if ((a[i] == a[j]) && (i<j)) {
                i++;
            } else {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        if (i-1>0) {
            a = quickSort(a, start, i-1);
        }
        if (j+1 < a.length-1) {
            a = quickSort(a, j+1, end);
        }
        return a;
    }

动图

quickSort.gif

5.堆排序

6.桶排序

8.基数排序

9.计数排序

10.归并排序