【转】简单选择排序 Selection Sort 和树形选择排序 Tree Selection Sort

选择排序 Selection Sort

　　选择排序的基本思想是：每一趟在剩余未排序的若干记录中选取关键字最小的（也可以是最大的，本文中均考虑排升序）记录作为有序序列中下一个记录。

　　如第i趟选择排序就是在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。

　　这样，整个序列共需要n-1趟排序。

 

简单选择排序

　　一趟简单选择排序的操作为：通过n-i次关键字的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换之。

　　代码如下：(假设记录为整型，并且关键字为其本身)

Selection Sort

typedef int ElemType;

void SelectSort(ElemType A[],int n)
{
    ElemType temp;

    for(int i=1;i<n;++i)
    {
        int k=i-1;
        for(int j=i;j<n;++j)
        {
            if(A[j]<A[k])
            {
                k=j;
            }
        }

        if(k!=i-1)
        {
            temp=A[i-1];
            A[i-1]=A[k];
            A[k]=temp;
        }
        
    }
}

 

　　容易看出，简单选择排序中，所需进行记录移动的操作次数较少，其最小值为“0”，最大值为3(n-1)。

　　然而，无论记录的初始序列如何，所需进行的关键字间的比较次数相同，均为n(n-1)/2，因此，总的时间复杂度为O(n²)。

　　因为简单选择排序没有利用上次选择时比较的结果，所以造成了比较次数多，速度慢。如果能够加以改进，将会提高排序的速度，所以出现了后面的树形选择排序和堆排序。

 

树形选择排序

　　树形选择排序（Tree Selection Sort），又称锦标赛排序（Tournament Sort），是一种按照锦标赛思想进行选择排序的方法。

　　首先对n个记录的关键字进行两两比较，然后在其中[n/2]（向上取整）个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。

　　这个过程可以用一棵有n个叶子结点的完全二叉树表示。如图中的二叉树表示从8个关键字中选出最小关键字的过程：

　　

                      

　　8个叶子结点中依次存放排序之前的8个关键字，每个非终端结点中的关键字均等于其左、右孩子结点中较小的那个关键字，则根结点中的关键字为叶子结点中的最小关键字。

　　在输出最小关键字之后，根据关系的可传递性，欲选出次小关键字，仅需将叶子结点中的最小关键字（13）改为“最大值”，然后从该叶子结点开始，和其左右兄弟的关键字进行比较，修改从叶子结点到根结点的路径上各结点的关键字，则根结点的关键字即为次小值。

 

 

 

　　同理，可依次选出从小到大的所有关键字。

　　由于含有n个叶子结点的完全二叉树的深度为[log₂n]+1，则在树形选择排序中，除了最小关键字以外，每选择一个次小关键字仅需进行[log₂n]次比较，因此，它的时间复杂度为O(nlogn)。

　　但是，这种排序方法也有一些缺点，比如辅助存储空间较多，并且需要和“最大值”进行多余的比较。

　　为了弥补，另一种选择排序被提出——堆排序。