前言

排序算法做为算法的入门，是比较重要的，虽然在实际开发当中很少自己去实现排序算法，但是掌握其一些基本概念，学会如何去写还是非常有必要的，所以系统的学习总结一下，希望能彻底搞明白这些知识点。如果有读者发现有写的不对的，可以微博私信我，谢谢。

学习算法之前，首先理解一下所谓稳定性的概念。

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

算法概要

冒泡排序

基本概念

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

实现代码

public class BubbleSort {
    public static void main(String[] args) {
        int[] data1 = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        int[] data2 = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        int c1 = 0;
        int c2 = 0;
        for (int i = data1.length - 1; i >= 0; i--) {//从后往前，将最大的数移到末尾
            for (int j = 0; j < i ; j++) {
                if (data1[j] > data1[j + 1]) {
                    c1++;
                    swap(data1, j, j + 1);
                }
            }
        }
        System.out.println(c1); //output:44
        System.out.println(Arrays.toString(data1));//output:[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
        for (int i = 0; i < data2.length; i++) {//从前往后，将最小的数移到开头
            for (int j = data2.length - 1; j > i; j--) {
                if (data2[j - 1] > data2[j]) {
                    c2++;
                    swap(data2, j - 1, j);
                }
            }
        }
        System.out.println(c2); //output:44
        System.out.println(Arrays.toString(data2)); //output:[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
    }

    private static void swap(int[] data, int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}

快速排序

基本概念

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是：
1.设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2.以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3.从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4.从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5.重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

实现代码

public class QuickSort {
    public static void main(String[] args) {
        int[] data = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        System.out.println(Arrays.toString(data));
        sort(data, 0, data.length - 1);

    }


    public static void sort(int[] data, int left, int right) {
        if (left < right) {
            int pivot = data[left];
            int i = left;
            int j = right;
            while (i < j) {
                while (i < j && data[j] > pivot) {
                    j--;
                }
                data[i] = data[j];
                while (i < j && data[i] <= pivot) { //这里和上方必须有一个等于，否则会出现死循环
                    i++;
                }
                data[j] = data[i];
            }
            data[i] = pivot;
            System.out.println(Arrays.toString(data));
            sort(data, left, j - 1);
            sort(data, j + 1, right);
        }
    }
}

详细过程

用一个例子来说明为什么快速排序是不稳定的，我们加几个连续的重复的数据,2a，2b,2c和2d值是一样的，我们用abcd区分它们为不同的2。
int[] data = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2a, 2b, 2c, 2d, 46, 4, 19, 50, 48};

1.选取第一个元素3作为基准元素，j从右侧开始向左边遍历，找到第一个小于等于基准元素的数2d，将其赋值给下标为0的3，此时变成[2d, 44, 38, 5, 47, 15, 36, 26, 27, 2a, 2b, 2c, 2d, 46, 4, 19, 50, 48]

2.然后i从左侧开始向右遍历，找到第一个大于基准元素的数(下标为1的44)，将44赋值给2d，[2d, 44, 38, 5, 47, 15, 36, 26, 27, 2a, 2b, 2c, 44, 46, 4, 19, 50, 48]

3.然后j继续往左，找到2c，将其赋值给下标为1的44，[2d, 2c, 38, 5, 47, 15, 36, 26, 27, 2a, 2b, 2c, 44, 46, 4, 19, 50, 48]

4.然后i继续往右，找到下标为2的38，将其赋值给2c，[2d, 2c, 38, 5, 47, 15, 36, 26, 27, 2a, 2b, 38, 44, 46, 4, 19, 50, 48]

5.然后j继续往左，找到2b，将其赋值给下标为2的38，[2d, 2c, 2b, 5, 47, 15, 36, 26, 27, 2a, 2b, 38, 44, 46, 4, 19, 50, 48]

6.然后i继续往右，找到下标为3的5，将其赋值给2b，[2d, 2c, 2b, 5, 47, 15, 36, 26, 27, 2a, 5, 38, 44, 46, 4, 19, 50, 48]

7.然后j继续往左，找到2a，将其赋值给下标为3的5，[2d, 2c, 2b, 2a, 47, 15, 36, 26, 27, 2a, 5, 38, 44, 46, 4, 19, 50, 48]

8.然后i继续往右，找到下标为4的47，将其赋值给2a，[2d, 2c, 2b, 2a, 47, 15, 36, 26, 27, 47, 5, 38, 44, 46, 4, 19, 50, 48]

9.最后j继续往左，找不到小于等于比基准元素3的了，j的值一直减到4，而i继续往右，i值为4，不满足i<j了，所以不再自增，跳出外层while循环，将基准元素赋值给i,j指针相遇的那个元素，最终得到[2d, 2c, 2b, 2a, 3, 15, 36, 26, 27, 47, 5, 38, 44, 46, 4, 19, 50, 48]。

10.然后以3为分割点，拆分成[2d, 2c, 2b, 2a]和[47, 15, 36, 26, 27, 5, 38, 44, 46, 4, 19, 50, 48]，分别递归对这2部分进行快排。左边按照上述步骤实际上做了以下交换[2d, 2c, 2b, 2a]->[2a, 2c, 2b, 2a]->[2a, 2c, 2b, 2d]。然后再拆分，左侧变为[2a, 2c, 2b]，排序过程[2a, 2c, 2b] ->[2b, 2c, 2b]->[2b, 2c, 2a]。再拆分，左侧变为[2b, 2c],排序过程[2b, 2c]->[2c, 2c]->[2c, 2b]。好了，最终那4个2排序的结果为[2c, 2b, 2a, 2d],跟原始的[2a, 2b, 2c, 2d]顺序不一致，所以得出结论快速排序是不稳定的。

是否稳定判断

也可以跑通过程序测试，测试代码如下:

public class QuickSort {
    public static void main(String[] args) {
        String[] data = {"2a", "2b", "2c", "2d"};
        System.out.println(Arrays.toString(data));
        sort(data, 0, data.length - 1);

    }


    public static void sort(String[] data, int left, int right) {
        if (left < right) {
            String pivot = data[left];
            int i = left;
            int j = right;
            while (i < j) {
                while (i < j && getData(data[j]) > getData(pivot)) {
                    j--;
                }
                data[i] = data[j];
                System.out.println(Arrays.toString(data));
                while (i < j && getData(data[i]) <= getData(pivot)) {
                    i++;
                }
                data[j] = data[i];
                System.out.println(Arrays.toString(data));
            }
            data[i] = pivot;
            System.out.println(Arrays.toString(data));
            sort(data, left, j - 1);
            sort(data, j + 1, right);
        }
    }

    private static int getData(String s) {
        return Integer.valueOf(s.substring(0,1));
    }

}

输出结果:
[2a, 2b, 2c, 2d]
[2d, 2b, 2c, 2d]
[2d, 2b, 2c, 2d]
[2d, 2b, 2c, 2a]
[2c, 2b, 2c, 2a]
[2c, 2b, 2c, 2a]
[2c, 2b, 2d, 2a]
[2b, 2b, 2d, 2a]
[2b, 2b, 2d, 2a]
[2b, 2c, 2d, 2a]

选择排序

基本概念

选择排序是从一组待排序的元素中选择出最小(或最大)的元素放在这组待排序元素的起始位置。选择排序的比较次数跟冒泡差不多，但是比冒泡改进的地方在于它大大减少了交互数据的次数，只有找到最小(或最大)的元素所在的索引和待排序元素的起始索引不一致时才进行交换。

实现代码

public class SelectionSort {
    public static void main(String[] args) {
        int[] data = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        for (int i = 0; i < data.length; i++) {
            int min = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[min]) {
                    min= j;
                }
            }
            if (min != i) {
                swap(data, i, min);
            }
        }
        System.out.println(Arrays.toString(data));
    }

    private static void swap(int[] data, int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}

详细过程

1.第一次遍历未排序的元素，设起始索引所对应的元素为最小值，拿后面的元素与之进行比较，找出真正最小的元素，使其与起始元素进行交换。
2.第二次遍历未排序的元素，由第一次遍历可以得出目前所有元素中的最小值已经找出来了，放在了元素开头，接下来未排序的元素就去掉了开头元素。
3.重复执行步骤1,2即可得出结果。

是否稳定判断

选择排序是不稳定的排序，例如一组元素[4a,4b,4c,2],我们按照上述步骤进行排序，最终得到的结果为[2,4b,4c,4a]，显然3个4的顺序跟之前不符了。

插入排序

基本概念

插入排序首先选择一个起始索引(大于0)，不断往前找，找到比它小的元素之间，插进去，然后后面元素往后移一位，实际上移位操作等同于该元素不断与前面比它大的元素进行交换，跟冒泡那种交换类似。然后起始索引往后移，重复前面插入操作。

实现代码

public class InsertSort {
    public static void main(String[] args) {
        int[] data = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        for (int i = 1; i < data.length; i++) {
            for (int j = i; j > 0; j--) {
                if (data[j] < data[j - 1]) {
                    swap(data, j, j - 1);
                } else {
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(data));
    }

    private static void swap(int[] data, int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}

详细过程

1.起始索引从1开始，比较data[1]和data[0]大小，如果data[1]小与data[0]，将data[1]插入到data[0]的位置，data[0]后移，实际上就是交换了两者的位置。否择直接跳出循环，继续移动起始索引。
2.起始索引从2开始，比较data[2]和data[1]的大小，38小与44，但是大于3，所以将38插入到44的位置，44往后移。
3.重复上述1，2步骤

插入排序的时间复杂度最好的情况是O(n)，例如对于一组已经排好序的元素[1,2,3,4]。
1.第一次遍历比较2和1,2大于1，break
2.第二次遍历比较3和2,3大约2，break
3.第三次遍历比较4和3,4大约3，break
实际上内层循环就只执行了一次，整体时间复杂度就只是外层的n次循环，故为O(n)。

是否稳定判断

插入排序每一次插入的过程，后面的元素是平移的，所以不会改变原先相同元素的顺序。例如[2,3a,4,3b,1]，3b跟4换了一次，1跟前面的元素都换了一次，最终得到[1,2,3a,3b,4]。3a还是在3b前面，所以是稳定的。

---

前面说的4种排序算法都是基于比较的，下面的2种排序算法是非比较算法，所谓非比较算法就是并非是通过比较数直接的大小来完成排序的。

计数排序

基本概念

计数排序是一种非比较算法，计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。
具体步骤：
1.先从需要排序的数据中找出最大值，用于确定一个计数数组可以用下标表示它们所有元素。
2.遍历需排序的数据，用计数数组下标来表示其对应元素的个数。
3.遍历计数数组，将每个下标表示的元素值用于表示小等于该下标数据的个数。
4.最后根据计数数组将原始数据按顺序填入新构建的存放数据的数组中。

实现代码

public class CountSort {
    public static void main(String[] args) {
        int[] a = {2, 3, 8, 7, 1, 12, 24, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2};
        int[] ret = new int[a.length];
        int max = a[0];
        for (int i = 0; i < a.length; i++) {
            max = Math.max(max, a[i]);
        }
        System.out.println("max: " + max);
        int[] count = new int[max + 1];

        for (int i = 0; i < a.length; i++) {
            count[a[i]]++;
        }


        for (int i = 1; i < count.length; i++) {
            count[i] = count[i - 1] + count[i];
        }


        for (int i = a.length - 1; i >= 0; i--) {//这里需要倒序遍历，否则最后的排序结果是不稳定的
            ret[--count[a[i]]] =  a[i];
        }

        System.out.println(Arrays.toString(ret));
    }

}

详细过程

1.找出最大值为24，那么我们可以用一个大小为24的数组（下标0~24）int[] count = new int[25]来表示所有的元素
2.遍历所有元素，可以得到count[0] = 0, count[1] = 2, count[2] = 5 …
3.遍历count数组，用count[i] = count[i - 1] + count[i]计算小于等于数组下标的所有元素个数，例如count[1] = 2, count[2] = 7… count[24] = 20
4.定义一个新的数组ret，将a数组的元素依次赋值进去，数值为2的a[19]元素， 该元素在新的数组中的位置为6(count[2] - 1),因为小于等于2的元素一共有7个，我们将这个2插到第7的位置上没有问题，然后将count[2]的计数从7->6。

是否稳定判断

排序为稳定的，参见上面详细过程第4步，有5个相同的2，从后往前遍历，前面的2由于count[2]的减1会放到靠前的位置了。

基数排序

基本概念

基数排序同样也是一种非比较的算法，是根据各个元素的位数进行排序的，主要实现方式有2种，一种是least significant digit(LSD)，一种是 most significant digit (MSD)。LSD从低位开始排到高位，每排一位都是把各个桶合并，再按下一位排序；MSD从高位开始排到低位，排完一位后不合并桶，相同的高位划分子桶继续分配，最后再合并。下面基于LSD来实现。

LSD具体步骤：
1.定义一个桶[0-9],将待排序的所有元素的个位值放入对应的桶中，例如123,23放入桶3, 4放入桶4， 1放入桶1。
2.针对上一部放入桶中的元素按序输出得到1, 123, 23, 4,然后对十位进行排序，因为个位已经排好序了，所以十位相同的元素个位小的会在前面
3.依次执行上述步骤，直到处理到所有元素的最高位，这里是百位

实现代码

public class RadixSort {


    public static void main(String[] args) {
        int[] data = {3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 203, 3138, 82, 2599, 743, 4127};
        int digit = getMaxDigit(data);
        System.out.println(Arrays.toString(sort(data, digit)));
    }


    //获取最高位数
    private static int getMaxDigit(int[] data) {
        int max = String.valueOf(data[0]).length();
        for (int i = 1; i < data.length; i++) {
            max = Math.max(max, String.valueOf(data[i]).length());
        }
        return max;
    }

    private static int getNumOnDigit(int num, int d) {
        while (d-- > 0) {
            num = num / 10;
        }
        return num % 10;
    }

    private static int[] countSort(int[] data, int d) {
        //因为基数为10，所以计数排序辅助数组0-9即可
        int[] count = new int[10];
        int[] ret = new int[data.length];
        for (int i = 0; i < data.length; i++) {
            int n = getNumOnDigit(data[i], d);
            count[n]++;
        }
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i - 1] + count[i];
        }


        for (int i = data.length - 1; i >= 0; i--) {
            int n = getNumOnDigit(data[i], d);
            ret[--count[n]] = data[i];
        }


        return ret;
    }


    private static int[] sort(int[] data, int digit) {
        for (int d = 0; d < digit; d++) {
            data = countSort(data, d);
        }
        return data;
    }

}

详细过程

1.先获取所有元素最高位数4
2.因为每一位的元素可以用0-9表示，每一位可以用前面提到的计数排序进行排序
3.对所有位进行计数排序

是否稳定判断

采用了稳定的计数排序作为每一位的排序算法，所以是稳定的。

#算法总结

Markdown语法编写表格样式还是比较麻烦的，打中文就对不齐了，只能这样了。

sort algorithm	time complexity(avg)	time complexity(worst)	time complexity(best)	zone complexity	is stable
bubble sort	O(n^2)	O(n^2)	O(n^2)	O(1)	yes
quick sort	O(nlogn)	O(n^2)	O(nlogn)	O(logn)	no
selection sort	O(n^2)	O(n^2)	O(n^2)	O(1)	no
insert sort	O(n^2)	O(n^2)	O(n)	O(1)	yes
count sort	O(n + k) k means range	O(n + k) k means range	O(n)	O(n+k)	yes
radis sort	O(d(n+k)) count sort	O(d(n+k))	O(n)	O(n+k)	yes