[C语言][排序(3)]选择排序+堆排序

1.选择排序

选择排序的思想就是从未排序部分中选出最小的那个元素,然后换到有序部分的最后位置。

比如:3 2 4 1

从 3 2 4 1中选出1,与第一个元素3交换位置:1243;现在1是有序部分,243是无序部分,再从243选出最小值2,与有序部分最后交换,恰好为2,交换后仍然为1243,现在12为有序部分,43是无序部分,依次进行。

void Swap(int *a,int *b)
{
      int c;
       c=*a;
       *a=*b;
       *b=c;
}
//ÆÕͨµÄ²åÈëÅÅÐò
int ScanForMin(int a[],int k,int n)
{
    int i,MinPosition,MinValue=Int;
    for(i=k;i

2.堆排序

可以发现,选择排序需要找最小元的时候耗时太多,我们之前学习过堆,可以很快找到最小元,因此我们可以利用堆找最小元的方法进行排序。

typedef struct MinHeap *Heap;
struct MinHeap
{
    int *data;
    int capacity;
    int hsize;
};
void PreDown(Heap h,int root)
{
    int i,parent,child,x;
    x=h->data[root];
    for(parent=root;parent*2<=h->hsize;parent=child)
    {
        child=parent*2;
        if(child!=h->hsize&&h->data[child]>h->data[child+1])
            child++;
        if(x<=h->data[child])
            break;
        else
            h->data[parent]=h->data[child];
    }
    h->data[parent]=x;
}
void BuildHeap(Heap h)
{
    int i;
    for(i=h->hsize/2;i>0;i--)
    {
        PreDown(h,i);
    }
}
Heap MakeHeap(int a[],int n)
{
    Heap h;
    int i;
    h=(Heap)malloc(sizeof(struct MinHeap));
    h->data=(int*)malloc(Maxsize*sizeof(int));
    h->hsize=0;
    h->capacity=Maxsize;
    h->data[0]=Maxsize;
    for(i=1;i<=n;i++)
    {
        h->data[i]=a[i];
        h->hsize+=1;
    }
    BuildHeap(h);
    return h;

}
int DeleteHeap(Heap h)
{
    if(h->hsize==0)
        return 0;
    int MinValue,x,parent,child;
    MinValue=h->data[1];
    x=h->data[h->hsize--];
    for(parent=1;parent*2<=h->hsize;parent=child)
    {
        child=parent*2;
        if(child!=h->hsize&&h->data[child]>h->data[child+1])
            child++;
        if(x<=h->data[child])
            break;
        else
            h->data[parent]=h->data[child];
    }
    h->data[parent]=x;
    return MinValue;
}
void Heap_sort(int a[],int n)
{
    Heap h;
    int i;
    int tmpa[n];
    h=MakeHeap(a,n);
    for(i=1;i<=n;i++)
    {
        tmpa[i]=DeleteHeap(h);
    }
    for(i=1;i<=n;i++)
    {
        a[i]=tmpa[i];
    }
}

不断用最小堆的删除,得到最小元,但这样的方法需要额外的空间。因此,我们换一个角度,完全模仿选择排序的思路,当建好最小堆之后,我们将堆根的元素和堆最后一个元素交换位置,然后重新调整从堆根到倒数第二个元素的最小堆,这样就把最小的值存储在数字的末尾,依次这样交换,只需要将数组倒序输出即可。直接用原数组表示堆。

void Swap(int *a,int *b)
{
      int c;
       c=*a;
       *a=*b;
       *b=c;
}
void PreDown(int a[],int root,int n)
{
    int i,parent,child,x;
    x=a[root];
    for(parent=root;parent*2+1<=n-1;parent=child)
    {
        child=parent*2+1;
        if(child!=n-1&&a[child]>a[child+1])
            child++;
        if(x<=a[child])
            break;
        else
            a[parent]=a[child];
    }
    a[parent]=x;
}
void Heap_sort(int a[],int n)
{
    int i;
    for(i=n/2-1;i>=0;i--)
    {
        PreDown(a,i,n);
    }
    for(i=n-1;i>0;i--)
    {
        Swap(&a[0],&a[i]);
        PreDown(a,0,i);
    }
}

 

你可能感兴趣的