排序算法

2021-01-12

直接插入排序

//直接插入排序,一定注意哨兵的作用
//a[0]位哨兵
int a[11]={0,4,5,3,6,2,8,1,16,19,17};
int main(){
    int n=10;
    for(int i=2;i<=n;i++){
        if(a[i]<a[i-1]){
            //复制待插入元素为哨兵，然后用其他元素向后顶掉它的位置
            a[0]=a[i];
            int j;
            for(j=i-1;a[j]>a[0];j--){
                a[j+1]=a[j];//右移
            }
            a[j+1]=a[0];
        }
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
}

归并排序

//归并排序
vector<int> a={4,5,3,6,2,8,1,16,19,17};
vector<int> b;
void Merge(int l,int mid,int r){
    //复制,b用来比较，a用来求值
    b=a;
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(b[i]<b[j]){
            a[k++]=b[i++];
        }
        else{
            a[k++]=b[j++];
        }
    }
    while(i<=mid){
        a[k++]=b[i++];
    }
    while(j<=mid){
        a[k++]=b[j++];
    }
}

void mergesort(int l,int r){
    if(l>=r) return;
    int mid=(l+r)/2;
    //这两步使两边分别有序，然后就可以归并排序了
    mergesort(l,mid);
    mergesort(mid+1,r);
    Merge(l,mid,r);
}

int main(){
    mergesort(0,9);
    for(int i=0;i<=9;i++){
        cout<<a[i]<<" ";
    }
}

快速排序

//快速排序
vector<int> a={4,5,3,6,2,8,1,16,19,17};


int Partition(int l,int r){
    int temp=a[l];
    while(l<r){
        //注意内层的while也要加上l<r的条件!!
        while(l<r&&a[r]>temp) --r;
        a[l]=a[r];
        while(l<r&&a[l]<temp) ++l;
        a[r]=a[l];
    }
    a[l]=temp;
    return l;
}


void fastsort(int l,int r){
    if(l>=r) return ;
    int pivot=Partition(l,r);//划分
    fastsort(l,pivot-1);
    fastsort(pivot+1,r);
}


int main(){
    fastsort(0,9);
    for(int i=0;i<=9;i++){
        cout<<a[i]<<" ";
    }
}

堆排序

//堆排序
vector<int> a={-1,4,5,3,6,2,8,1,16,19,17};

//关键部分，向下调整,k的含义是当前这个元素准备存放的位置
void adjustdown(int k,int len){
    int temp=a[k];
    //用for相当于是沿着子树一直向下遍历左子
    for(int j=2*k;j<=len;j*=2){
        //判断儿子中最大的
        if(j+1<=len&&a[j+1]>a[j]) j++;
        if(a[j]<temp) break;
        else{
            //从变动的结点继续向下，为temp找到合适的位置
            a[k]=a[j];
            k=j;
        }
    }
    a[k]=temp;//放入最终位置
}


void BuildMaxheap(int len){
    //从最后一个非叶子结点开始遍历并向下调整
    for(int i=len/2;i>=1;--i){
        adjustdown(i,len);
    }
}

void heapsort(int len){
    if(len==0) return ;
    BuildMaxheap(len);
    cout<<a[1]<<" ";//输出堆顶元素
    a[1]=a[len];
    a.pop_back();
    adjustdown(1,len-1);//最后一个元素拿上来后向下调整
    heapsort(len-1);
}


int main(){
    heapsort(a.size()-1);
}