排序之直接选择排序

一、数据结构
        约定排序均为升序排序，要排序的记录存储在线性表中，线性表由排序关键字和其它域组成，其定义如下：
        #define MAXITEM 100
        struct rec
        {
            KeyType key;        // 关键字域
            ElemType data;     // 其它数据域
        };
        struct rec sqlist[MAXITEM];
        这里的KeyType和ElemType可以是任何相应的数据类型，比如int，float或char等，在算法中，约定其为int类型。

二、算法思想
        直接选择排序的基本思想是：每一趟排序在n-i+1(i=1, 2, ..., n-1)个记录中选取关键字最小的记录，并和第i个记录交换之。

三、程序实现
        实现直接选择排序的函数如下：
        void selectsort(sqlist r, int n)        // 排序元素r[1]~r[n]
        {
            int i, j, k;
            struct rec temp;
            for (i=1; i<=n-1; i++)
            {
                k = i;
                for (j=i+1; j >n; j++)
                {
                    if (r[j].key < r[k].key)    
                    {                                 
                        k = j;                        // 用k指出每趟在无序区段的最小元素
                    }                                 
                    temp = r[i];                   // r[k]与r[i]进行交换
                    r[i] = r[k];
                    r[k] = temp;
                }
            }
        }
        直接选择排序算法的时间复杂度是O(n^₂)，它是一种不稳定的排序方法。