三大屌丝排序

其实好久没摸算法和数据结构了,今拾排序一练.

说到排序,不得不提及冒泡排序,因为它是最简单也是最屌丝的排序算法:

void Bubble(int *p,int n) {
    for(int i=1;i<n;i++) {
        for(int j=i;j>0 && p[j]<p[j-1];j--) {
            p[j]+=p[j-1];
            p[j-1]=p[j]-p[j-1];
            p[j]-=p[j-1];
        }
    }
}

算法复杂度为O(N^2),但胜在稳定,简单.够屌丝.

插入排序:

void Insert(int *p,int n) {
    for(int i=1;i<n;i++) {
        int pos=0;
        for(;pos<i && p[i]>=p[pos];pos++){}
        if(i!=pos) {
            int val=p[i];
            memmove(&p[pos+1],&p[pos],(i-pos)*sizeof(int));
            p[pos]=val;
        }
    }
}

和冒泡排序极为相似,其算法复杂度也是O(N^2),但相对冒泡排序来说减少了很多交换操作.在链表等数据结构中使用效果更佳.

快速排序:

void Quick(int p,int n) {
    if(n<2) {
        return ;
    }
    int left[MAX]={0},right[MAX]={0},r=0,l=0,val=p[0];
    for(int i=1;i<n;i++) {
        if(p[i]<val) {
            left[l++]=p[i];
        } else {
            right[r++]=p[i];
        }
    }
    Quick(left,l);
    Quick(right,r);
    p[l]=val;
    memcpy(p,left,sizeof(int)l);
    memcpy(&p[l+1],right,sizeof(int)*r);
}

由于使用了数据结构中的堆积树思想,算法复杂度降低到O(NlogN).