学习计划

**
学习目标

永远充满热情，坚持21天学习打卡

学习内容

直接选择排序

学习日记

学习知识点

原理

        选择排序的核心思想是:每一趟从无序区中选出关键字最小的元素，按顺序放在有序区的最后（生成新的有序区，无序区元素个数减1)，直到全部排完为止。

直接选择排序

        也称简单选择排序，整个过程就是每一趟都将无序区中的所有元素进行逐一比较，找到最小的元素，与无序区中的首个元素进行交换，有序区长度加1，无序区长度减1。重复以上步骤，直到所有的元素均已排好。

树形选择排序

        也称锦标赛排序，是为了优化每次在无序区中确定最小元素时比较次数过多的问题。核心思想是借助树形结构对整个序列进行两两比较，将数值较小的元素作为优胜者上升到父节点。最后能够在树形结构中记录每一次优胜者之间的关系，按规则取出即可。

堆排序

        堆排序是对树形选择排序的优化，由于树形选择排序需要花费较多的存储空间，堆排序的主要思想是构建一个小顶堆(升序排列中)。整个的过程就是不断的弹出堆顶元素，归入有序区，然后继续将堆中剩余元素调整为小顶堆，重复这个过程，直到排好所有元素。
 算法步骤

        在第1趟中，从n个记录中找出关键字最小的记录与第1个记录交换;

        在第2趟中，从n-1个记录中找出关键字最小的记录与第2个记录交换;

        可以归纳为  在第i趟中，从n-i+1个记录中找出关键字最小的记录与第i个记录交换;直到完成i=n-1时的操作，此时整个序列有序。

算法复杂度

        选择排序不需要额外的存储空间，空间复杂度为O(1),所以是原地排序算法。

        最好、最差、平均时间复杂度都是O(n^2),因为无论你是否完全有序，还是完全逆序，都需要找出后边的最小值进行替换。

直接选择排序动图

 C代码

void selectsort(int a[],int n){
    for(int i=1;i<=n-1;i++){//进行n-1趟选择
        int index=i;
        for(int j=i+1;j<=n;j++)//从无序区选取最小的记录
            if(a[index]>a[j])
                index=j;
        if(index!=i)
            swap(a[i],a[index]);
    }
}