数据库入门级之算法【三】

之前我们跟随笔者重温了数据结构中的查询算法和部分排序算法，现在我们继续跟随笔者继续学习一些基本的排序算法。

选择排序

使用条件：可对比大小的集合。

算法思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}

//简单选择排序  
void SimpleSelect(int b[10])  
{  
    int temp;  
    int i;  
    for(i=0;i<9;i++)  
    {  
        for(int j=i+1;j<9;j++)  
        {  
            if(b[i]>b[j])  
            {  
                temp=b[i];  
                b[i]=b[j];  
                b[j]=temp;  
            }  
        }  
    }  
    cout<<"the sort is:";  
    for(int i=0;i<10;i++)  
    {  
        cout<<b[i]<<" ";  
    }  
    cout<<endl;  
}  

性能分析：时间复杂度为O（n^2）

堆排序

使用条件：可对比大小的集合。

算法思想：其实堆排序是简单选择排序的一种进化，它最主要是减少比较的次数。什么是堆？若将序列对应看成一个完全二叉树，完全二叉树中所有非终端节点的值均不大于（或者不小于）其左右孩子节点的值，可以称作为堆。由堆的性质可以知道堆顶是一个最大关键字(或者最小关键字)。在输出堆顶后，使剩下的元素又建成一个堆，然后在输出对顶。如此反复执行，便能得到一个有序序列，这个过程成便是堆排序。

堆排序主要分为两个步骤：

1. 从无序序列建堆。
2. 输出对顶元素，在调成一个新堆。

举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}

//堆排序  
void HeapSort(int b[10])  
{  
    void HeapAdjuest(int b[10],int min,int max);  
    void Sawp(int *a,int *b);  
    int i;  
    //因为是完成二叉树，所以从最后一个非叶子节点开始堆转换  
    for(i=9/2;i>=0;i--)  
    {  
        HeapAdjuest(b,i,9);  
    }  
    //拿出堆顶数据在从新堆排序  
    for(i=9;i>0;i--)  
    {  
        Sawp(&b[i],&b[0]);  
        HeapAdjuest(b,0,i-1);  
    }  
}  
//堆调整(大顶堆)  
//min 数据需要调整在数组中的开始位置  
//max 数据需要调整在数据中的结束位置  
void HeapAdjuest(int b[10],int min,int max)  
{  
    if(max<=min)return ;  
    int temp;  
    temp=b[min];  
    int j;  
    //延它的孩子节点循环  
    for(j=2*min;j<=max;j*=2)  
    {  
        //选择它的大孩子  
        if(j<max&&b[j]<b[j+1])  
        {  
            j++;  
        }  
        //堆顶小于它的孩子不做处理  
        if(temp>b[j])  
        {  
            break;  
        }  
        //将大的数替换成小的数  
        b[min]=b[j];  
        min=j;  
        }  
    b[min]=temp;  
}  
//交换函数  
void Sawp(int *a,int *b)  
{  
    int temp;  
    temp=*a;  
    *a=*b;  
    *b=temp;  
}  

性能分析：时间复杂度时间复杂度O(nlogn)

归并算法又称2路归并算法

使用条件：可对比大小的集合。

算法思想：假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1，然后两两归并，得到[n/2]个长度为2或者为1（这里长度为1可能这里序列长度是奇数，那么最后一个序列就落单了，所以长度为1）；在两两归并，如此重复，直至得到一个长度为n的有序序列为止。

举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}

//归并排序  
void MergeSort(int b[10],int d[10],int min,int max)  
{  
    //用与存放中间分区域得到的序列  
    int c[10];  
    void Merge(int c[10],int d[10],int min,int mid,int max);  
    if(min==max)d[min]=b[min];  
    else 
    {  
        //平分成两个区域  
        int mid=(min+max)/2;  
        //将这个区域进行归并排序  
        MergeSort(b,c,min,mid);  
        //将这个区域进行归并排序  
        MergeSort(b,c,mid+1,max);  
        //两个区域归并  
        Merge(c,d,min,mid,max);  
    }  
}  
//将有序序列d[min-mid]与d[mid+1-max]归并成有序序列c[min-max]  
void Merge(int c[10],int d[10],int min,int mid,int max)  
{  
    int i,j,k;  
    for(i=j=min,k=mid+1;j<=mid&&k<=max;i++)  
    {  
        if(c[j]>c[k])  
        {  
            d[i]=c[k];  
            k++;  
        }  
        else 
        {  
            d[i]=c[j];  
            j++;  
        }  
    }  
    if(j<=mid)  
    {  
        for(;j<=mid;j++,i++)  
        {  
            d[i]=c[j];  
        }  
    }  
    if(k<=max)  
    {  
         for(;k<=max;k++,i++)  
        {  
            d[i]=c[k];  
        }  
    }  
}  

性能分析：时间复杂度O(nlogn)

总结

因为不同的排序方法适应不同的应用换进和要求，选择合适的排序方法考虑以下因素:

1. 待排序的记录数n
2. 对其稳定性要求
3. 存储结构
4. 时间和辅助空间复杂度

那么这么多排序算法，到底什么时候用什么样的算法呢？

如果n比较小（例如n<=50),可采用直接插入排序或者简单选择排序。

如果序列初始状态基本有序，则可选用直接插入排序，冒泡排序。

如果n比价大，则可采用时间复杂度为O(nlogn)的算法：快速排序，堆排序，归并排序。

1. 快速排序被认为目前基于比较的内部排序中最好的方法。当带排序的关键字随机分布时，快速排序平均时间最短。 不稳定
2. 堆排序所需要的辅助空间小于快速排序，并且不会出现快速排序可能出现的最坏情况。 但还是比较不稳定
3. 归并排序，比较稳定，但是归并排序一般不提倡使用，实用性很差，占用的辅助空间肯能个比较大。

 原文链接：http://www.cnblogs.com/couhujia/archive/2011/03/25/1994996.html

【编辑推荐】

1. 初探数据挖掘中的十大经典算法
2. 当今世界最受人们重视的十大经典算法
3. 程序员须知之面试时算法题的解答思路
4. 数据库入门级之算法【一】
5. 数据库入门级之算法【二】