内部排序之---选择类排序

三：选择类排序

1：简单选择排序

【算法思想】第一趟简单选择排序时，从第一个记录开始，通过n-1次关键字的比较，从n个记录中选出关键字最小的记录，并且和第一个记录进行交换。第二趟简单排序，从第二个记录开始，通过n-2次关键字的比较，从n-1个记录中选择关键字最小的记录进行交换

如此反复，经过N-1趟简单排序后，将最小记录直接排到最后。

【算法描述】 

A：{48   62  35  77  55  14  35  98}//寻找最小的值与48交换

B: 14 {   62   35  77   55  48   35  98}//寻找到了14，然后除去14，继续寻找

C：14   35 {  62  77   55   48   35   98 }//寻找到了最开始的35，除去35继续

D：14   35   35{  77   55   48   62   98}//寻找到第二个35，继续寻找

E：14    35   35  48 {  55   77   62   98}//寻找到了48，继续

F：14    35   35  48   55   {77   62   98}//寻找到了55，继续

G：14    35   35  48   55   62   {72   98}//寻找到了62，继续

H：14    35   35  48   55   62   72   98//完成

【算法代码】

void selectsort(int *r,int len)

{

int i,j,k;

int n=len;

for(i=1;i<=n-1;i++)

{

k=i;

for(j=i+1;j<=n;j++)

{

if(r[j]

k=j;

}

if(k!=i)

{

r[0]=r[i];

r[i]=r[k];

r[k]=r[0];

}

Output(r,len);

}

}

【算法分析】

最好情况下，即待排序记录初始状态就已经是正序列了，则不需要移动，最换情况下。即待排序记录初始状态是按照逆序列的，则需要移动记录的次数最多为3(n-1)

时间复杂读为O（n^2）

2:堆排序

【算法思想】把待排序的记录存放在数组r[1...n]中，将r看成是一颗完全二叉树的顺序表示，每个节点表示一个记录，第一个记录r[1]看作是根，任意节点r[i]的做孩子是r[2*i],右孩子是r[2*i+1];双亲是r[i/2]。

堆定义：使得所有节点满足：r[i]>=r[2*i]&&r[i]>=r[2*i+1]，满足这个条件的完全二叉树叫做大堆根。

（1）重建堆之---调整堆（堆排序中最重要的算法）

 

（a）48的左右子树均为堆，准备筛48                             （b）将48移除，98准备上移

（c）98上移动后，77准备上移                                                  （d）77上移后，62准备上移

（e）62上移后，48准备移入空记录                                          （f）48移入空记录后，得到筛选的堆

【算法思想】首先将根节点移出，作为待调整记录。此时根节点相当于空节点，从空节点的左右孩子中选出一个关键字较大的记录，如果该记录的关键字大雨这个待调整的记录节点，则将该记录上移至空节点中。此时，那个关键字较大的子节点相当于空节点，从空节点的左右孩子中选出较大的记录，如果该记录的关键字仍然大于待调整记录的关键字。则该记录上移动到空节点。

【筛选的算法】

 

//调整堆的算法
void sift(int *r,int k,int m)
{
    int i,j,t;
    int flag;
    r[0]=r[k];
    i=k;
    j=2*i;
    flag=0;
    while(j<m&&!flag)
    {
        if(j<m&&r[j]<r[j+1])//先比较出两个孩子中最大的一个
            j++;
        if(r[0]>=r[j])
            flag=1;//如果根大于这个最大的孩子，则结束
        else
        {
            r[i]=r[j];//否则，将这个节点设置为那个最大的孩子
            i=j;//然后再往下一次比较
            j=2*i;
        }
    }
    r[i]=r[0];//将节点i的值设为r[0]
}

（2）堆排序之---建立初始堆

【算法思想】反复利用“调整堆算法”，自底向上逐层把所有子树调整为堆。

{48,62,35,77,55,14,35,98}，要求筛选一个堆，再此，n=8,所以先从第4个节点77开始筛选。依次筛选4,3,2,1

 

（a）初始序列对应的完全二叉树，首先准备筛选“77”    （b）77筛选完后，准备筛选35

 

（c）35筛选完比，准备筛选62                               （d）62筛选完后，准备筛选48

 

（e）48筛选完，得到一个大堆根                             

【建立初堆的算法】

void create_heap(int *r,int len)
{
    int n=len;
    int i;
    for(i=n/2;i>=1;--i)
        sift(r,i,n);
}

（3）堆排序之---堆排序

1）将待排序记录按照堆的定义建立初堆，并输出堆顶元素

2）调整剩余的记录序列，利用筛选法将前n-i个元素重新筛选建成一个新堆，再输出

3）重复执行第二步，进行n-1次筛选，新筛选的堆会越来越小，这个过程称之为堆排序

【过程】

（a）初始大根堆                                                （b）堆顶元素于堆尾元素交换

（c）将前7个元素（除了98）重新调整为堆                       （d）堆顶元素于堆尾交换（77与35交换）

 

（e）将前6个元素重新调整为堆                                   （f）堆顶元素于堆尾元素交换

（g）将前5个元素重新调整为堆                                  （h)堆顶元素与堆尾元素交换

（i）将前4个元素重新调整为堆                                 （j）堆顶元素于堆尾元素交换

（k）将前3个元素重新调整为堆                               （l）堆顶元素于堆尾元素交换

（m）将前2个元素重新调整为堆，堆顶于堆尾交换后，原序列有序

建立堆的时间复杂度为O(log2n),堆排序的时间复杂度为O(nlog2n)

【堆排序算法代码】

void heap_sort(int r[],int len)
{
    int i,n,b;
    n=len;
    create_heap(r,len);
    Output(r,len);
    for(i=n;i>=2;--i)
    {
        b=r[1];
        r[1]=r[i];
        r[i]=b;
        sift(r,1,i-1);
    }
    Output(r,len);

}

【堆排序与简单排序的例子】

 

#include<stdio.h>
#include<stdlib.h>

void Output(int *r,int len)
{
    int i;
    for(i=1;i<=len;i++)
        printf("%d ",r[i]);
    printf("\n");
}

//简单选择排序
void selectsort(int *r,int len)
{
    int i,j,k;
    int n=len;
    for(i=1;i<=n-1;i++)
    {
        k=i;
        for(j=i+1;j<=n;j++)
        {
            if(r[j]<r[k])
                k=j;
        }
        if(k!=i)
        {
            r[0]=r[i];
            r[i]=r[k];
            r[k]=r[0];
        }
        Output(r,len);
    }
}
//调整堆的算法
void sift(int *r,int k,int m)
{
    int i,j,t;
    int flag;
    r[0]=r[k];
    i=k;
    j=2*i;
    flag=0;
    while(j<m&&!flag)
    {
        if(j<m&&r[j]<r[j+1])//先比较出两个孩子中最大的一个
            j++;
        if(r[0]>=r[j])
            flag=1;//如果根大于这个最大的孩子，则结束
        else
        {
            r[i]=r[j];//否则，将这个节点设置为那个最大的孩子
            i=j;//然后再往下一次比较
            j=2*i;
        }
    }
    r[i]=r[0];//将节点i的值设为r[0]
}
//建立初堆
void create_heap(int *r,int len)
{
    int n=len;
    int i;
    for(i=n/2;i>=1;--i)
        sift(r,i,n);
}
//堆排序算法

void heap_sort(int r[],int len)
{
    int i,n,b;
    n=len;
    create_heap(r,len);
    Output(r,len);
    for(i=n;i>=2;--i)
    {
        b=r[1];
        r[1]=r[i];
        r[i]=b;
        sift(r,1,i-1);
    }
    Output(r,len);

}

int main()
{
    int r[8];
    int len=8;
    int t,i;
    printf("请输入您想要排序的数字：\n");
    for(i=1;i<=len;i++)
        scanf("%d",&r[i]);
    printf("请输入您想要选择的方式：");
    scanf("%d",&t);
    switch(t)
    {
        case 0:printf("简单排序开始:");
             selectsort(r,len);
             break;
        case 1:printf("堆排序开始：");
             heap_sort(r,len);
             break;
    }
}