【算法】直接选择排序解析

​

作者：[柒号华仔]
个人信条：星光不问赶路人,岁月不负有心人。
个人方向：主要方向为5G，同时兼顾其他网络协议，编解码协议，C/C++，linux，云原生等，感兴趣的小伙伴可以关注我，一起交流。

1. 直接选择排序介绍

1.1 定义

直接选择排序是指每次都从剩余数据中选出最大或者最小的，将其排在已经排好的有序表后面。

1.2 基本原理

每次从无序表中选择最小(或最大)元素，将其作为首元素，知道所有元素排完为止。将一个有n个元素的数组从小到大排序，第一次从R[0] ~ R[n-1]中选取最小值，与R[0]交换，第二次从R[1] ~ R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1] ~ R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2] ~ R[n-1]中选取最小值，与R[ n -2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

下面的动图非常清晰的诠释了直接插入排序的过程：

1.3 时间复杂度

最好的情况是数组所有元素已经是有序排列，移动次数为0；
最差的情况是数组所有元素全部反序，移动次数为3(n-1)。

无论最好与最差情况，在排序时所有待排元素均需与后面的元素进行比较，比较次数为：
(n-1)+(n-2)+ ...+2+1= n(n-1)/2

因此，直接插入排序的平均时间复杂度为O($n^2$) 。

1.4 空间复杂度

直接选择排序仅需一个存储空间用于记录交换的暂存单元，因此空间复杂度为：O(1) 。

1.5 优缺点

优点：直接选择排序算法简单直观，当待排序记录数量n很小时，局部有序时，较为适用。
缺点：不稳定，由于直接选择排序是以最大或最小值直接与最前方未排序的键值交换，数据排序顺序很有可能被改变。

2. 代码实现

2.1 代码设计

a. 实现直接插入排序需要设计两层循环，整个数组为外循环，后面未排列好的无序元素为内循环；
b. 使用变量minIndex存储最小值的数组元素下标，依次遍历无序元素，找出最小元素下标；
c. 将最小元素与无序元素的首元素进行交换，无序元素个数减1，相应i加1；
d. 重复b和c两步操作，直至i=n-1，即无序元素个数为0，则排序完成。

2.2 代码实现

#include <stdio.h>

void printArray(int array[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
} 

void chooseSort(int array[],int n)
{
    int i,j;
    int minIndex,temp,num;
    for(i=0;i<n-1;i++)
    {
        minIndex=i;
        for(j=i+1;j<n;j++)
        {
            if(array[j]<=array[minIndex])
            {
                minIndex=j;
            }
        }
        if(i!=minIndex)
        {
            temp=array[minIndex];
            array[minIndex]=array[i];
            array[i]=temp;
        }
        printArray(array, n);
    }
}

int main(void)
{
    int array[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

    printArray(array,sizeof(array)/sizeof(int));
    chooseSort(array,sizeof(array)/sizeof(int));
    printf("\n");
    return 0;
}

运行结果：

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
2 44 38 5 47 15 36 26 27 3 46 4 19 50 48
2 3 38 5 47 15 36 26 27 44 46 4 19 50 48
2 3 4 5 47 15 36 26 27 44 46 38 19 50 48
2 3 4 5 47 15 36 26 27 44 46 38 19 50 48
2 3 4 5 15 47 36 26 27 44 46 38 19 50 48
2 3 4 5 15 19 36 26 27 44 46 38 47 50 48
2 3 4 5 15 19 26 36 27 44 46 38 47 50 48
2 3 4 5 15 19 26 27 36 44 46 38 47 50 48
2 3 4 5 15 19 26 27 36 44 46 38 47 50 48
2 3 4 5 15 19 26 27 36 38 46 44 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50