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

(本文属于排序算法总结,并非零基础讲解。更多内容可以参考: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 三路快排的优势是什么?

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