排序算法-选择排序（C语言）_m0_61150341的博客

选择排序，简单粗暴直观的排序算法。

一个长度为N的序列num[N]，分为有序部分和无序部分

第一次，num[0]~num[N-1]是无序部分，从这N个数中选出最小的数，放在序列的第一个位置，

此时，num[0]是有序部分，num[1]~num[N]是无序部分

第二次，num[0]是有序部分，num[1]~num[N]是无序部分，从N-1个数中选出最小的数，放在序列的第二个位置，

此时，num[0]~num[1]是有序部分，num[2]~num[N]是无序部分

如此进行下去，整个序列最终为有序（顺序）序列

代码：

#include<stdio.h>
#define N 10
void selectsort(int *num , int length )
{ 
    int i ;
    int j;
    int temp;//中间变量，供交换值的时候使用
    for(i = 0;i < length ; i ++)//假设无序序列的第一个元素num[i]为最小值
    {   
        for(j = i+1 ; j < length ;j++)//遍历最小值后面的所有元素(num[i+1]~num[length-1])
        {
            if(num[i] > num[j])//若找到比最小值num[i]还要小的元素，则与原来的最小值元素交换值
            {
                temp = num[i];
                num[i] = num[j];
                num[j] = temp;
            }
        }
    }
}

int main()
{
    int num[N] = {9,8,7,6,5,4,3,2,1,0};
    selectsort(num , N);
    for(int i=0; i < N;i++)
    {
        printf("%d ",num[i]);
    }
    printf("\n");
    return 0;
}

运行结果

看一下程序细节

时间复杂度

第一次需要遍历N-1个元素，第二次需要遍历N-2个元素······

$\large \sum_{i=1}^{n-1}(n-i)=n-1+ n-2 +\cdot \cdot \cdot +1 = \frac{n(n-1)}{2}$

所以时间复杂度是）O（N^2）

然而，细想一下，选择排序，每一趟遍历无序部分，却只为了找到那个最小的数，效率太低（老子辛辛苦苦在无序序列兜了一圈，只找一个最小值，这哪行，哪像计算机人搜搜扣扣的精神（又扣时间又扣空间））

于是，赶一只羊也是赶，赶两只羊也是赶。我们跑一趟无序序列，把最小值和最大值都找出来。

代码：

#include<stdio.h>
#define N 10
#include<time.h>
void  swap(int *a,int *b)//函数作用，交换a和b的值
{
    int temp ;
    temp = *a;
    *a = *b;
    *b = temp;
}
void selectsort(int *num ,int n)
{   
    int start = 0;//无序部分的第一个元素
    int end = N-1;//无序部分的最后一个元素
    while(start < end)
    {
        int min_index = start;//最小值元素的下标
        int max_index = end;//最大值元素的下标
        int i = 0;
        for(i = start;i<=end;i++)//遍历无序序列
        {
            if(num[i] < num[min_index])
                min_index = i;//记录无序序列最小值元素的下标
            if(num[i] > num[max_index])
                max_index = i; //记录无序序列最大值元素的下标
        }
        swap(&num[start],&num[min_index]);//将找到的最小值放在序列开头
        //错误语句实例 swap(&num[end],&num[max_index]);
        //将找到的最大值放在序列末尾，看似合情合理，但在极端情况下与上一句语句是矛盾的
        //本例就属于极端情况，此处挖一个坑
       
        if(start == max_index)//极端情况，当最大值位于序列开头，要被最小值替换
        {
            max_index = min_index;
        }
        start++;//缩小无序序列长度，因为有序序列变长了
        end--;

        //细节演示
        // for(int i = 0;i<N;i++)
        // {
        // printf("%d ",num[i]);
        // }
        // printf("\n");

    }
}

int main()
{   
    int num[N] = {9,8,7,6,5,4,3,2,1,0};
    selectsort(num,N);
    for(int i = 0;i<N;i++)
    {
        printf("%d ",num[i]);
    }
    printf("\n");
    return 0;
}

运行结果：