title: 排序算法整理

@Gizmosir 2016-03-15T02:51:59.000000Z 字数 4838 阅读 619

date: 2016-02-25
categories: Algorithms
tag: [sort, 排序]
mathjax: true
博客

引言

排序是算法中最基础的东西，很多时候都集成在语言或者支持库中。很多时候仅需简单地调用并可以完成排序操作，这也让越来越多的人不解学习排序的意义是什么。其实我个人觉得算法的核心在思路而非实现本身，通过比较简单的排序算法能够培养解决某类问题的思路。

简单地整理下比较常用的几个排序算法的思路以及实现，它们是：
1. Selection sort
2. Insertion sort
3. Shell sort
4. Merge sort
5. Quick sort

Selection sort（选择排序）

构思

假设我们需要对一个字符串文本 T 进行排序:
a l g o r i t h m

则该算法的思路：
1. 定义两个指针：i，j；
2. 使用j遍历 T 并找到最小的字符；
3. 将找到的最小的字符与i字符对换位置；
4. j++；
5. 循环 2 3 4 直至i到达 T 的末端。

实现

//Java 
public class Selection
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        for(int i = 0; i < N; i++)
        {
            int min = i;
            for(int j = i+1; j < N; j++)
                if(less(a[j], a[min]))
                    min = j;
            exch(a, i, min);
        }
    }
    private static boolean less(Comparable v, Comparable w)
    { return v.compareTo(w) < 0; }
    private static void exch(Comparable[] a, int i, int j)
    {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
 }

本文排序的算法实现主要参考于Robert [1]

分析

从代码中不难看出，Selection sort 算法中字符比较的次数为： $(N-1)+(N+2)+...+1+0$ ~ $N^2/2$ ，
字符互换的次数为： $N$ 。

所以其时间性能为： $O(N^2)$ ，但由于其是基于字符对换的排序算法，不需要额外的空间，所以其空间性能为： $O(N)$ 。

Insertion sort（插入排序）

构思

定义指针i；
i++;
如果新的字符比其左边小，则左移一位；
循环 3 至新的字符不比其左边的字符小；
循环 2 3 4 直至i到达 T的末端。

实现

//Java
public class Insertion
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                if(less(a[j], a[j-1]))
                    exch(a, j, j-1);
                else break;
    }
    private static boolean less(Comparable v, Comparable w)
    { /*与 Selection sort 代码中的一致*/ }
    private static void exch(Comparable[] a, int i, int j)
    { /*与 Selection sort 代码中的一致*/ }
}

分析

不同于Selection sort，Insertion sort 的运行时间与其需要排序的字符串有关。当待排序文本几乎处于已经正序的状态时，其只需 $N-1$ 次对比以及 $0$ 次字符互换；而当带排序文本处于完全反序的状态时，其需要 ~ $1/2 N^2$ 次比较以及 ~ $1/2 N^2$ 次互换。所以平均来说，Insertion sort 的时间复杂度为 $O(N^2)$ ，由于其同样是基于字符对换的排序算法，不需要额外的空间，所以其空间性能也为： $O(N)$ 。

Shell sort（希尔排序）

构思

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本 [2]

Shell sort与Insertion sort 算法实现思路基本一致，唯一不同的是后者使用步长为 1 的增量（即i每次只增加1位），而前者则使用变步长的增量（即i增加h位，以h为步长的排序通常也叫做h-sort）。

常见的增量步长：

$x^2$ ：1, 2, 4, 8, 16, 32, ...
$x^2 -1$ ： 1, 3, 7, 15, 31, ...
$3h + 1$ : 1, 4, 13, 40, 121, 363, ...
sedgewick: 1, 5, 19, 41, 109, 209, 505,...

采用不同增量步长将直接影响Shell sort的运行时间。使用上述中的sedgewick增量步长速度最快，然而由于该值不容易计算，所以实际应用中常使用稍慢一些但容易计算的 $3h+1$ 增量步长。

举例

假设我们需要对一个字符串文本 T 进行排序:
a l g o r i t h m
我们使用增量步长为 $3h+1$ 的Shell sort：
4-sort:
a l g o m i t h r
a i g o m l t h r
a i g o m l t h r
a i g h m l t o r
1-sort:
a i g h m l t o r
a i g h m l t o r
a g i h m l t o r
a g h i m l t o r
a g h i m l t o r
a g h i l m t o r
a g h i l m t o r
a g h i l m o t r
a g h i l m o r t

实现

//Java
public class Shell
{
    public static void sort(Comparable[] a)
    {   
        //h-sort
        int N = a.length;
        int h = 1;
        while(h < N/3) h = 3 * h + 1; // 3h + 1 步长方式
        while(h >= 1)
        {
            for(int i = h; i < N; i++)
            {
                for(int j = i; j >= h && less(a[j], a[j-h]); j -= h)
                    exch(a, j, j-h);  
            }
            h = h/3;
        }
    }
    private static boolean less(Comparable v, Comparable w)
    { /*与 Selection sort 代码中的一致*/ }
    private static void exch(Comparable[] a, int i, int j)
    { /*与 Selection sort 代码中的一致*/ }
}

分析

由于使用 $3h - 1$ 增量步长的原始的算法实现在最坏的情况下需要进行 $O(n^{3/2} )$ 的比较和交换。尽管V. Pratt的书[1]对算法进行了少量修改，可以使得性能提升至 $O(n log^2 n)$ 。但仍然比merge sort、quick sort等算法要慢许多。因为其实现起来较为简单，代码量也较少，所以shell sort 主要用于Linux系统或嵌入式系统中进行小型数组排序。

Merge sort（归并排序）

构思

将字符串完整复制到aux数组中；
将aux字符串数组分成前后两部分，并确定这两部分都已经排好序；
定义三个指针i、j、k，并使得前两个指针分别指向aux两部分的开头，k指向原数组的开头；
对比i、j指向的两个字符，并将最小的数替换k指向的数，并同时增加其与k的值；
当i或j其中一者超过原数组的一半大小时，表示还未排序的所有数都比以及排序的数要大，则直接将剩余未排序的数依次替换原数组。

在实际操作中，通常使用递归来依次对需要排序数组的一半进行排序。

实现

//Java
private class Merge
{
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi)
    {
        //先决条件： 前后两部分已经排好序！
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, hi);
        for(int k = lo; k <= hi; k++)
            aux[k] = a[k]; //复制
        int i = lo, j = mid+1;
        for(int k = lo; k <= hi; k++)
        {
            if     (i > mid)                a[k] = aux[j++];
            else if(j > hi)                 a[k] = aux[i++];
            else if(less(aux[j], aux[i]))   a[k] = aux[j++];
            else                            a[k] = aux[i++];
        }
        assert isSorted(a, lo, hi);
    }
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
    {
        if(hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid+1, hi);
        merge(a, aux, lo, mid, hi);
    }
    private static void sort(Comparable[] a)
    {
        aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }
}

分析

Merge sort 最多使用 $NlgN$ 次比较以及 $6NlogN$ 取值。但由于去需要将原数组完整拷贝依次，所以空间复杂度为 $O(2N)$ 。所以常用在对存储空间没有那么严格要求的排序中，如Java中的Object排序。

Quick sort（快速排序）

构思

“随机”选取一个字符V；
定义两个指针i和j，分别指向字符串的开头和结尾；
i++直至出现a[i]>V；
j--直至出现a[j]<V；
交互a[i]和a[j]；
重复3 4 5 直至i与j相错，并将V放于其中；
对V前后两个部分循环 2 3 4 5 6步骤进行排序；
递归并完成字符串排序。

实现

//Java
public class Quick
    private static int partition(Comparable[] a, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        while(true)
        {
            while(less(a[++i], a[lo]))
                if(i == hi) break;
            while(less(a[lo], a[--j]))
                if(j == lo) break;
            if(i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
    public static void sort(Comparable[] a)
    {
        //为了保证快速排序的速度，必须先对原数组进行打乱！
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1)
    }
    private static void sort(Comparable[] a, int lo, int hi)
    {
        if(hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1; hi);
    }
}

分析

Quick sort使用的最多的排序算法之一，其平均时间复杂度为 $O(NlgN)$ ，空间复杂度为 $O(N)$ 。但是保证去高效的一个必要条件是先对字符串进行打乱。否则最坏的情况下其时间复杂度将变成 $o(N^2)$ 。

当字符串长度很短的时候，由于其代价较大造成速度较慢，所以我们通常使用Insertion sort来排序。

另外“随机”选取的字符也很重要，越接近字符串的中间位置其速度越快，所以通常情况下使用以下代码来“随机”取值：

int m = medianOf3(a, lo, lo + (hi - lo) / 2, hi);
swap(a, lo, m);

当我们使用Quick sort排序的时候，遇到相同的值时我们会频繁的互换值并降低其速度，而当字符串中有大量的重复的值时，时间复杂度将会变成 $O(N^2)$ 。可以使用以下这种3-way quick sort来解决这个问题。

private static void sort(Comparable[] a, int lo, int hi)
{
    if(hi <= lo) return;
    int lt = lo, gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while(i <= gt)
    {
        int cmp = a[i].CompareTo(v);
        if      (cmp < 0)    exch(a, lt++, i++);
        else if (cmp < 0)    exch(a, i, gt--);
        else                 i++;
    }
    sort(a, lo, lt - 1);
    sort(a, gt + 1, hi);
}