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

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/* 直接选择排序 */
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)。