Posted by : Nguyễn Văn Tuấn 30 March 2014

Sắp xếp vun đống (Heapsort) dựa trên một cấu trúc dữ liệu được gọi là đống nhị phân (binary heap), gọi đơn giản là đống. Trong mục này chỉ nói về đống trong bài toán sắp xếp.

Đọc thêm tại: Wikipedia

Heap.PNG
Code:

#include <iostream>
using namespace std;
void heap_sort(int a[], int n)
{
int k,x,s,f,ivalue;
for(k=1;k<n;k++)
    {
    x=a[k];
    s=k;
    f=(s-1)/2;
    while(s>0 && a[f]<x)
        {
        a[s]=a[f];
        s=f;
        f=(s-1)/2;
        }
    a[s]=x;
    }
for(k=n-1;k>0;k--)
    {
    ivalue=a[k];
    a[k]=a[0];
    f=0;
    if(k==1)
        s=-1;
    else
        s=1;
        if(k>2 && a[2]>a[1])
        s=2;
    while(s>=0 && ivalue<a[s])
        {
        a[f]=a[s];
        f=s;
        s=2*f +1;
        if (s+1<=k-1 && a[s]<a[s+1])
            s=s+1;
        if (s>k-1)
            s=-1;
        }
    a[f]=ivalue;
    }
}

int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    heap_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";
}





Leave a Reply

Subscribe to Posts | Subscribe to Comments

- Copyright © Kiến thức tổng quan - Kiến Thức Tổng Quan - Powered by Blogger - Designed by SnowBlack -