排序算法
2017-12-01 本文已影响0人
bluarry
一。 初级排序算法
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 ~ N2/2次比较，时间复杂度为O(n2);
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. 几个改进技巧：
- 对小规模的数组使用插入排序
- 测试数组是否有序
- 不复制元素到辅助数
ps：简书不支持数学公式呀。。。凑合看吧
未完，待续。。。（写完时删掉此行）
