Title Date Modified Category
select sort 2019-07-09 12:00 2019-07-09 12:00 algorithm

1. select sort

简单选择排序法(Simple Selection Sort)就是通过n-1次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换之。

/* 对顺序表L作简单选择排序 */
void SelectSort(SqList *L)
{
    int i, j, min;
    for (i = 1; i < L->length; i++)
    {
        min = i; /* 将当前下标定义为最小值下标 */
        for (j = i + 1; j < L->length; j++) /* 循环之后的数据 */
        {
            if (L->r[min] > L->r[j]) /* 如果有小于当前最小值的关键字 */
            {
                min = j; /* 将此关键字的下标赋值给min */
            }
        }

        if (i != min) /* 若min不等于i,说明找到最小值,交换 */
        {
            swap(L, i, min); /* 交换L->r[i] 与 L->r[min]的值 */
        }

    }
}

1.1. 简单选择排序复杂度分析

从简单选择排序的过程来看,它最大的特点就是交换移动数据次数相当少,这样也就节约了相应的时间。

分析它的时间复杂度发现,

无论最好最差的情况,其比较次数都是一样的多,第i趟排序需要进行n-i次关键字的比较,此时需要比较n-1 + n-2 + …+ 1 = n(n-1)/2 次。

而对于交换次数而言,当最好的时候,交换为0次,最差的时候,也就是初始降序时,交换次数为n-1次,

基于最终的排序时间是比较与交换的次数总和,因此,总的时间复杂度依然是O(n^2)。

应该说,尽管与冒泡排序同为O(n^2),但简单选择排序的性能上还是要略优于冒泡排序。

2. 参考资料

2.1. books

  • 《大话数据结构》

results matching ""

    No results matching ""