七大排序之选择排序

<SelectionSort>
“从篮子里取苹果排大小”
是冒泡排序的改进：小步慢跑——找到最小后再放入Sorted序列中，而不是一次一次交换。
简而言之，就是通过n-i次关键字之间的比较，从n-i+1个记录里选出关键字最小的记录，并与第i个元素交换之。

void SelectionSort(int a[],int lo,int hi)
{
    int n=hi-lo+1;
    int index;

    for(int i=lo;i<lo+n-1;i++)
    {
        index=i;
        for(int j=i+1;j<lo+n;j++)//通过j（从i后一个元素开始递增）一次又一次的扫描
                                      //将index替换为未排序数组中最小元素的下标值
        {
            if(a[index]>a[j]) index=j;
        }
        swap(a[i],a[index]);
    }
}

时间复杂度分析：
第i趟排序需要n-i次关键字之间的比较，此时需要比较的次数为(n-1)+(n-2)+...+1=n(n-1)/2次。对于交换次数而言，当最好的时候交换0次，最差的时候交换n-1次，总的时间幅度依然为O(n^2)。
性能依然优于冒泡排序，效率体现在移动操作远远少于冒泡排序。