基本排序（二）：选择排序 - 不断选出剩余数组中最小的元素

排序算法

• 选择排序过程：首先，选出数组中最小的元素，将它与数组中第一个元素交换，然后找出次小的元素，并将它与数组中第二个元素交换。。。直至整个数组排序完成。即通过不断选出剩余数组中最小的元素实现。
• 选择排序时间复杂度：O(N^2)
• 实现程序：

void Selection_sort(Item a[], int l, int r)
{
    for(int i = l; i < r; i++) //最后一个无需交换
    {
        int min = i;
        for(int j = i + 1; j <= r; j++)
        {
            if(less(a[j], a[min]))
                min = j;
        }
        exch(a[i], a[min]);
    }
}

• 缺点：运行时间对文件中已有序部分依赖较少。从文件中选出最小元素的每遍操作过程，并没有给出下一遍要找的最小元素位置的相关信息。
• 优点：对于元素比较大，关键字又比较小的文件，应该选择该算法。