选择排序

选择排序

    1）原理：对于一个将要排序的数组A[n],先找出最小元素(升序排列)，将其与A[0]交换，接着在数组下标为1~n-1的元素中寻找最小值，与A[1]交换，直到排序结束。

    2）C语言实现：

void main()
{
    int t,temp,count, *p;
    printf("please input the count :");
    scanf_s("%d", &count);
    p = (int *)malloc(count * 2);
    printf("\nplease input the number to be sorted : \n");
    for (int i = 0; i < count; i++)
    {
        scanf_s("%d", p+i);
    }
    for (int i = 0; i < count; i++)
    {
        t = i;
        for (int j = i+1; j < count; j++)
        {
            if (p[t] > p[j])
            {
                t = j;
            }
        }
        temp = p[t];
        p[t] = p[i];
        p[i] = temp;
    }
    for (int i = 0; i < count; i++)
    {
        printf("%d ", p[i]);
    }
    system("pause");
}

    3）分析：

1. 最好情况(序列已经有序) ：在这种情况下，选择排序只需要将整个序列遍历一遍即可。故时间复杂度为O(n),为线性时间复杂度。
2. 最坏情况：每次遍历寻找最小元素A[i]时都需要从i寻找到最后一个元素，例如:2,3,4,5,6,7,8,9,1，在进行选择排序的时候很是吃亏，其时间复杂度为O(n^2)。
3. 平均情况：随机选择n个数来进行插入排序，每次寻找最小的元素大概能在中间的位置找到，平均时间复杂度也是O(n^2)。