现在位置: 首页 / 算法笔记 / 排序 / 正文

一文总结常见基础排序算法

（本文属于排序算法总结，并非零基础讲解。更多内容可以参考：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html）

0 前言

个人总结的常见基础排序算法，罗列如下：

  • 简单排序，时间复杂度 O(N2)：冒泡排序、选择排序、插入排序
  • 高级排序，时间复杂度 O(NlogN)：归并排序（自顶向下、自底向上）、快速排序（含3路快排）、堆排序

像希尔排序、桶排序，我感觉代表性稍微弱一些。本文不讨论。

1 简单排序

1.1 冒泡排序

思想

冒泡排序可能是大多数人学习的第一种排序算法，非常有名。

对数组做 n 次遍历，每次遍历就是一次“冒泡”。在遍历过程中，对相邻的元素做两两比较，如果两者顺序不对，就做一次交换。每次“冒泡”遍历结束后，最大的那个元素就跑到数组末尾了。

实际实现的时候，有两种做法：（1）每轮冒泡，把最大的元素选出来，放到末尾；（2）每轮冒泡，把最小的元素选出来，放到最前面。

代码

public class BubbleSort implements Sort {
    @Override
    public int[] sort(int[] input) {
        for (int i = 0; i < input.length; i++) {
            for (int j = 0; j < input.length - i - 1; j++) {
                if (input[j+1] < input[j]) {
                    SortHelper.swap(input, j, j+1);
                }
            }
        }
        return input;
    }
}

1.2 选择排序

思想

做 N 次遍历，每次都选出当前范围的最小值，与最前面的元素做交换。

代码

public class SelectionSort implements Sort {
    @Override
    public int[] sort(int[] input) {
        for (int i = 0; i < input.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < input.length; j++) {
                if (input[j] < input[minIndex]) {
                    minIndex = j;
                }
            }
            SortHelper.swap(input, i, minIndex);
        }
        return input;
    }
}

1.3 插入排序

思想

这是我们玩扑克牌时常用的排序方式。从头到尾做一次遍历，对于遇到的每一个元素，都向前找到合适的位置插入，保证插入后的有序性。遍历结束后，整个数组就变得有序了。

代码

public class InsertionSort implements Sort {
    @Override
    public int[] sort(int[] input) {
        for (int i = 1; i < input.length; i++) {
            int val = input[i];
            int j = i-1;
            while (j >= 0 && input[j] > val) {
                input[j+1] = input[j];
                j--;
            }
            input[j+1] = val;
        }
        return input;
    }
}

2 高级排序

2.1 归并排序

思想

分治思想。

自顶向下：把数组一分为二，先对左边部分进行排序，然后对右边部分进行排序。最后把两部分有序的数组合并起来。

自底向上：设定一个从1开始逐步倍增的 size，以 size 为单位每次划分出两个有序数组，进行归并。

代码

自顶向下：

public class MergeSort implements Sort {
    @Override
    public int[] sort(int[] input) {
        mergeSort(input, 0, input.length-1);
        return input;
    }

    private void mergeSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int m = l + (r-l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }

    /**
     * 对 arr[l, m] 和 arr[m+1, r] 进行归并
     */
    private void merge(int[] arr, int l, int m, int r) {
        int[] tmp = new int[r-l+1];
        int k=0, i=l, j=m+1;
        while (i <= m || j <= r) {
            if (i > m) {
                tmp[k++] = arr[j++];
                continue;
            }
            if (j > r) {
                tmp[k++] = arr[i++];
                continue;
            }
            if (arr[i] < arr[j]) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
        System.arraycopy(tmp, 0, arr, l, r-l+1);
    }
}

自底向上：

public class MergeSortBU implements Sort {
    @Override
    public int[] sort(int[] input) {
        for (int size = 1; size < input.length; size += size) {
            for (int i = 0; i + size < input.length; i += 2*size) {
                int m = i + size - 1;
                merge(input, i, m, Math.min(i+2*size-1, input.length-1));
            }
        }
        return input;
    }

    private void merge(int[] arr, int l, int m, int r) {
        int[] tmp = new int[r-l+1];
        int k = 0;
        int i = l;
        int j = m+1;
        while (i <= m || j <= r) {
            if (i > m) {
                tmp[k++] = arr[j++];
                continue;
            }
            if (j > r) {
                tmp[k++] = arr[i++];
                continue;
            }
            if (arr[i] < arr[j]) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
        System.arraycopy(tmp, 0, arr, l, r-l+1);
    }
}

2.2 快速排序

思想

仍然是分治思想。

  • 经典快排：选一个值作为轴值（pivot，一般选择第一个元素就行），通过一次遍历把数组一分为二，左边的元素都 <= pivot，右边的元素都 > pivot。然后再分别都左边和右边应用快速排序。
  • 三路快排：选一个值作为轴值，通过一次遍历，把数组分为三个部分（<pivot，=pivot，>pivot）。

代码

经典快排：

public class FastSort implements Sort {
    @Override
    public int[] sort(int[] input) {
        fastSort(input, 0, input.length-1);
        return input;
    }

    private void fastSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int pivot = partition(arr, l, r);
        fastSort(arr, l, pivot);
        fastSort(arr, pivot + 1, r);
    }

    private int partition(int[] arr, int l, int r) {
        // 定义：
        // arr[l+1, i] 都小于 v
        // arr[i+1, j] 都大于等于 v
        int v = arr[l];
        int i = l;
        for (int j = l+1; j <= r; j++) {
            if (arr[j] < v) {
                SortHelper.swap(arr, ++i, j);
            } else {
                // do nothing
            }
        }
        SortHelper.swap(arr, l, i);
        return i;
    }
}

三路快排：

public class FastSortThreePath implements Sort {
    @Override
    public int[] sort(int[] input) {
        fastSortThreePath(input, 0, input.length-1);
        return input;
    }

    private void fastSortThreePath(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }

        // partition
        int v = arr[low];
        // 定义：
        // arr[low+1, l] 都是 < v
        // arr[l, i] 都是 = v
        // arr[r, high] 都是 > v
        int l = low;
        int r = high + 1;
        for (int i = low + 1; i < r;) {
            if (arr[i] < v) {
                SortHelper.swap(arr, i++, ++l);
            } else if (arr[i] > v) {
                SortHelper.swap(arr, i, --r);
            } else {
                i++;
            }
        }
        SortHelper.swap(arr, l, low);

        fastSortThreePath(arr, low, l-1);
        fastSortThreePath(arr, r, high);
    }
}

2.3 堆排序

思想

首先把数组构造成一个大顶堆（这个过程叫 heapify），不停地把堆顶元素与最后一个元素交换位置，堆的大小减1，做 sink 操作。直到这个堆消失为止。

代码

public class HeapSort implements Sort {
    @Override
    public int[] sort(int[] input) {
        // 1. 构造一个下标从 0 开始的大顶堆
        int N = input.length;
        for (int k = (N-2)/2; k >= 0; k--) {
            sink(input, k, N);
        }

        // 2. 排序
        while (N > 0) {
            SortHelper.swap(input, 0, --N);
            sink(input, 0, N);
        }
        return input;
    }

    private void sink(int[] arr, int k, int N) {
        while (k*2+1 < N) {
            int j = k*2+1;
            if (j+1 < N && arr[j+1] > arr[j]) {
                j = j+1;
            }
            if (arr[k] >= arr[j]) {
                break;
            }
            SortHelper.swap(arr, k, j);
            k = j;
        }
    }
}

3 全部代码

已上传 github。

https://github.com/plough/sort-algorithms

4 答疑

4.1 高级排序一定更好吗？

不一定。

  • 对于数据量较小的场景，时间复杂度中常数项的影响较大，简单排序算法的效率可能更高。
  • 简单排序算法容易实现，不易出现bug，对于需要手写算法的情况下（例如某些嵌入式场景），是首选。

4.2 归并排序和快速排序的对比

两者都使用了分治思想，递归。

  • 归并排序是稳定的，快速排序是不稳定的。
  • 归并排序需要使用额外空间，快速排序是原地排序。
  • 极端情况下，快速排序的时间复杂度可能会退化到 O(N2)。
  • 一般而言，快排比归并排序要快一点点。（不然为啥叫它快速排序呢？）

4.3 三路快排的优势是什么？

对于数组中存在大量重复元素的情况，使用三路快排是远远优于原始快排的。