[算法]内排序专题

各种内排序有各自的优缺点，再次总结一下。

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n²)	O(n²)	稳定	O(1)	n小时较好
交换	O(n²)	O(n²)	不稳定	O(1)	n小时较好
选择	O(n²)	O(n²)	不稳定	O(1)	n小时较好
插入	O(n²)	O(n²)	稳定	O(1)	大部分已排序时较好
基数	O(log_RB)	O(log_RB)	稳定	O(n)	B是真数(0-9)， R是基数(个十百)
Shell	O(nlogn) O(n^1.25) ???	O(n^s) 1<s<2	不稳定	O(1)	s是所选分组
快速	O(nlogn)	O(n²)	不稳定	O(nlogn)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好

1、快速排序

　　选择数组的其中一个元素(一般为第一个)作为分界pivot，用两个游标分别从后往前和从前往后扫描数组。先从后游标开始，当后游标所指的值比pivot小，则与pivot交换，后游标交换后才扫描前游标；当前游标所指值比pivot大，则与pivot交换。一次分组的结果是pivot前面的元素全部比pivot小，后面的全部比pivot大。既然对前后两部分继续调用分组函数即可完成排序。

　　下面的程序对上述过程做了优化，交换的时候直接把游标所指的值覆盖到pivot的位置上，覆盖后，原来游标所指的位置作为下一次的pivot位置，准备被下一次调换时被覆盖。当前后两个游标相遇时，此位置就是pivot值在有序数组中的位置了。此优化其实就是利用了pivot的位置进行元素交换，避免了使用多余的空间。

int partition(int *p,int begin,int end){
    int ipivot=begin;
    int pivot=p[begin];
    begin++;
    while(begin<=end){
        while(begin<=end && p[end]>=pivot){
            end--;
        }
        if(begin<=end){
            p[ipivot]=p[end];
            ipivot=end;
            end--;//这里不用忘记了
        }
        while(begin<=end && p[begin]<=pivot){
            begin++;
        }
        if(begin<=end){
            p[ipivot]=p[begin];
            ipivot=begin;
            begin++;//这里不用忘记了
        }
    }
    p[ipivot]=pivot;
    return ipivot;
}

void myqs(int *p,int begin,int end){
    if(begin>=end){
        return;
    }
    int ipivot=partition(p,begin,end);
    myqs(p,begin,ipivot-1);
    myqs(p,ipivot+1,end);
}

2、堆排序

　　堆排序适合于数据量非常大的场合（百万数据）。
　　堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
　　堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

//插入堆数据网上调整   //对堆插入数据的时候用，插入的数据放在数组最后
/*void adjust_minheap_up(int *heap,int i){
    int father=(i-1)/2;
    int cur=i;
    while(father>=0){
        if(heap[cur]<heap[father]){
            heap[cur]^=heap[father];
            heap[father]^=heap[cur];
            heap[cur]^=heap[father];
            if(father==0){
                break;
            }
            cur=father;
            father=(cur-1)/2;
        }else{
            break;
        }
    }
}*/

//把不符合最小堆的元素i往下调整，把左右子节点中较小的跟i交换。
//然后接着调整位于子节点中的需调整节点
void adjust_minheap_down(int *heap,int len,int i){
    int target=2*i+1;
    int tmp=heap[i];//临时存放需调整元素，提高交换时效率
    while(target<len){//有左儿子
        if(target+1<len && heap[target+1]<heap[target]){
            target++;//右儿子存在且比左儿子小，则取右儿子
        }
        if(heap[target]>tmp){//左右儿子都比tmp小，调整结束
            break;
        }
        heap[i]=heap[target];//把较小的移到父节点
        i=target;//更新下一个处理节点
        target=2*i+1;//更新target为目标节点的左儿子
    }
    heap[i]=tmp;//找到合适位置后，放回目标节点
}

//由数组创建最小堆
void make_min_heap(int *data,int len){
    int i;
    for(i=len/2-1;i>=0;i--){//叶子节点不需调整，从最后一个非叶节点开始（最后一个节点的父节点((n-1)-1)/2）
        adjust_minheap_down(data,len,i);
    }
}

//堆排序：先把数组构成一个最小堆。把堆顶最小的数与堆末的数对调
//然后整理0到len-1的堆。这样，最小的数就累积到数组后段，并不再调整
//因此，使用最小堆的堆排序是降序排序。升序排序需要使用最大堆。
void heap_sort(int *heap,int len){
    make_min_heap(heap,len);
    int i;
    for(i=len-1;i>=1;--i){
        heap[0]^=heap[i];
        heap[i]^=heap[0];
        heap[0]^=heap[i];
        adjust_minheap_down(heap,i,0);
    }
}

平时的时候想要使用堆，或者面试的时候，马上写出个堆够麻烦的，其实STL的优先队列就是用堆实现的，完全可以用优先队列简单实现一个堆，下面就是使用优先队列进行堆排序的例子。

注意：优先队列默认是最大的在top，如要构造最小堆，需加入堆的基础数据结构类型（vector<int>）和greater<int>

//flag=0 is ascend,1 is descend
void heap_sort_STL(int *p,int len,int flag){
    int i;
    if(!flag){//descend use min heap
        priority_queue<int,vector<int>,greater<int> > min_heap(p,p+len);
        for(i=0;i<len;++i){
            p[i]=min_heap.top();
            min_heap.pop();
        }
    }else{
        priority_queue<int> max_heap(p,p+len);//默认是大顶堆
        for(i=0;i<len;++i){
            p[i]=max_heap.top();
            max_heap.pop();
        }
    }
}

2 归并排序（MergeSort）

　　归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组（最大额外空间为原数组大小）。

//end表示最后一个元素的下一个位置
void merge(int *p,int begin,int mid,int end){
    if(begin+1==end){
        return;
    }
    int *tmp=new int[end-begin];
    int i1=begin,i2=mid,i=0;
    while(i1<mid && i2<end){
        if(p[i1]<p[i2]){
            tmp[i]=p[i1];
            i1++;
        }else{
            tmp[i]=p[i2];
            i2++;
        }
        i++;
    }
    while(i1<mid){
        tmp[i++]=p[i1++];
    }
    while(i2<end){
        tmp[i++]=p[i2++];
    }
    for(i=0;i<end-begin;++i){
        p[begin+i]=tmp[i];//注意0并非原始数组的开头
    }
    delete []tmp;
}

//end表示最后一个元素的下一个位置
void merge_sort(int *p,int begin,int end){
    if(begin+1==end){
        return;
    }
    int mid=(end+begin)/2;//注意，使用加法除2可避免偏移量问题
    merge_sort(p,begin,mid);
    merge_sort(p,mid,end);
    merge(p,begin,mid,end);
}

4 Shell排序（ShellSort）
　　Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序（shell是插入排序的改进），以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。

　　Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

//0,increment,2*increment,....为一组。开始的时候分为较多组，每组元素较少
//最后increment为1，就是每两个为一组，把整个数组分为两组，进行插入排序
void shell_sort(int *p,int len){
    int increment=len;
    int i,j;
    do{
        increment=increment/3+1;//一般取这个增量
        for(i=increment;i<len;++i){
            for(j=i-increment;j>=0 && p[j]>p[j+increment];j-=increment){
                p[j]^=p[j+increment];//把分组中较大的元素往前移
                p[j+increment]^=p[j];//直到前面的元素比它小即可停止循环
                p[j]^=p[j+increment];//因为前面的元素已经是有序的了
            }
        }
    }while(increment>1);
}