最近在准备面试, 看到一篇公众号总结的排序算法十分详细 面试常问的十个排序算法都在这里了（含JAVA代码实现） , 因此在这里记录下.

本文将采取文字描述 + 正确的java代码实现来讲解以下的十大排序算法:

  1. 冒泡排序
  2. 选择排序
  3. 插入排序
  4. 希尔排序
  5. 归并排序
  6. 快速排序
  7. 堆排序
  8. 计算排序
  9. 桶排序
  10. 基数排序

1. 冒泡排序

介绍

冒泡排序是一种简单的排序算法. 它重复的走访要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把它们交换过来.

走访数列的工作是重复地进行直到没有在需要交换为止, 也就是说数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端.

算法时间复杂度: O(n2)

算法描述

  • 比较相邻的元素.如果第一个比第二个大, 就交换它们;
  • 对每一对相邻元素做同样的工作, 从开始第一对到结尾的最后一对, 这样在最后的元素应该会是最大的数;
  • 针对所有的元素重复以上的步骤, 除了最后一个;
  • 重复步骤1~3, 直到排序算法完成.

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

    /**
     * 冒泡算法
     */
    void bubbleSort(int[] array) {
        int len = array.length;
        if (len == 0) {
            return;
        }
        boolean needOrder;
        for (int i = 0; i < len; i++) {
            needOrder = false;
            for (int j = 0; j < len - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    needOrder = true;
                    swap(array, j, j + 1);
                }
            }
            if (!needOrder) {
                break;
            }
        }
    }

    /**
     * 交换array[i]与array[j]
     */
    private void swap(int[] array, int i, int j) {
        if (i != j) {
            array[i] = array[i] ^ array[j];
            array[j] = array[i] ^ array[j];
            array[i] = array[i] ^ array[j];
        }
    }

2. 选择排序

介绍

表现 最稳定的排序算法之一 , 因为无论什么数据进去都是O(n2) 的时间复杂度, 所以用到它的时候, 数据规模越小越好.

首选在未排序序列中找到最小(大)的元素, 存放在排序算法的起始位置, 然后, 再从剩余未排序元素中继续寻找最小(大)元素, 然后放到已排序序列的末尾.从此类推, 直到所有元素均排序完毕.

算法时间复杂度为: O(n2)

算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果. 具体算法描述如下:

  • 初始状态: 无序区为R[1…n], 有序区为空;
  • 第i趟排序(i = 1, 2, 3…n-1)开始时, 当前有序区和无序区分别为 R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  • n-1趟结束,数组有序化了.

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

    /**
     * 选择排序
     */
    void selectionSort(int[] array) {
        int len = array.length;
        if (len == 0) {
            return;
        }
        for (int i = 0; i < len; i++) {
            int minIndex = i;
            for (int j = i; j < len; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

3. 插入排序

介绍

插入排序的算法描述是一种简单直观的算法排序. 它的工作原理是通过构建有序序列, 对于未排序数据, 在已排序序列中从后向前扫描, 找到相应位置并插入.

算法时间复杂度: O(n2)

算法描述

一般来说, 插入排序都采用 in-place在数组上实现. 具体算法描述如下:

  • 从第一个元素开始, 该元素可以认为已经被排序;
  • 取出下一个元素, 在已经排序的元素序列中从后向前扫描;
  • 如果该元素大于新元素, 将该元素移到下一个位置;
  • 重复步骤3, 直到找到已排序的元素小于或者等于新元素位置;
  • 将新元素插入到该位置后, 重复步骤2~5

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

    /**
     * 插入排序
     */
    void insertionSort(int[] array) {
        int len = array.length;
        if (len == 0) {
            return;
        }
        int current, preIndex;
        for (int i = 1; i < len; i++) {
            current = array[i];
            preIndex = i - 1;
            while (preIndex >= 0 && array[preIndex] > current) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
    }

4. 希尔排序

介绍

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破 O(n2)的第一批算法之一。

它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法时间复杂度: O(nlogn)

算法描述

我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。

希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行k 趟排序；
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

img

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    /**
     * 希尔排序
     */
    void ShellSort(int[] array) {
        int len = array.length;
        if (len == 0) {
            return;
        }
        int current, gap = len / 2, preIndex;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                current = array[i];
                // 每次步长为gap
                preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > current) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = current;
            }
            gap /= 2;
        }
    }

5. 归并排序

介绍

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法时间复杂度: O(nlogn)

算法描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列;
  • 对这两个子序列分别采用归并排序;
  • 将两个排序好的子序列合并成一个最终的排序序列

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

    /**
     * 归并排序
     */
    int[] mergeSort(int[] array) {
        int len = array.length;
        if (len < 2) {
            return array;
        }
        int mid = len / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, len);
        return merge(mergeSort(left), mergeSort(right));
    }

    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     */
    private int[] merge(int[] left, int[] right) {
        int l = left.length;
        int r = right.length;
        int len = l + r;
        int[] res = new int[len];
        for (int index = 0, i = 0, j = 0; index < len; ) {
            if (i == l) {
                res[index++] = right[j++];
            } else if (j == r) {
                res[index++] = left[i++];
            } else if (left[i] < right[j]) {
                res[index++] = left[i++];
            } else {
                res[index++] = right[j++];
            }
        }
        return res;
    }

6. 快速排序

介绍

快速排序的基本思想: 通过一趟排序将待排序记录分割成独立的两部分, 其中一部分的关键字均比另一部分的关键字小, 则可分别对这两部分记录继续进行排序, 以达到整个序列有序.

算法时间复杂度 O(nlogn)

算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-list). 具体算法描述如下:

  • 从数列中跳出一个元素, 成为"基准"(pivot);
  • 重新排序数列, 所有元素比基准值小的摆放在基准前面, 所有元素比基准值大的摆放在基准的后面(相同的数可以到任一边). 在这个分区退出之后, 该基准就处于数列的中间位置. 这个成为分区(partition)操作.
  • 递归地(recursive)把小于基准元素的子数列和大于基准值元素的子数列排序

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

    /**
     * 快速排序
     */
    int[] quickSort(int[] array, int start, int end) {
        if (start < 0 || end >= array.length || start > end) {
            return null;
        }
        int smallIndex = partition(array, start, end);
        if (smallIndex > start) {
            quickSort(array, start, smallIndex - 1);
        }
        if (smallIndex < end) {
            quickSort(array, smallIndex + 1, end);
        }
        return array;
    }

    /**
     * 快速排序-分区
     */
    private int partition(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        swap(array, pivot, end);
        for (int i = start; i <= end; i++) {
            if (array[i] <= array[end]) {
                smallIndex++;
                if (smallIndex < i) {
                    swap(array, i, smallIndex);
                }
            }
        }
        return smallIndex;
    }

7. 堆排序

介绍

堆排序是指利用堆这种数据结构所设计的一种排序算法. 堆积是一个近似完全二叉树的结构, 并同时满足堆积的性质: 即子节点的键值或索引总是小于或者大于它的父节点.

算法时间复杂度为 O(nlogn)

算法描述

  • 将初始待排序关键字序列(R1, R2…Rn)构建成大顶堆, 此堆为初始的无序区;
  • 将堆顶元素R[1]与最后一个元素R[n]交换, 此时得到新的无序区 (R1,R2,……Rn-1)和新的有序区(Rn), 且满足R[1, 2…n - 1] <= R[n];
  • 由于交换后新的堆顶R[1]可能违反堆的性质, 因此需要对当前无序区(R1,R2…Rn-1)调整为新堆, 然后再次将R[1]与无序区最后一个元素交换, 得到新的无序区(R1,R2…Rn-2)和新的有序区(Rn-1, Rn). 不断重复此过程直到有序区元素的个数为n-1, 则整个排序过程完成.

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

    /**
     * 堆排序
     */
    int[] heapSort(int[] array) {
        int len = array.length;
        if (len < 1) {
            return array;
        }
        // 1.构建一个最大堆
        buildHeap(array, len);
        // 2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
        while (len > 0) {
            swap(array, 0, len - 1);
            len--;
            adjustHeap(array, 0, len);
        }
        return array;
    }

    /**
     * 建立最大堆
     */
    private void buildHeap(int[] array, int len) {
        // 从最后一个非叶子节点开始向上构造最大堆
        for (int i = (len - 1) / 2; i >= 0; i--) {
            adjustHeap(array, i, len);
        }
    }

    /**
     * 调整使之成为最大堆
     */
    private void adjustHeap(int[] array, int i, int len) {
        int maxIndex = i;
        // 如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (2 * i < len && array[2 * i] > array[maxIndex]) {
            maxIndex = 2 * i;
        }
        // 如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if (2 * i + 1 < len && array[2 * i + 1] > array[maxIndex]) {
            maxIndex = 2 * i + 1;
        }
        // 如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex, len);
        }
    }

8. 计数排序

介绍

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中. 作为一种线性时间复杂度的排序, 计数排序要求输入的数据必须是有确定范围的整数.

计数排序是一种稳定的排序算法. 计数排序使用了一个额外的数组C, 其中第i个元素是待排序数组A中值等于i的元素的个数.

然后根据数组C来将A中的元素排到正确的位置. 它只能对整数进行排序.

算法时间复杂度: O(n+k)

算法描述

  • 找出待排序的数组中最大和最小的元素;
  • 统计数组中每个值为i的元素出现的次数, 存入数组C的第i项;
  • 对所有的计数累加(从C中的第一个元素开始, 每一项和前一项相加);
  • 反向填充目标数组:将每一个元素i放在新数组的第C(i)项, 每放一个元素就讲C(i)减去1.

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

    /**
     * 计数排序
     */
    int[] countingSort(int[] array) {
        int len = array.length;
        if (len < 1) {
            return array;
        }
        int min = array[0], max = array[0], diff;
        for (int i : array) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        diff = 0 - min;
        int[] bucket = new int[max - min + 1];
        Arrays.fill(bucket, 0);
        for (int i : array) {
            bucket[i + diff]++;
        }
        int index = 0, i = 0;
        while (index < len) {
            if (bucket[i] != 0) {
                array[index++] = i - diff;
                bucket[i]--;
            } else {
                i++;
            }
        }
        return array;
    }

9. 桶排序

介绍

桶排序是计数排序的升级版. 它利用了函数的映射关系, 高效与否的关键就在于这个映射函数的确定.

桶排序的工作原理: 假设输入的数据服从均匀分布, 将数据分到有限数量的桶里, 每个桶再分别排序(有可能再使用别的排序算法或是递归方式继续使用桶排序进行排序)

算法时间复杂度: O(n2)

算法描述

  • 人为设置一个bucketSize, 作为每个桶所能放置多少个不同数值(例如当bucketSize = 5时, 该桶可以存放{1, 2, 3, 4, 5}这几种数字, 但是容量不限, 即可以存放100个3);
  • 遍历输入数据, 并且把数据一个个放到对应的桶中;
  • 对每个不是空的桶进行排序, 可以使用其他排序方法, 也可以递归使用桶排序;
  • 从不是空的桶里把排好序的数据拼接起来.

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

    /**
     * 桶排序
     */
    ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2)
            return array;
        int max = array.get(0), min = array.get(0);
        // 找到最大值最小值
        for (Integer value : array) {
            if (value > max)
                max = value;
            if (value < min)
                min = value;
        }
        int bucketCount = (max - min) / bucketSize + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        ArrayList<Integer> resultArr = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }
        for (Integer integer : array) {
            bucketArr.get((integer - min) / bucketSize).add(integer);
        }
        for (int i = 0; i < bucketCount; i++) {
            if (bucketCount == 1)
                bucketSize--;
            ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
            resultArr.addAll(temp);
        }
        return resultArr;
    }

10. 基数排序

介绍

基数排序也是非比较的排序算法, 对每一位进行排序, 从最低位开始排序. 复杂度为O(kn), n位数组长度, k为数组中的数的最大数的位数;

基数排序是按照低位先排序, 然后收集; 再按照高位排序, 然后再收集; 以此类推, 直到最高位.

有时候有些属性是有优先级顺序的, 先按低优先级排序, 再按高优先级排序. 最后的次序就是高优先级高的在前, 高优先级相同的低优先级高的在前.

基数排序基于分别排序, 分别收集, 所以是稳定的.

算法描述

  • 取得数组中的最大数, 并取得位数;
  • arr为原始数组, 从最低为开始取每个位组成radix数组;
  • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

    /**
     * 基数排序
     */
    int[] radixSort(int[] array) {
        int len = array.length;
        if (len < 2) {
            return array;
        }
        int max = array[0];
        for (int i : array) {
            max = Math.max(i, max);
        }
        int maxDigit = 0;
        while (max != 0) {
            maxDigit++;
            max /= 10;
        }
        int mod = 10, div = 1;
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            bucketList.add(new ArrayList<>());
        }
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int value : array) {
                int num = (value % mod) / div;
                bucketList.get(num).add(value);
            }
            int index = 0;
            for (ArrayList<Integer> integers : bucketList) {
                for (Integer integer : integers) {
                    array[index++] = integer;
                }
                integers.clear();
            }
        }
        return array;
    }

总结

各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：

img