Algorithm

排序算法

排序算法分析和总结

Posted by 袁平 on October 6, 2018

前言

排序算法总结, 分析各种排序算法的时间复杂度, 空间复杂度, 使用场景和优化等方面

包括: 选择排序, 归并排序, 插入排序, 冒泡排序, 快排, 堆排, 基数排序, 希尔排序, 计数排序, 桶排序

文中代码使用Java实现, C/C++实现可以参见: https://github.com/HusterYP/DataStructure

正文

一. 选择排序

1.1 基本思路

找到数组中的最小元素, 将它和数组的第一个元素交换, 然后在剩下元素中找到最小元素和数组第二个元素交换, 如此往复, 直到有序

1.2 主要代码

public static void sort(int[] noSort) {
        if (noSort == null || noSort.length <= 0) // 边界条件
            return;
        int N = noSort.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (Utils.less(noSort[min], noSort[j]) < 0) // 注意此处比较条件, 不要写成noSort[i]和noSort[j]比较了
                    min = j;
            }
            Utils.exch(noSort, i, min);
        }
}

1.3 特点

  1. 时间复杂度: O(N^2); 需要进行(N-1)+(N-2)+...+1 = (N-1)*N/2次比较和N次交换

  2. 临界时间: 选择排序的最好情况与最坏情况时间相同, 同其时间复杂度分析(也可以说没有最好最坏情况)

  3. 空间复杂度: 1; 需要一个临时变量min

  4. 稳定性: 不稳定的; 如[5, 5, 2]

二. 插入排序

2.1 基本思路

从第一个元素开始, 该元素可认为已经被排序, 取出下一个元素, 在已排序元素序列中从后往前开始扫描, 插入到相应位置

2.2 主要代码

public static void sort(int[] noSort) {
        if (noSort == null || noSort.length <= 0)
            return;
        int N = noSort.length;
        for (int i = 1; i < N; i++) {
            int index = i;
            while (index > 0 && Utils.less(noSort[index], noSort[index - 1])) {
                Utils.exch(noSort, index, index - 1);
                index--;
            }
        }
}

2.3 特点

  1. 时间复杂度: O(N^2); 平均情况下需要N^2 / 4次比较和N^2 / 4次交换

  2. 临界情况: 最好情况是, 所有数据有序, 此时需要N-1次比较和0次交换; 最坏情况是所有数据逆序有序, 此时需要N^2 / 2次比较和N^2 / 2次交换(注意, 其实平均情况就是最坏情况对半, 因为每个位置每个元素出现几率相同)

  3. 适用情况: 对于部分有序的数组, 插入排序的效率很高; 部分有序数组:

  1. 数组中每个元素距离它的最终位置都不远
  2. 一个有序的大数组接一个小数组
  3. 数组中只有几个元素的位置不正确

  1. 空间复杂度: 1

  2. 稳定性: 稳定

三. 希尔排序

插入排序的改进

3.1 基本思路

使数组中任意间隔为h的数组都是有序的, 称为h有序数组; 类似插入排序, 但使用不同增量, 因为在插入排序中讲解适用性的时候说过, 插入排序在用于小数组的时候(可以理解为部分有序数组的第一种情况)很有效, 希尔排序就是将一个大数组按照h间隔分为许多小数组, 然后分别对这些小数组进行插入排序, 部分有序之后对整体进行插入排序(h=1), 此时即有序; 而这两种情况都适用于插入排序

h的选择, 1/2*(3^k-1), 从N/3递减至1, 如下代码

int h = 1;
while(h < N/3)
    h = h * 3 + 1;

3.2 基本代码

public static void sort(int[] noSort) {
        if (noSort == null || noSort.length <= 0)
            return;
        int N = noSort.length;
        int h = 1;
        while (h < N / 3)
            h = h * 3 + 1;
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && Utils.less(noSort[j], noSort[j - h]); j -= h)
                    Utils.exch(noSort, j, j - h);
            }
            h = h / 3;
        }
}

3.3 特点

  1. 时间复杂度: 优于插入排序; 取决于h的取值

  2. 空间复杂度: 1(h)

  3. 稳定性: 不稳定

  4. 适用情况: 希尔排序也可以用于大数组, 对任意排序(不一定是随机的)的数组表现也很好; 可以先考虑使用希尔排序, 然后再考虑是否值得将它替换为更加复杂的排序算法

四. 冒泡排序

4.1 基本思路

比较相邻元素, 如果第一个比第二个大, 就交换他们两个, 遍历所有元素, 一趟之后, 最后一个元素为最大元素; 对剩余元素重复该步骤(除了最后一个)

4.2 主要代码

public static void sort(int[] noSort) {
        if (noSort == null || noSort.length <= 0)
            return;
        int N = noSort.length;
        for (int i = N; i > 0; i--) {
            for (int j = 0; j < i - 1; j++) {
                if (Utils.less(noSort[j + 1], noSort[j]))
                    Utils.exch(noSort, j, j + 1);
            }
        }
}

4.3 特点

  1. 时间复杂度: O(N^2)

  2. 空间复杂度: 0

  3. 稳定性: 稳定

  4. 改进: 添加标志位, 如果一趟遍历中没有交换, 说明已经有序, 直接退出即可

public static void sort(int[] noSort) {
        if (noSort == null || noSort.length <= 0)
            return;
        int N = noSort.length;
        boolean isChange = true;
        for (int i = N; i > 0 && isChange; i--) {
            isChange = false;
            for (int j = 0; j < i - 1; j++) {
                if (Utils.less(noSort[j + 1], noSort[j])) {
                    Utils.exch(noSort, j, j + 1);
                    isChange = true;
                }
            }
        }
}

五. 归并排序

5.1 基本思路

递归排序, 先将一个数组分成两半分别排序, 然后将结果归并起来

5.2 主要代码

自顶向下的归并排序:

public class MergeSort {
    private static int[] aux; // 辅助数组

    public static void sort(int[] noSort) {
        if (noSort == null || noSort.length <= 0)
            return;
        aux = new int[noSort.length];
        sort(noSort, 0, noSort.length - 1);
    }

    public static void sort(int[] noSort, int low, int high) {
        if (high <= low)
            return;
        int mid = low + (high - low) / 2;
        sort(noSort, low, mid); // 将左半边数组排序
        sort(noSort, mid + 1, high); // 将右半边数组排序
        merge(noSort, low, mid, high); // 将数组归并
    }

    public static void merge(int[] noSort, int low, int mid, int high) {
        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) {
            aux[k] = noSort[k];
        }

        for (int k = low; k <= high; k++) {
            if (i > mid)
                noSort[k] = aux[j++]; // 如果左边用完
            else if (j > high)
                noSort[k] = aux[i++]; // 如果右边用完
            else if (Utils.less(aux[j], aux[i]))
                noSort[k] = aux[j++];
            else
                noSort[k] = aux[i++];
        }
    }
}

自底向下的归并排序:

public static void sortBU(int[] noSort) {
        int N = noSort.length;
        aux = new int[N];
        for (int sz = 1; sz < N; sz = sz + sz) {
            for (int low = 0; low < N - sz; low += sz + sz)
                merge(noSort, low, low + sz - 1, Math.min(low + sz + sz - 1, N - 1));
        }
}

5.3 特点

  1. 时间复杂度: O(NlogN); 归并排序是一种渐进最优的基于比较的排序算法; 能够保证O(NlogN)的时间复杂度(即最坏情况最好情况都相同)

  2. 空间复杂度: 需要与N成正比的额外数组空间

  3. 稳定性: 稳定

  4. 两种归并方式的区别: 自底向上的归并方式比较适合用链表组织的数据, 此时只需要重新组织链表链接就能将链表原地排序, 不需要额外空间

5.4 改进

  1. 对小规模子数组使用插入排序

  2. 测试数组是否已经有序: 如果noSort[mid] < noSort[mid+1]说明数组有序, 可以跳过本次merge()了

  3. 不将元素复制到辅助数组: 可以节省将元素复制到辅助数组所用的时间(但是空间不行), 即进行交替归并即可(可以添加一个标志位标识最终结果存储在哪个数组)

六. 快排

6.1 基本思路

对于某个j, a[j]已经排定, a[low]到a[j-1]中的所有元素都不大于a[j], a[j+1]到a[high]中的所有元素都不小于a[j]

6.2 主要代码

public class QuickSort {

    public static void sort(int[] noSort) {
        if (noSort == null || noSort.length <= 0)
            return;
        sort(noSort, 0, noSort.length - 1);
    }

    private static void sort(int[] noSort, int low, int high) {
        if (high <= low)
            return;
        int j = partition(noSort, low, high);
        sort(noSort, low, j - 1);
        sort(noSort, j + 1, high);
    }

    private static int partition(int[] noSort, int low, int high) {
        int i = low;
        int j = high + 1;
        int temp = noSort[low];
        while (true) {
            while (Utils.less(noSort[++i], temp))
                if (i == high)
                    break;
            while (Utils.less(temp, noSort[--j]))
                if (j == low)
                    break;
            if (i >= j)
                break;
            Utils.exch(noSort, i, j);
        }
        Utils.exch(noSort, low, j);
        return j;
    }
}

6.3 特点

  1. 时间复杂度: O(NlogN); 比归并和希尔排序都快

  2. 临界情况: 依赖于切分情况; 最好情况是每次都能将数组对半分; 最坏情况是第一次从最小元素切分, 第二次第二小元素切分, 如此这般, 每次调用都只能移除一个元素, 造成最坏情况(可以在开始排序之前, 现将待排序数组打乱(shuffle()))

  3. 空间复杂度: logN

  4. 稳定性: 不稳定

6.4 算法改进

  1. 小数组时切换到插入排序

  2. 三取样切分: 使用子数组的一小部分元素的中位数来切分数组, 这样切分更好, 但代价是需要计算中位数; 将取样大小设置为3并用大小居中的元素切分的效果更好; 还可以将取样元素放在数组末尾作为哨兵, 这样可以避免临界值判断

  3. 熵最优排序: 当含有大量重复元素的时候, 快排的递归性会使元素全部重复的子元素经常出现, 这就有很大的改进潜力, 将线性对数级的性能提高到线性级别; 一个简单的想法是将数组切分为三部分, 即小于, 等于和大于(荷兰国旗问题); 基本思路是: 维护一个指针lt使得a[low..lt-1]中的元素都小于v(切分元素), 一个指针gt使得a[gt+1..hi]中的元素都大于v, 一个指针i使得a[lt..i-1]中元素都等于v, a[i..gt-1]中元素都还未确定, 一开始i和low相等:

  1. a[i]小于v, 将a[lt]和a[i]交换, lt和i加一
  2. a[i]大于v, 将a[gt]和a[i]交换, 将gt减一
  3. a[i]等于v, 将i加一

三向切分改进代码如下: 三向切分的最坏情况是所有元素都不同; 在包含大量重复元素时, 其能将对数级别的时间降低到线性级别

public static void sort3Way(int[] noSort, int low, int high) {
        if (high <= low)
            return;
        int lt = low;
        int i = low + 1;
        int gt = high;
        int temp = noSort[low];
        while (i < gt) { // 找出重复元素
            if (noSort[i] < temp)
                Utils.exch(noSort, lt++, i++);
            else if (noSort[i] > temp)
                Utils.exch(noSort, i, gt--);
            else
                i++;
        }
        sort3Way(noSort, low, lt - 1);
        sort3Way(noSort, gt + 1, high);
}

七. 堆排

7.1 基本思路

堆是一个二叉树的每个节点都大于等于(或小于等于)它的两个子节点; 分为大顶堆和小顶堆

7.2 主要代码

注: 摘自Wiki

public class HeapSort {

    public static void sort(int[] arr) {
        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1;
        for (int i = beginIndex; i >= 0; i--) {
            maxHeapify(arr, i, len);
        }

        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for (int i = len; i > 0; i--) {
            Utils.exch(arr, 0, i);
            maxHeapify(arr, 0, i - 1);
        }
    }

    /**
     * 调整索引为 index 处的数据，使其符合堆的特性。
     *
     * @param index 需要堆化处理的数据的索引
     * @param len   未排序的堆（数组）的长度
     */
    private static void maxHeapify(int[] arr, int index, int len) {
        int li = (index << 1) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cMax = li;             // 子节点值最大索引，默认左子节点。

        if (li > len) return;       // 左子节点索引超出计算范围，直接返回。
        if (ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
            cMax = ri;
        if (arr[cMax] > arr[index]) {
            Utils.exch(arr, cMax, index);
            maxHeapify(arr, cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }
}

7.3 特点

  1. 时间复杂度: 堆排序是唯一能够同时最优的利用空间和时间的方法, 在最坏情况下它也能保证O(NlogN)的时间复杂度和恒定空间

  2. 空间复杂度: O(1)

  3. 适用场景: 在空间十分紧张(如嵌入式设别或低成本的移动设备中)十分流行, 但是由于其数据变更比较频繁, 因此无法利用缓存(缓存命中率比较低), 在现代系统的许多应用中很少使用

  4. 稳定性: 不稳定

  5. 使用堆还可以实现优先队列, 使得当有大量数据时, 可用较少空间即可从中筛选出指定数量的最大(小)K个数据

八. 小结

上面介绍的七个排序算法都是基于比较的, 这里再以表的形式总结如下:

排序算法 是否稳定 是否为原地排序 时间复杂度 空间复杂度
选择排序 否 是 N^2 1
插入排序 是 是 介于N和N^2之间 1
希尔排序 否 是 未知(NlogN / N^(5/6) ?) 1
快排 否 是 NlogN logN
三向快排 否 是 介于N和NlogN之间 logN
归并排序 是 否 NlogN N
堆排 否 是 NlogN 1

下面要介绍的是线性排序; 有这样一个结论是: 没有任何基于比较的算法能够保证使用少于log(N!) ~ NlogN次比较将长度为N的数组排序; 所以这也决定了上面基于比较的排序算法的上界;

九. 计数排序

参考博客

十. 基数排序

参考博客

十一. 桶排序

参考博客

FEATURED TAGS
Algorithm Java Android Hust 操作系统 View Note iOS
FRIENDS