三大排序.doc

从中我们可以看到,每次都会将后面的L-(i+1)个数拿来和a[i]比较,然后将小一点的换到前面。有人就觉得啊,这个每次都交换很费性能,影响效率。所以他们就将a[j]和a[i]比较后的最小值的下标记下来,当比较完之后,最后记下的下标就是最小的值的下标,然后再进行一次交换。于是便有了选择排序法。选择排序法代码: 1void SelectSort(int a[],int l) 2{ 3    for(int i = 0; i< l; ++i) 4    { 5        int k=i; 6        for(int j = i+1; j<l;++j) 7        { 8             9            if(a[j]<a[k])10            {11                k=j;12            }13        }14        int t = a[i];15        a[i]=a[k];16        a[k]= t;17    }18}虽然,我们并没有根本性地扭转冒泡排序的地位。但效率是有明显提升的,至少减少了L*(L-1)-L=L*(L-2)=L^2-2*L次交换!另外,目前广为使用的快速排序和选择排序联合使用,也会有意想不到的提升!众所周知,当用快速排序法排序时,划分到很细的时候,明显很亏。比如:两三个数排序却要划分成两堆,这样很划不来。所以,我们可以设定一个阀值,当快速排序划分到一定粒度的时候,便采用选择排序。至于这个阀值,可以通过performace来测试,以得到一个“最优值” 1void QSort(int a[],int l,int r) 2{ 3    int p; 4    if(l<r) 5    { 6        if(l-r<= DEFINE_NUMBER) 7            SelectSort(a,l,r); 8        else 9        {10            p = Partition(a,l,r);11            QSort(a,l,p-1);12            QSort(a,p+1,r);13        }14    }15}