直接选择排序

将待排序列看成左右两个子序列，左子序列是有序的，右子序列是无序的，并且左序列中最大关键字（在左序列的最右边）小于右序列的最小关键字。排序的过程为：定义某个变量i指向最大关键字的下一个位置，在右序列中找到最小关键字k，将i和k交换。

代码如下：

/* 直接选择排序 */
void StraightSelectionSort(int a[], int n)
{
    int i, j, k, tmp;
    for (i=0; i<n-1; i++)
    {
        k = i;  // a[0]...a[k]是有序的，a[k]最大
        for (j=i+1; j<n; j++)    // 找最小元素的下标k
        {
            if (a[j] < a[k])
                k = j;
        }
        if (i != k) // 交换
        {
            tmp=a[i]; a[i]=a[k]; a[k]=tmp;
        }
    }
}

直接选择排序的时间复杂度为O(n2)，空间复杂度为O(1)。当待排序列为正序时，不发生交换；当为逆序时，发生(n-1)次交换，移动次数为3(n-1)。