一。 初级排序算法

---

1. 选择排序

(1). 简单描述: 首先找到数组中最小的元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素,那么就和自己交换),再次，在剩下的元素中找到最小的元素，将它与数组第二个元素交换。如此往复,直到整个数组有序

(2). 算法实现伪代码

void SelectSort(a[],N){
    for(int i=0;i<N;i++){
        int m=i;
        for(int j=i+1;j<N;j++)
            if(a[j] < a[m]) m=j;
        swap(a,i,m);
    }
}

(3). 复杂度分析

通过分析,对于一个长度为N的数组,0~N-1的任意一个i都会进行1次交换和N-1次比较，因此总共有N次交换以及(N-1)+(N-2)+……+2+1 = N*(N-1)/2 ~ N^{2/2次比较，时间复杂度为O(n}2);

2.插入排序算法

(1). 简单描述：为了给要插入的元素腾出空间，我们需要将其余所有元素插入之前都向右移动一位。

(2). 算法实现伪代码

void InsertSort(a[],N){
    for(int i=0;i<N;i++)
        for(int j=i;j>0 && a[j] < a[i];j--) swap(s,j,j-1);
}

(3). 复杂度分析

对于长度为N且主键不重复的数组，平均情况下插入排序需要 ~ N^2/4 次比较以及 ~ N^2/4次交换，最坏情况下需要 ~N^2/2 次比较和 ~N^2/2 次交换。最好情况下需要 N-1次比较和0次交换

3.希尔排序

(1). 简单描述: 希尔排序为一种改进的插入排序,算法思想为：使数组中任意间隔为h的元素都是有序的，h由大到小，最后必须为1.这样权衡了子数组的规模和有序性，，可改进插入排序.

(2). 实现代码：

void ShellSort(a[],N){
    int h=1;
    while(h<N/3)h=h*3+1;
    while(1){
        for(int i=h;i<N;i++)
            for(int j=i;j>=h&&a[j] < a[j-h];j-=h)
                swap(a[j],a[j+h]);
        h/=3;
    }
}

(3). 算法分析

该算法的数学论证较复杂，和h的选择有密切关系，如使用算法有给出的序列，那么比较的次数不会超出$$N$$的若干倍乘以倍增序列的长度，对于中等大小的数组，它的运行时间是可以接受的，它代码量小，且不需要额外的内存空间。

---

二。归并排序

---

1. 思想描述:

首先将数组对半分为两个子数组，递归的利用归并排序完成子数组的排序，然后将两个已排好序的子数组合并即可。

2. 将两个子数组合并算法Merge()实现:

void Merge(a[],lo,mid,hi,b[]){
    int i=lo,j=mid+1;
    for(int k=lo;k<=hi;k++)b[k]=a[k];
    for(int k=lo;k<=hi;k++){
        if(i > mid)             a[k]=b[j++];
        else if(i>hi)           a[k]=b[i++];
        else if(b[j] < b[i])    a[k]=b[j++];
        else                    a[k]=b[i++]; 
    }
}

3. 自顶向下的归并排序实现

1. 算法代码实现

void sort(a[],b[],N){
    mysort(a,0,N-1,b);
}
void mysort(a[],lo,hi,b[]){
    if(hi <=lo ) return;
    int mid=lo+(hi-lo)/2;
    mysort(a,lo,mid);
    mysort(a,mid+1,hi);
    Merge(a,lo,mid,hi,b);
}

2. 复杂度分析:

对于一个长度为N的数组，归并排序需要$$(1/2NlgN)-(NlgN)$$次比较

证明: 令C(N)表示将数组排序是比较次数，显然，C(0)=C(1)=0;通过递归调用mysort, 可得上限为:$$ C(N) <= C(lceil(N/2))+C(lfloor(N/2))+N $$

左边第一项为排序左半部分比较次数，第二项为有半部分的比较次数，第三项为归并是需要的比较次数，比较次数最少为 $$ lfloor(N/2) $$ ，所以下限为 $$ C(N) >= C(lceil(N/2))+C(lfloor(N/2))+ lfloor(N/2) $$

假定 $$ N=2^N $$

3. 几个改进技巧：

1. 对小规模的数组使用插入排序
2. 测试数组是否有序
3. 不复制元素到辅助数

---

---

ps：简书不支持数学公式呀。。。凑合看吧

未完，待续。。。（写完时删掉此行）