CSDN21天学习挑战赛之选择排序

• 选择排序的概念
• • 1.直接选择排序
  • • 概念
    • c++实现
    • 复杂度分析
  • 2.堆排序
  • • 概念
    • C++实现
    • 复杂度分析

“九层之台，起于垒土”。学习技术须脚踏实地。

本文为CSDN21天学习挑战赛系列专栏内容，介绍直接插入排序与改进后的堆排序。

活动地址：CSDN21天学习挑战赛

算法的每一趟从无序区中选出键值最小的元素，放在有序区的后面，直至结束。

直接选择排序也称简单选择排序，算法过程就是扫描无序区，从中选择出最小的元素，与无序区第一个元素互换，直至整个数列有序。

动图演示：

参考：菜鸟教程

template 
void direct_select_sort(std::vector& arr) {
        for (int i = 0; i < arr.size() - 1; i++) {
                int min = i;
                for (int j = i + 1; j < arr.size(); j++)
                        if (arr[j] < arr[min])
                                min = j;
                std::swap(arr[i], arr[min]);
        }
}

• 时间复杂度：每次寻找最小元素都要扫描一遍无序数组，
  • 比较时间：T = （n-1)）+ （n -2）+（n - 3）… + 1; ===>> T = [n*(n-1) ] / 2，即O(n²)。
  • 交换时间：最好的情况全部元素已经有序，则 交换次数为0；最差的情况，全部元素逆序，就要交换 n-1 次；
• 空间复杂度：只需要一个临时量存储极值元素，所以为O(1)。

预备知识：

完全二叉树：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。

完全二叉树的性质：左边子节点位置 = 当前父节点的两倍 + 1，右边子节点位置 = 当前父节点的两倍 + 2

大根堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小根堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序，是根据完全二叉树的性质利用大根堆这种数据结构进行的排序。

算法步骤：

• 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
• 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
• 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

动图演示：

参考：JS-Sorting-Algorithm

template 
void adjust(T* arr, int len, int index)
{
    int left = 2*index + 1;
    int right = 2*index + 2;
    int maxIdx = index;
    if(left arr[maxIdx]) maxIdx = left;
    if(right arr[maxIdx]) maxIdx = right; 
    if(maxIdx != index) 
    {
        std::swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);    
    }

}
void heapSort(T* arr, int size)
{
    for(int i=size/2 - 1; i >= 0; i--)  
    {
        adjust(arr, size, i);
    }
    for(int i = size - 1; i >= 1; i--)
    {
        swap(arr[0], arr[i]);
        adjust(arr, i, 0); 
    }
}

• 时间复杂度：
  • 比较时间：建堆是通过父节点和子节点两两比较并交换得到的，时间复杂度为O（n）。
  • 交换时间：调整堆需要交换n-1次堆顶元素，并调整堆，调整堆的过程就是满二叉树的深度logn。
    所以时间复杂度为O(nlogn)。
• 空间复杂度：需要几个变量存储索引，所以为O(1)。

本周的学习就到此结束了，本周还是以复习经典排序算法为主，自己又练习了一下希尔排序和堆排序，学习算法过程中动图有助于我们了解算法执行的过程当然自己画一遍试试坑会理解的更深。


我是博仔，期待你的关注，让我们一起进步！