排序

简单排序

假设

已经定义了判断大小；判断是否有序；交换次序这三种函数
本文是《算法》的笔记，java代码来自于书中

选择排序

找到数组中最小的元素，将它和第一个元素交换（如果它就是第一个元素，则自身和自身交换）。再次，在剩下的元素中找到最小的元素，将它与第二个元素交换。如此反复，直到将整个数组排序。
运行时间与输入无关，即使是有序的数组，它仍然需要不断遍历数组。
数据移动最少，每次都会改变两个数组元素的值，因此选择排序用了N次交换，与数组大小成线性关系。
示例代码：

public class Selection
{
    public static void sort(Comparable[] a)
    {//将a升序排列
    int N=a.length;
    for(int i=0;i<N;i++)
    {//将a[i]和a[i+1..N]中最小的元素交换
    int min=i;
    for(int j=i+1;j<N;j++)
        if (less(a[j],a[min]))min=j;
        exch(a,i,min)
    }
    }
}

void sort(Comparable *a,int asize)
{
    {//将a升序排列
    int N=aSize;
    for(int i=0;i<N;i++)
    {//将a[i]和a[i+1..N]中最小的元素交换
    int min=i;
    for(int j=i+1;j<N;j++)
        if (less(a[j],a[min]))min=j;
        exch(a,i,min)
    }
    return 0;
}

def sort(a):
    N=len(a)
    for i in range(N):
        min=i
        for j in range(i+1,N):
            if (less(a[j],a[min])):
                min=j;
        exch(a,i,min)

插入排序

将某个元素插入到已经有序的元素中。当索引到达数组的最右端时，排序结束。

运行时间取决于输入元素的初始顺序，当数组十分接近有序时，运行速度较快。

示例代码

public class Insertion
{
    public static void sort(Comparable[] a)
    {//将a升序排列
    int N=a.length;
    for(int i=1;i<N;i++)
    {//将a[i]插入到a[i-1]，a[i-2],a[i-3]...中
    for(int j=i;j>0&&less(a[j],a[j-1];j--))
    exch(a,j,j-1);
    }}
}

void Insertion(Comparable *a,int aSize)
{   //将a升序排列
    int N=aSize;
    for(int i=1;i<N;i++)
    {//将a[i]插入到a[i-1]，a[i-2],a[i-3]...中
    for(int j=i;j>0&&less(a[j],a[j-1]);j--)
    exch(a,j,j-1);
    }
}

def Insertion(a):
    N=len(a)
    for i in range(N):
        j=i
        while(j>0 and less(a[j],a[j-1])):
            exch(a,j,j-1)

当

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

插入算法的速度可能是所有算法中最快的。

只要将内循环中较大元素都向右移动而非交换两个元素时，速度会更快。

    Comparable temp=a[i]
    for(int j=i;j>0&&less(a[j],a[j-1]);j--)
    {a[j]=a[j-1];int u=j}
    a[u]=temp;

希尔排序

希尔排序基于插入排序。在插入排序中，将某一元素移动到正确位置需要经过最多N-1次（因为一次只能移动一个位置）

在希尔排序中，首先交换不相邻的元素以达到局部有序，然后将局部有序的数组排序。
希尔排序的思想是使数组中间隔为h的数组是有序的。如对数组a[0,1,2,3..N-1],使得a[0,h,2h,..],a[1,h+1,2h+1,..],...有序

希尔排序综合了数组的规模和有序性，可以看作增量不为1的插入排序。

h不需要取N的因数，即使有一些在起初没有“照顾”到的元素，在最后h为1时，都会成为它的因数。

代码如下：

public class shell
{
    public static void sort(Comparable[] a)
    {
        int N=a.length;
        int h=1;
        while(h<N/3)h=3*h+1;//1,4,13,40,...
        while(h>=1)
        {//将数组变为h有序
        for(int i=h;i<N;i++)
        {//将a[i]插入到a[i-h],a[i-2h],a[i-3h]中去
        for(int j=i;j>=h&&less(a[j],a[j-h]));j-=h)
        exch(a,j,j-h);
        }
        h=h/3;
        }
    }
}  

void sort(Comparable *a,int asize)
    {
        int N=aSize;
        int h=1;
        while(h<N/3)h=3*h+1;//1,4,13,40,...
        while(h>=1)
        {//将数组变为h有序
        for(int i=h;i<N;i++)
        {//将a[i]插入到a[i-h],a[i-2h],a[i-3h]中去
        for(int j=i;j>=h&&less(a[j],a[j-h]));j-=h)
        exch(a,j,j-h);
        }
        h=h/3;
        }
    }

def sort(a):
    int N=len(a)
    int h=1
    while(h<N/3):
        h=3*h+1
    while(h>=1):
        j=i
        for i in range(h,N):
            while(j>=h and less(a[j],a[j-h])):
                j-=h
                exch(a,j,j-h)
    h=h//3

希尔排序的速度依赖于h序列的选择，一些复杂的序列可能拥有更好的性能。

归并排序

将两个有序数组归并成一个更大的数组

时间复杂度满足O($logN$)，所需额外空间与N成正比

原地归并

归并的朴素想法是构建第三个数组，用来容纳两个有序数组的结果。但在排序过程中，需要多次归并。如果每次归并都多创造一个数组，会耗费巨大的空间。因此采取一种原地归并的算法。

public static void merge(Comparable[] a,int lo,int mid,int hi )
{//将a[lo..mid]和a[mid+1,hi]归并
    int i=lo,j=mid+1;
    for(int k=lo;k<=hi;k++)//将a[lo..hi]复制到aux[lo..hi]
        aux[k]=a[k];
    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++];
}

void merge(Comparable *a,int lo,int mid,int hi)
{   //将a[lo..mid]和a[mid+1,hi]归并
    int i=lo,j=mid+1;
    for(int k=lo;k<=hi;k++)//将a[lo..hi]复制到aux[lo..hi]
        aux[k]=a[k];
    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++];
}

def merge(a,lo,mid,hi):
    i=lo
    j=mid+1
    aux=a[:]
    for i in range(lo,hi):
        if i>mid:
            a[k]=aux[j]
            j+=1
        elif j>hi:
            a[k]=aux[i]
            i+=1
        elif less(aux[j],aux[i]):
            a[k]=aux[j]
            j+=1
        else:
            a[k]=aux[i]
            i+=1

以上四个判断的意义依次为：

1. 左边用尽，存入右边
2. 右边用尽，存入左边
3. 左边比右边大，存入右边

4. 右边比左边大，存入左边

   自顶向下的归并排序

   如果一个函数能够排列两个子数组，那么它就可以通过归并两个子数组对整个数组进行排序

public class Merge
{
    private static Comparable[] aux;
    public static void sort (Comparable[] a)
    {
        aux=new Comparable[a.length];
        sort(a,0,a.length-1);
    }
    private static void sort (Comparable[] a,int lo,int hi)
    {//将数组a[lo..hi]排序
    if(hi<=mid>)return;
    int mid=lo+(hi-mid)/2;
    sort(a,lo,mid);//排序左半边
    sort(a,mid+1,hi);//排序右半边
    merge(a,lo,mid,hi);//归并结果（见“原地归并排序”）
    }
}

void sort (Comparable *a,int lo,int hi,int aSzie)
{
    if(hi<=mid>)return;
    int mid=lo+(hi-mid)/2;
    sort(a,lo,mid);//排序左半边
    sort(a,mid+1,hi);//排序右半边
    Comparable *a=(Comparable *)malloc(sizeof(Comparable)*aSize);
    merge(a,lo,mid,hi);//归并结果（见“原地归并排序”）
}

def sort(a,lo,hi):
    if(hi<=mid>):
        return;
    mid=lo+(hi-mid)/2
    sort(a,lo,mid)
    sort(a,mid+1,hi)
    merge(a,lo,mid,hi)

对小规模子数组可以使用插入排序

时间可以缩短约10%——15%

可以判断数组是否有序

加判断条件a[mid]是否小于a[mid+1]，在某些情况下就可以跳过merge()函数

不将元素复制到辅助数组

这里指的是避免将元素复制到辅助数组的时间，并不是指避免辅助数组本身（即可以节省时间，但不能节省空间）
有两种方法

1. 将数据从输入数组排序到辅助数组

2. 将数据从辅助数组排序到输入数组

   自底向上的归并算法

   先归并微型数组，然后归并小数组，然后归并大数组，如此这般

public class MergeBU
{
    private static Comparable[] aux;
    public static void sort(Comparable[] a)
    {//进行lgN次归并
        int N=a.length;
        aux=new Comparable[N];
        for(int sz=1;sz<N;sz=sz+sz)//sz子数组大小
            for(int lo=0;lo<N-sz;lo+=sz+sz)//lo:子数组索引
                merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1);
    }
}

void sort(Comparable *a,int aSize)
{
    int N=aSize;
    Comparable *aux=(Comparable *)malloc(sizeof(Comparable)*N);
    for(int sz=1;sz<N;sz=sz+sz)//sz子数组大小
        for(int lo=0;lo<N-sz;lo+=sz+sz)//lo:子数组索引
            merge(a,lo,lo+sz-1,min(lo+sz+sz-1,N-1);
}

def sort(a):
    N=len(N)
    aux=a[:]
    while sz<N:
        for lo in range(0,N-sz,sz*2):
            merge(a,lo,lo+sz-1,min(lo+sz+sz-1,N-1))
        sz+=sz

当排序对象是用链表实现时，只需要重新组织链表，就能实现原地排序

归并排序的复杂度

数学证明略，可以知道排序算法最快时间复杂度是O($NlogN$),不可能存在比它还小的算法

但是归并算法还存在一些局限性

1. 空间复杂度不是最优的
2. 在实践中不一定会遇到最坏的情况
3. 除了比较，算法的其他操作（例如访问）也很重要
4. 不进行比较也能将某些数组排序

快速排序

快速排序的空间需要小，时间复杂度满足O($logN$)，但在某些情况下速度会降到O($N^2$)。

基本算法

快速排序是一种分治算法，将一个数组分为两个部分，再将两个部分分别排序。当两个子数组有序时，整体数组自然就有序了。

在归并算法中，数组被等分成两部分，递归在处理整个数组之前。在快速排序中，数组切分的位置取决于数组的内容，递归发生在处理整个数组之后。

实现代码

public Class Quick
{
    public static void sort(Comparable[] a)
    {
        StdRandom.shuffle(a);\
        sort(a,0,a.length-1);
    }
    private static 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);
    }
}

void quciksort(int *a,int aSize)
{
    StdRandom.shuffle(a);
    sort(a,0,aSize);
}
void sort(int 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);
}

def quicksort(a):
    random.shuffle(a)
    sort(a,0,a.length-1)
def sort(a,lo,hi):
    if(hi<lo):
        return
    j=partition(a,lo,hi)
    sort(a,lo,j-1)
    sort(a,j+1,hi)

切片算法一般选择a[lo]作为切片元素。定义两个指针，一个从左往右，一个从右往左，当左指针遇到一个大于等于它的元素，右指针遇到一个小于等于它的元素，就交换。当两个指针相遇时，返回左数组右边最大的数。

如果无法理解的话，可以写几个数组模拟这个过程。

代码实现：

private static int partition(Comparable[] a,int lo,int hi)
{//将数组切分为a[lo..i-1],a[i],a[i+1..hi]
    int i=lo,j=hi+1;//左右扫描数组
    Comparable v=a[0];//切分元素
    while(true)
    {//左右扫描，检查扫描是否结束并交换元素
    while(less(a[++i],v))if(i==hi)break;
    while(less(v,a[--j]))if(j==lo)break;
    if(i>=j)break;
    exch(a,i,j);
    }
    exch(a,lo,j);//将v=a[j]放到正确的位置
    return j;
}

int partition(int a*,int lo,int hi)
{//将数组切分为a[lo..i-1],a[i],a[i+1..hi]
    int i=lo,j=hi+1;//左右扫描数组
    Comparable v=a[0];//切分元素
    while(true)
    {//左右扫描，检查扫描是否结束并交换元素
    while(less(a[++i],v))if(i==hi)break;
    while(less(v,a[--j]))if(j==lo)break;
    if(i>=j)break;
    exch(a,i,j);
    }
    exch(a,lo,j);//将v=a[j]放到正确的位置
    return j;
}

def partition(a,lo,hi):
    i=lo
    j=hi+1
    v=a[0]
    while(ture):
        while(less(a[i],v)):
            a[i]+=1
            if(i==hi):
                break
        while(less(v,a[j])):
            a[j]-=1
            if(j==lo):
                break
        if(i>=j):
            break
        exch(a,i,j)
    exch(a,lo,j)
    return j

原地切分

如果创建一个辅助数组来进行切分，复制回去的开销可能得不偿失。

别越界

小心指针抛出数组边界

保持随机性

起初打乱数组有利于快速排序

终止循环

比如可能出现和切分元素相同的值，需要考虑

处理切分元素有重复的情况

以上方法可能出现等值交换，但可以避免时间复杂度降低到平方级

终止递归

合理选用切分元素，要保证切分元素被放入了正确的位置

算法改进

切换到插入排序

当数列较小时，可以选用快速排序
将if(hi<=lo)return修改为if(hi<=lo+M){Insertion.sort(a,lo,hi);return}

三取样切分

使用一部分子数组的中位数作为切分元素可能效果更好，但需要损耗计算中位数的时间。一般发现，取样大小为3的效果较好。

熵最优的排序

一些数组含有大量的重复元素，但快速排序仍然会对他们排序，可以适当修改。

比如对数组三切分，分为大于、等于、小于切片元素的部分。
感兴趣的可以自行搜索详细教程，这里仅附上java代码

public class Quick3way
{
    private static void sort(Comparable[] a,int lo,int hi)
    {
        if(hi<=lo)return;
        int lt=lo,i=lo+1,gt=hi;
        Comparable v=a[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,t-1);
        sort(a,gt+1,hi);
    }
}

其他一些关于优先序列的内容，也不能完全算排序，以后再更吧。