1.简单选择排序

核心思想

遍历整个数组，从当前元素后面的所有元素中找出一个最小的元素，并与当前元素交换。

核心代码

void SelectSort()
{
    int n=11;
    for (int i=1;i<n;i++)
    {
        int min=i;
        for (int j=i+1;j<=n;j++)
        {
            if (a[min]>a[j]) min=j;
        }
        if (min!=i) swap(&a[i],&a[min]);
    }
}

举例

9 8 7 6 5

第一趟：5 8 7 6 9

第二趟：5 6 8 7 9

第三趟：5 6 7 8 9

排序完成

特点

元素间比较次数与初始状态无关，始终是n（n-1）/2

2.堆排序

核心思想（从大到小排序）

构建大根堆，每次将数组第一个元素（根）输出，然后将最后一个元素与第一个元素交换，重新调整堆。

核心代码

//堆
void HeadAdjust(int k,int n)
{
    a[0]=a[k];
    for (int i=k*2;i<=n;i*=2)
    {
        if (i<n&&a[i+1]>a[i]) i++;
        if (a[0]>=a[i]) break;
        else
        {
            a[k]=a[i];
            k=i;
        }
    }
    a[k]=a[0];
}
void BuildMaxHeap(int n)
{
    for (int i=n/2;i>0;i--) HeadAdjust(i,n);
}
void HeapSort()
{
    int n=11;
    BuildMaxHeap(n);
    for (int i=n;i>1;i--)
    {
        printf("%d ",a[1]);
        swap(&a[1],&a[i]);
        HeadAdjust(1,i-1);
    }
}

代码流程

首先是建堆（从最后一个叶结点的双亲开始，一直到根结点调整堆），然后是调整堆。

每次调整堆的时候选出叶子结点较大的那个，与双亲比较，如果叶子结点大，就交换，并且继续往下调整。

3.总结

稳定性

两种选择排序都是不稳定的排序。

空间复杂度

简单选择排序是O（1）

堆排序是O（1）

时间复杂度

简单选择排序O（$n^2$)

堆排序O（nlogn）