选择排序法及其优化
巧若拙

选择排序基础算法是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序基础算法代码如下：
void SelectSort_1(int vec[], int n) //选择排序基础算法
{
    int i, j, min;
    int temp;
   
    for (i=0; i<n-1; i++)
    {
        min = i;
        for (j=i+1; j<n; j++)
        {
            if (vec[j] < vec[min])
            {
                min = j;
            }
        }
        
        if (min != i)
        {
            temp = vec[i];
            vec[i] = vec[min];
            vec[min] = temp;
        }   
    }
}

为了减少比较的次数，可采用每一趟扫描时，同时选出最大和最小值，这样逐步缩小扫描范围，直到只剩下一个元素。
    改进版本中有一点要注意：如果最大值在最左边，肯定要被移走，此时要转移到相应的新位置。
选择排序基础改进代码如下：
void SelectSort_2(int vec[], int n) //选择排序改进算法：同时选出最大和最小值
{
    int i, min, max, left, right;
    int temp;
   
    for (left=0, right=n-1; left<right; left++, right--)
    {
        min = left;
        max = right;
        for (i=left; i<=right; i++)
        {
            if (vec[i] < vec[min])
            {
                min = i;
            }
            else if (vec[i] > vec[max])
            {
                max = i;
            }
        }
        
        if (min != left)
        {
            temp = vec[left];
            vec[left] = vec[min];
            vec[min] = temp;
            
            if (max == left) //如果最大值在最左边，肯定要被移走，此时要转移到相应的新位置
            {
                max = min;
            }
        }   
        
        if (max != right)
        {
            temp = vec[right];
            vec[right] = vec[max];
            vec[max] = temp;
        }
    }
}

简单说说吧：
这种算是复杂度不变的优化，可能代码的编程复杂度变了，但是呢实际程序需要的时间和空间开销仍然没有变
真正能够实现排序优化的，你如果继续研究你肯定会发现的。简单一个方向，使用分治，嘘别告诉别人哦

楼上说的是快排吗？
我“同时选出最大和最小值”的算法在平均时间复杂度上应该是比单纯找最小值的算法好，是1.5n 和 2n的区别。