大话数据结构-9.4 简单选择排序 - 高飞网

9.4 简单选择排序

2017-01-23 10:57:22.0

9.4.1 简单选择排序算法

    简单选择排序法(Simple Selection Sort)就是通过n-i次关键字之间的比较,从n-i+1个记录中选择出关键字最小的记录,并和第i(1≤i≤n)个记录交换之。

/* 选择排序 */                                                  
void SelectSort(SqList *L)                                      
{                                                               
    for(int i=1;i<L->length;i++)                                
    {                                                           
        int min = i;//假定当前i为最小的                         
        for(int j=i+1;j<=L->length;j++)//循环之后数据           
        {                                                       
            if(L->r[j]<L->r[min])//找到更小的数,更新最小数索引 
                min = j;                                        
        }                                                       
        if(i!=min)//发现最小数后,交换                          
            swap(L,i,min);                                      
    }                                                           
}                                                               

9.4.2 简单选择排序复杂度分析

    简单选择排序的最大特点是交换移动数据次数相当少,这样也就节约了时间。分析发现,最好最差,都要进行n(n-1)/2次比较,而最好的交换次数为0,最差时是n-1次,因此总的时间复杂度为O(n2)。

    尽管与冒泡排序同为O(n2),但简单选择排序的性能上还是要略优于冒泡排序。