排序算法（不稳定）

不稳定排序

---

1.选择排序
2.快速排序
3.希尔排序
4.堆排序

---

选择排序

int A[M];
void sort(){
    FOR(i,1,n){
        k=i;
        FOR(j,i+1,n)//在[i+1,n]的范围找到最小值的下标 
            if(A[j]<A[k])k=j;
        if(k!=i)swap(A[i],A[k])//第i个数与最小值交换 
    }
}

复杂度为O(n^2)

---

快速排序

int A[M];
void sort(int L,int R) {
    if(L>=R)return ;
    int i=L,j=R,key=A[L];
    while(i<j) {
        while(i<j&&A[j]>=x)--j;//滑动右边指针
        if(i<j)A[i++]=A[j];
        while(i<j&&A[i]<=x)++i;//滑动右边指针
        if(i<j)A[j--]=A[i];
    }
    A[i]=key;
    sort(l,i-1);
    sort(i+1,r);
}

首先任意选取一个数据（key）作为关键数据，
将所有比它小的数都放到它前面，所有比它大的数都放到它后面,
然后再递归对这两部分进行排序。
平均复杂度是O(nlogn)
最坏情况O(n^2)（有序数组）,为了避免这种情况，可以随机取key的位置。
STL调用的sort函数比手打的快排一般要快
扩展用法：求序列中第K大数。

---

希尔排序

int A[M];
void sort(){
    int n,i,j,k,step,tmp;
    for(step=n/2;step>0;step/=2) //增量
        for(i=step;i<n;i++)
            if(A[i]<A[i-step]){
                tmp=A[i];k=i-step;
                while(k>=0&&A[k]>tmp){
                    A[k+step]=A[k];
                    k-=step;
                }
                A[k+step]=tmp;
            }
}

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，
当增量减至1时，整个文件恰被分成一组，算法便终止。
复杂度存在争议，下限是O(nlogn)，平均O(n^1.5)

---

堆排序

struct Heap {
    int W[M];
    int sz;
    void push(int x) {
        int p=++sz,q;
        while(q=p>>1) {
            if(x<W[q]) W[p]=W[q],p=q;
            else break;
        }
        W[p]=x;
    }
    void pop() {
        int p=1,q;
        int x=W[sz--];
        while((q=p<<1)<=sz) {
            if(q<sz && W[q|1]<W[q]) q|=1;
            if(W[q]<x) W[p]=W[q],p=q;
            else break;
        }
        W[p]=x;
    }
    int top() {return W[1];}
    bool empty() {return sz==0;}
}Q; 

堆排序就是利用堆来实现排序
堆能实现数据的插入和删除都在logn的时间内完成
STL里的priority_queue优先队列
或者(make_heap, pop_heap, push_heap, >sort_heap）
也可以实现这一功能,不过手打的堆一般要快一些
复杂度：O(nlogn)

---